Minimization I.I.D. Prophet Inequality via Extreme Value Theory: A Unified Approach

Vasilis Livanos, Ruta Mehta

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)}$$

The function $\Lambda(\gamma)$ characterizes the asymptotic competitive ratio for both maximization and minimization problems across different extreme value domains.

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

Abstract

The I.I.D. Prophet Inequality is a fundamental problem where, given $n$ independent random variables $X_1,\dots,X_n$ drawn from a known distribution $\mathcal{D}$, one has to decide at every step $i$ whether to stop and accept $X_i$ or discard it forever and continue. The goal is to maximize or minimize the selected value and compete against the all-knowing prophet. For maximization, a tight constant-competitive guarantee of $\approx 0.745$ is well-known (Correa et al, 2019), whereas minimization is qualitatively different: the optimal constant is distribution-dependent and can be arbitrarily large (Livanos and Mehta, 2024). In this paper, we provide a novel framework via the lens of Extreme Value Theory to analyze optimal threshold algorithms. We show that the competitive ratio for the minimization setting has a closed form described by a function $\Lambda$, which depends only on the extreme value index $\gamma$; in particular, it corresponds to $\Lambda(\gamma)$ for $\gamma \leq 0$. Despite the contrast of maximization and minimization, our framework turns out to be universal and we recover the results of (Kennedy and Kertz, 1991) for maximization as well. Surprisingly, the optimal competitive ratio for maximization is given by the same function $\Lambda(\gamma)$, but for $\gamma \geq 0$. Along the way, we obtain several results on the algorithm and the prophet's objectives from the perspective of extreme value theory, which might be of independent interest. We next study single-threshold algorithms for minimization. Using extreme value theory, we generalize the results of (Livanos and Mehta, 2024) which hold only for special classes of distributions, and obtain poly-logarithmic in $n$ guarantees. Finally, we consider the $k$-multi-unit prophet inequality for minimization and show that there exist constant-competitive single-threshold algorithms when $k \geq \log{n}$.
BibTeX
@inproceedings{livanos2025minimization,
  author = {Vasilis Livanos and Ruta Mehta},
  title = {{Minimization I.I.D. Prophet Inequality via Extreme Value Theory: A Unified Approach}},
  booktitle = {EC},
  year = {2025},
  doi = {10.1145/3736252.3742682},
}
Figure