Single-Leg Revenue Management with Advice

• 成果类型: Article; Early Access
• 署名作者: Balseiro, Santiago R.; Kroer, Christian; Kumar, Rachitesh
• 署名单位: Columbia University; Columbia University; Carnegie Mellon University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0363
• 发表日期: 2025
• 关键词: online; algorithm

摘要

Single-leg revenue management is a foundational problem of revenue management that has been particularly impactful in the airline and hotel industry: Given n units of a resource, for example, flight seats, and a stream of sequentially arriving customers segmented by fares, what is the optimal online policy for allocating the resource? Previous work focused on designing algorithms when forecasts are available, which are not robust to inaccuracies in the forecast, or online algorithms with worst-case performance guarantees, which can be too conservative in practice. In this work, we look at the single-leg revenue management problem through the lens of the algorithms-with-advice framework, which attempts to harness the increasing prediction accuracy of machine learning methods by optimally incorporating advice about the future into online algorithms. In particular, we provide an online algorithm that attains every point in the Pareto frontier between consistency (performance when advice is accurate) and competitiveness (performance when advice is inaccurate) for every advice. We also study the class of booking limit policies, which is the most widely deployed technique for single-leg revenue management: We provide an algorithm to incorporate advice into booking limits that optimally trades off consistency and competitiveness. Moreover, we numerically evaluate the performance of these algorithms on synthetic data. We find that our algorithm for booking limit policies performs remarkably well on most instances, even if it is not guaranteed to be on the Pareto frontier in theory. Our results extend to other unit-cost online allocations problems such as the display advertising and the multiple secretary problem together with more general variable-cost problems such as the online knapsack problem.