Introduction
In the field of optimal stopping theory, the Prophet Inequality has long served as a benchmark for evaluating online algorithms against an omniscient adversary. While the maximization of rewards has been extensively studied since the 1980s, the problem of cost minimization has remained "qualitatively different" and often more challenging. This paper provides a significant theoretical bridge, using Extreme Value Theory (EVT) to create a unified framework that describes the optimal performance limits for both settings through a single mathematical function.
The Prophet Inequality Problem
In a classic I.I.D. prophet inequality setting, an observer encounters a sequence of $n$ independent and identically distributed random variables. At each step, the observer must decide whether to accept the current value or discard it forever. The goal is to compete with a "prophet" who knows all values in advance and selects the absolute best (maximum reward or minimum cost).
For maximization, it is well-established that an algorithm can always achieve at least $\approx 0.745$ of the prophet's expected value. Conversely, minimization is often harder; the competitive ratio—the ratio of the algorithm's expected cost to the prophet's—can be unbounded for many distributions. This research addresses the lack of a unified theory explaining the relationship between these two objectives.
Methodology: The EVT Lens
The authors leverage the Fisher-Tippett-Gnedenko Theorem from Extreme Value Theory to analyze the limiting distributions of extrema. They categorize distributions based on their Extreme Value Index ($\gamma$):
- Fréchet ($\gamma > 0$): Heavy-tailed distributions.
- Gumbel ($\gamma = 0$): Distributions like Exponential or Normal.
- Reverse Weibull ($\gamma < 0$): Distributions with finite upper bounds.
By applying Karamata’s theory of regular variation, the researchers focus on the Asymptotic Competitive Ratio (ACR) as the number of samples $n$ approaches infinity, providing a "large market" analysis of these stopping problems.
A Unified Framework
The most striking discovery of this work is that the performance of optimal threshold algorithms for both maximization and minimization is governed by the same function, $\Lambda(\gamma)$:
$$\Lambda(\gamma) = \frac{(1-\gamma)^{-\gamma}}{\Gamma(1-\gamma)}$$
As shown in the figure, the competitive ratio for maximization is defined by $\min\{\Lambda(\gamma), 1\}$, while for minimization, it is $\max\{\Lambda(\gamma), 1\}$. This reveals a fundamental symmetry: maximization and minimization are two sides of the same mathematical coin, separated primarily by the sign of the extreme value index $\gamma$.
Key Insights and Results
- Closed-Form Characterization: The paper provides the first elegant, closed-form characterization of the ACR for I.I.D. minimization.
- The Hardness of Minimization: The framework explains why minimization is difficult. For distributions with very negative $\gamma$, $\Lambda(\gamma)$ grows exponentially, leading to poor competitive ratios.
- MHR Distributions: Monotone Hazard Rate (MHR) distributions are shown to be well-behaved because their indices fall within ranges ($\gamma \le 0$ for max, $\gamma \ge -1$ for min) that yield constant competitive ratios.
- Multi-Unit Selection: In settings where $k$ items must be selected, the authors prove that if $k \ge \log n$, even simple single-threshold algorithms can achieve a constant competitive ratio for minimization.
Conclusion
By unifying maximization and minimization under the umbrella of Extreme Value Theory, this research provides a powerful tool for understanding optimal stopping. While the current focus is asymptotic, the results offer a definitive map of the performance limits in large-scale online selection problems. Future work may extend this EVT lens to non-I.I.D. settings or more complex combinatorial constraints.
Summary updated