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