Risk of Bad Tails: CVaR-Aware Pandora's Box and Prophet Inequality
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911696743825408 |
|---|---|
| author | Ji, Jingwei |
| author_facet | Ji, Jingwei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_19181 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Risk of Bad Tails: CVaR-Aware Pandora's Box and Prophet Inequality Ji, Jingwei Computational Complexity 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. |
| title | Risk of Bad Tails: CVaR-Aware Pandora's Box and Prophet Inequality |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2605.19181 |