Online Resource Allocation Under Partially Predictable Demand

Dawsen Hwang, Patrick Jaillet, Vahideh Manshadi

Introduction

In the domain of online resource allocation—ranging from airline ticket sales to real-time internet advertising—decision-makers must accept or reject incoming requests without knowing future demand. Historically, this problem has been analyzed through two extreme lenses: adversarial models, which assume worst-case scenarios and lead to conservative strategies, and stochastic models, which assume predictable distributions and can fail during unexpected traffic spikes.

This research introduces a "partially predictable" demand model that bridges this gap. By assuming that a fraction $p$ of customers arrive according to a random permutation while the remaining $1-p$ fraction is controlled by an adversary, the authors develop algorithms that are robust yet capable of capitalizing on predictable demand patterns. This model provides a more realistic framework for firms that face a mix of regular, predictable traffic and unpredictable strategic behavior.

The Hybrid Arrival Model

The authors propose a model where an adversary selects a sequence of $n$ customers. These customers are categorized into two types: Type 1 (high value, revenue = 1) and Type 2 (low value, revenue = $a < 1$). The arrival order is a mixture:

  • Stochastic Group: A fraction $p$ of the customers are randomly permuted across the time horizon.
  • Adversarial Group: The remaining $1-p$ fraction arrive in an order determined by the adversary.

The algorithm must make irrevocable decisions without knowing which group a specific customer belongs to, creating a challenge that requires balancing immediate revenue against the risk of future inventory depletion.

Algorithmic Strategies

The research presents two primary algorithmic frameworks to address this hybrid demand:

1. Non-Adaptive Thresholding (Algorithm 1)

This approach utilizes predetermined dynamic thresholds. It combines an evolving threshold—designed to accept low-value customers at a steady rate by exploiting the uniform distribution of the stochastic group—with a fixed threshold that protects against adversarial "front-loading" of low-value requests. This dual-threshold strategy ensures that the algorithm remains robust against adversarial manipulation while still capturing revenue from the predictable portion of the stream.

2. Adaptive Estimation (Algorithm 2)

The adaptive algorithm continuously updates upper bounds on the total number of high- and low-value customers based on observed data. By dynamically adjusting the acceptance threshold for low-value customers in real-time, it can achieve higher efficiency, provided there is sufficient initial inventory ($b$).

Key Insights and Theoretical Results

The study demonstrates that predictability directly scales with performance. The competitive ratio—the ratio of the algorithm's revenue to the offline optimal—increases linearly with the fraction $p$ of predictable demand. This proves that even limited stochastic information can be leveraged to significantly boost revenue.

Competitive Ratio Guarantees

Algorithm 1 achieves a competitive ratio of approximately $p + \frac{1-p}{2-a}$. This result is significant because it perfectly interpolates between the known optimal ratios for purely adversarial ($p=0$) and purely random-order ($p=1$) models.

The Role of Inventory and Adaptivity

A critical finding is that adaptivity requires a "buffer." The adaptive algorithm (Algorithm 2) strictly outperforms the non-adaptive version when inventory scales linearly with the time horizon ($b = \kappa n$). For instance, with $a=0.7$, $b=0.7n$, and $p=0.2$, the adaptive approach can yield 10% more revenue than its non-adaptive counterpart. However, if inventory is small ($b = o(\sqrt{n})$), the authors prove that no online algorithm can surpass the non-adaptive competitive ratio, as the adversary can exhaust resources before the algorithm has time to learn from the arrival pattern.

Extension: The Secretary Problem

The authors also apply this model to the classic Secretary Problem, where the goal is to select the single best candidate from a sequence. They find that while a deterministic observation period (skipping the first $1/e$ fraction) is optimal in purely stochastic settings, the presence of an adversarial component ($p < 1$) makes randomizing the length of the observation period a superior strategy for maximizing the probability of success.

Conclusion and Future Directions

This work provides a robust mathematical framework for online allocation in environments that are neither purely random nor entirely hostile. The authors demonstrate that the "cost" of making online decisions decreases as the predictability of the environment increases. While the current model focuses on two customer types and specific inventory scaling, future research could extend these results to handle multiple customer types and continuous-time Poisson arrival processes.

Summary updated

Abstract

For online resource allocation problems, we propose a new demand arrival model where the sequence of arrivals contains both an adversarial component and a stochastic one. Our model requires no demand forecasting; however, due to the presence of the stochastic component, we can partially predict future demand as the sequence of arrivals unfolds. Under the proposed model, we study the problem of the online allocation of a single resource to two types of customers, and design online algorithms that outperform existing ones. Our algorithms are adjustable to the relative size of the stochastic component, and our analysis reveals that as the portion of the stochastic component grows, the loss due to making online decisions decreases. This highlights the value of (even partial) predictability in online resource allocation. We impose no conditions on how the resource capacity scales with the maximum number of customers. However, we show that using an adaptive algorithm---which makes online decisions based on observed data---is particularly beneficial when capacity scales linearly with the number of customers. Our work serves as a first step in bridging the long-standing gap between the two well-studied approaches to the design and analysis of online algorithms based on (1) adversarial models and (2) stochastic ones. Using novel algorithm design, we demonstrate that even if the arrival sequence contains an adversarial component, we can take advantage of the limited information that the data reveals to improve allocation decisions. We also study the classical secretary problem under our proposed arrival model, and we show that randomizing over multiple stopping rules may increase the probability of success.
BibTeX
@misc{hwang2018online,
  author = {Dawsen Hwang and Patrick Jaillet and Vahideh Manshadi},
  title = {{Online Resource Allocation Under Partially Predictable Demand}},
  year = {2018},
  eprint = {1810.00447},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.00447},
}
Figure