Sequential Resource Allocation and Applications in Revenue Management

Abstract

Sequential resource allocation is a fundamental problem in operations research, encompassing a wide range of applications where decisions must be made dynamically under uncertainty. This thesis develops new theoretical foundations, explores practical applications, and establishes evaluation methodologies for sequential resource allocation, with a focus on revenue management, robustness and fairness, and experiment design. On the theoretical side, this thesis advances the study of classical network revenue management, a long-standing challenge in dynamic resource allocation. We introduce the first LP-free algorithm, improving the regret bound from O(T ^1/2) to O(T ^3/8)—a significant step toward closing the gap between existing algorithms and the theoretical lower bound of O(1). Additionally, we enhance robustness in sequential resource allocation by developing algorithms that incorporate machine-learned advice, striking a balance between overly conservative worst-case models and overly optimistic stochastic assumptions. Furthermore, we integrate individual fairness into sequential decision-making, ensuring equitable resource allocation without compromising competitive performance. On the application side, we demonstrate the impact of sequential resource allocation in the hospitality management domain. Collaborated with Oracle Lab, we design an online upgrading mechanism that enables hotels to dynamically determine when and at what price to offer room upgrades. Additionally, we propose near-optimal, fast approximation algorithms for this mechanism, achieving a regret bound of O(logT), which is close to the natural lower bound of O(1). We also incorporate our upgrading algorithm to a hotel dataset, and improves more than 20% revenue in 2022. Finally, we introduce new methodologies for evaluating sequential decision-making policies, with a focus on online experiment design. Traditional A/B testing methods struggle with dynamically arriving data, leading to biased or inefficient experimental results. Our pigeonhole experimental design effectively reduces bias and outperforms several well-known experimental design policies, including matched pair design and completely randomized design, making it a more reliable approach for evaluating sequential decision-making strategies. By unifying theoretical insights, real-world applications, and online evaluation frameworks, this thesis contributes to the broader field of sequential resource allocation, providing fundamental advancements with practical implications across revenue management and experimental design.