Single-Leg Revenue Management with Advice

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.

Funding: This work was supported by the Office of Naval Research awards [N00014-22-1-2530 and N00014-23-1-2374] and the National Science Foundation awards [IIS-2147361 and IIS-2238960].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2022.0363.