AI summaryⓘ
The authors study prophet inequalities, which help evaluate decision-making algorithms, but in scenarios where inputs are correlated through a hidden variable Z. They explore two models: one where each input is shifted by Z (common-base) and another where inputs are scaled by Z (common-scale). For the common-base model, they analyze algorithms that accept the last item and find the best competitive ratios achievable, showing these are below the classic 1/2 ratio known for independent inputs. They develop a new mathematical approach using differential equations to describe these outcomes. In the common-scale model, they prove that strong correlations make it nearly impossible for any algorithm to perform well, limiting success to a ratio no better than 1 divided by the number of items.
Prophet inequalitiesOnline algorithmsCorrelated inputsCommon-base modelCommon-scale modelCompetitive ratioSingle-threshold algorithmsDifferential equationsMinimax argumentAdversarial choice
Authors
José Correa, Maximilian Fichtl, Reda Jlibene, Rida Laraki, Vasilis Livanos, Kevin Schewior, Victor Verdugo
Abstract
Prophet inequalities have become a central tool for analyzing the performance of online algorithms. However, most existing results assume that input random variables are independent, which limits their applicability. Motivated by this gap, we study prophet inequalities under two correlation models induced by a latent state of the world variable $Z$. In the common-base model, the algorithm observes the sequence $Z+X_1,\dots,Z+X_n$. We analyze single-threshold algorithms with the constraint that they always accept the final item, guaranteeing a reward of at least $Z$. When $Z$ is chosen adversarially, we characterize the optimal deterministic algorithm of this form, achieving a competitive ratio of $0.381$. We then show that randomizing improves the guarantee to $0.4$. By a minimax argument, the same ratio is achievable when $Z$ is random. We depart from standard techniques by establishing a stronger lower bound of $0.41$ and an upper bound of $0.475$, ruling out the possibility that this class of algorithms attains the $1/2$ ratio known for independent inputs. The core technical contribution is a new analytical framework that captures the reward dynamics of single-threshold algorithms. We introduce a differential equation characterizing the expected reward of a threshold in the worst-case instance, parameterized by the distribution of the maximum. This equation admits a closed-form and unifies known single-threshold prophet inequalities, yielding a simple threshold-optimality condition applicable to the common-base model. Finally, we study the common-scale model, where inputs take the form $Z\cdot X_1,\dots,Z\cdot X_n$. We show that this minimal multiplicative correlation yields strong impossibility results: no algorithm can achieve a competitive ratio exceeding $1/n$.