Risk of Bad Tails: CVaR-Aware Pandora's Box and Prophet Inequalities

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 elegant Weitzman-style index solution after a one-dimensional variational reduction. For the prophet inequality, the picture is different: for every CVaR level $\alpha \in (0,1)$, no positive constant approximation guarantee can hold without additional distributional structure, in sharp contrast with the risk-neutral case $\alpha =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 relatively bounded. This impossibility is due to the nature of CVaR objective: it measures only the worst $\alpha$-fraction of outcomes, so any compromise an online policy makes to preserve the chance of a large payoff in the upper $(1-\alpha )$-fraction might not help its CVaR. It turns out that some additional distributional structure restores a uniform result: under continuous reward distributions satisfying an increasing-failure-rate-average (IFRA) condition, a threshold policy achieves an explicit constant bound.