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, e.g. 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 optimally incorporate
advice/predictions about the future into online algorithms. In particular, we
characterize the Pareto frontier that captures the tradeoff between consistency
(performance when advice is accurate) and competitiveness (performance when
advice is inaccurate) for every advice. Moreover, we provide an online
algorithm that always achieves performance on this Pareto frontier. We also
study the class of protection level policies, which is the most widely-deployed
technique for single-leg revenue management: we provide an algorithm to
incorporate advice into protection levels that optimally trades off consistency
and competitiveness. Moreover, we empirically evaluate the performance of these
algorithms on synthetic data. We find that our algorithm for protection level
policies performs remarkably well on most instances, even if it is not
guaranteed to be on the Pareto frontier in theory.
