Risk of Bad Tails: CVaR-Aware Pandora's Box and Prophet Inequality
For researchers in sequential decision-making under risk, this work reveals fundamental limitations of CVaR objectives in prophet inequalities and provides a positive result under distributional assumptions.
The paper studies CVaR-aware variants of Pandora's box and the prophet inequality, finding that Pandora's box retains an index solution while the prophet inequality has no constant approximation guarantee without distributional structure, but under an IFRA condition a threshold policy achieves an explicit constant bound.
We study Conditional Value-at-Risk (CVaR) variants of two canonical sequential decision problems: Pandora's box and the prophet inequality. For Pandora's box, the risk-aware problem retains an exact Weitzman-style index solution after a one-dimensional variational reduction. For the prophet inequality, the picture is different: for every CVaR level $α\in(0,1)$, no positive constant approximation guarantee can hold without distributional structure, in sharp contrast with the risk-neutral case $α=1$, and we characterize the tight instance-dependent guarantee. Already in two-item hard instances, the prophet's CVaR benchmark can be made arbitrarily large while every online policy's CVaR remains bounded. This impossibility is due to the nature of CVaR objective: it measures only the worst $α$-fraction of outcomes, so any compromise an online policy makes to preserve the chance of a large payoff in the upper $(1-α)$-fraction does not help its CVaR. It turns out that additional distributional structure restores a uniform result: under continuous reward distributions satisfying a recentered increasing-failure-rate-average (IFRA) condition, a threshold policy achieves an explicit constant bound.