When Should you Offer an Upgrade: Online Upgrading Mechanisms for Resource Allocation

Patrick Jaillet, Chara Podimata, Andrew Vakhutinsky, Zijie ZhouarXiv 2024 · DOI · arXiv

TL;DR

This paper introduces DynUp, a novel online mechanism for resource allocation that dynamically offers "upgrades-for-a-fee" to maximize revenue and minimize underutilization. The authors prove that their algorithm achieves near-optimal $O(\log T)$ regret and demonstrate through hospitality industry simulations that it could boost annual revenue by over 17%.

What Problem Does This Paper Address?

In industries like hospitality and aviation, suppliers face a classic "perishable inventory" problem: a hotel room or airplane seat not sold today is lost revenue forever. While demand fluctuates, capacity is fixed. This often leads to "premium" resources (like suites or first-class seats) sitting empty while "basic" resources are overbooked.

Existing literature often suggests offering free upgrades to fill these gaps. However, in the real world, upgrades usually come at a price. The challenge for a supplier is deciding when to offer an upgrade and how much to charge. If the fee is too high, the customer rejects it and the premium resource remains empty. If it's too low, the supplier might "cannibalize" a premium resource that a high-paying customer would have bought later. This paper tackles this sequential decision-making problem under uncertainty, where the supplier lacks foresight into future demand.

Methods

The authors propose a mechanism called DynUp (Dynamic Upgrading). The core of their approach involves:

  1. Hybrid Programming (HP): To measure performance, the authors define a new benchmark called "hybrid programming." This approach interpolates between a deterministic model (common in price-based revenue management) and a hindsight optimum (common in quantity-based models). It provides a theoretical upper bound on the expected revenue any algorithm could achieve.
  2. DynUp-2 Algorithm: For the case of two resource types (Basic and Premium), the algorithm solves the HP problem at each time step using the remaining inventory and expected future demand. Despite the underlying optimization problem being non-convex, the authors derive a closed-form solution for the optimal upgrade price.
  3. DynUp-n Algorithm: To handle $n$ resource types, the authors show that the problem can be decomposed into $n-1$ parallel "2-type" problems. This allows the algorithm to scale efficiently as the number of resource categories increases.
  4. Regret Analysis: The authors use martingale theory to prove that the difference between the revenue of a hindsight-optimal strategy and DynUp (the "regret") grows only logarithmically with time ($O(\log T)$), which is a hallmark of highly efficient online algorithms.

Datasets

The authors evaluated their algorithm using a real-world dataset from the hospitality industry:

  • Scope: 13,155 upgrade offers recorded over one year.
  • Attributes: The data included initial payment, room categories (from/to), the upgrade price offered, and the customer's final decision (accept/reject).
  • Modeling: They used this data to perform a regression analysis, fitting a parametric exponential decay function ($f(v) = e^{-av^b}$) to model the probability of a customer accepting an upgrade fee.
  • Simulation: They simulated daily reservations for a hotel with three room categories (inventories of 60, 30, and 2) to compare DynUp against standard industry benchmarks.

Key Insights and Ideas

  • The Power of the Fee: Moving from "free upgrades" to "upgrades-for-a-fee" significantly complicates the math but offers a much more realistic and lucrative path for revenue management.
  • Inventory Protection: A key part of the algorithm is "protecting" premium inventory. It calculates exactly how many premium units should be reserved for future high-tier requests versus how many can be safely used for upgrades today.
  • Smooth Phase Transitions: The authors proved that the decision-making process remains "smooth" even as resources are depleted. By constructing a specific martingale, they showed that the algorithm's pricing decisions stay close to the theoretical optimum even when inventory is critically low.
  • Decomposition: The discovery that an $n$-tier upgrade system can be treated as a series of independent 2-tier problems is a major simplification that makes the algorithm practical for complex real-world systems.

Key Results

  • Theoretical Efficiency: The algorithm achieves $O(n \log T)$ regret, meaning its performance gap compared to an omniscient strategy grows very slowly over time.
  • Revenue Boost: In simulations using real hospitality data, DynUp increased annual revenue by 17.07% compared to a standard first-come, first-served benchmark.
  • High-Demand Performance: The benefits were even more pronounced during peak periods. In the high-demand month of November, the algorithm increased revenue by over 26%.

Limitations and Future Work

  • Known Likelihood Functions: The current model assumes the supplier already knows the function $f(u)$ (the probability a customer accepts a specific fee). In practice, this must be learned. The authors suggest "blind" online learning of these functions as a vital next step.
  • Customer Loyalty and Fairness: The mechanism treats every request independently. It does not account for long-term customer loyalty or the potential "unfairness" of offering different upgrade prices to different customers for the same room.
  • Multi-Night Stays: The empirical study focused on single-night stays. Extending the logic to multi-night bookings—where a single upgrade affects inventory across a range of dates—presents a significant combinatorial challenge.

Summary updated

Abstract

In this work, we study an upgrading scheme for online resource allocation problems. We work in a sequential setting, where at each round a request for a resource arrives and the decision-maker has to decide whether to accept it (and thus, offer the resource) or reject it. The resources are ordered in terms of their value. If the decision-maker decides to accept the request, they can offer an upgrade-for-a-fee to the next more valuable resource. This fee is dynamically decided based on the currently available resources. After the upgrade-for-a-fee option is presented to the requester, they can either accept it, get upgraded, and pay the additional fee, or reject it and maintain their originally allocated resource. We take the perspective of the decision-maker and wish to design upgrading mechanisms in a way that simultaneously maximizes revenue and minimizes underutilization of resources. Both of these desiderata are encapsulated in a notion of regret that we define, and according to which we measure our algorithms' performance. We present a fast algorithm that achieves O(log T) regret. Finally, we implemented our algorithm utilizing data akin to those observed in the hospitality industry and estimated our upgrading mechanism would increase the annual revenue by over 17%.
BibTeX
@misc{jaillet2024when,
  author = {Patrick Jaillet and Chara Podimata and Andrew Vakhutinsky and Zijie Zhou},
  title = {{When Should you Offer an Upgrade: Online Upgrading Mechanisms for Resource Allocation}},
  year = {2024},
  eprint = {2402.08804},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.08804},
}
Figure