I.i.d. Prophet Inequalities with Discounted Rewards: As Hard as the Non-i.i.d. Case
2026-06-29 • Computer Science and Game Theory
Computer Science and Game TheoryDiscrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors study a problem where rewards that are the same and independent over time get smaller as time passes. They find that even a tiny decrease in rewards over time removes the usual advantage that comes from rewards being the same each time. Their results show that when rewards are discounted, simple strategies that work great in the usual setting only guarantee about half the reward compared to the best possible. They also develop strategies that work well under these conditions and show that this difficulty remains even in a continuous, infinite timeframe.
prophet inequalitiesdiscounted rewardsi.i.d. (independent and identically distributed)competitive ratiosingle-quantile threshold policynonstationaritystopping rulesdecay factorinfinite horizoncontinuous decay
Authors
Jung-hun Kim, Vianney Perchet
Abstract
We study prophet inequalities with discounted rewards, where i.i.d. base rewards are multiplicatively discounted over time. Our main message is that even this structured and arbitrarily weak form of nonstationarity can erase the classical advantage of the stationary i.i.d. setting. Focusing on single-quantile threshold policies, we show that the competitive ratio transitions from the classical $1-1/e$ guarantee to a fundamental $1/2$ barrier as discounting accumulates over many phases in a canonical regime with a common-decay factor and equal-length phases. We further show that, in the same regime, the $1/2$ barrier persists even for arbitrary stopping rules. Consequently, i.i.d. base rewards under discounting can be as hard as the fully non-i.i.d. case. On the algorithmic side, we design single-quantile threshold rules that attain the tight bounds by calibrating acceptance decisions to an effective horizon induced by discounting, and we extend this calibration to heterogeneous decay factors and unequal phase lengths. We further show that a similar discontinuous breakdown persists in an infinite-horizon continuous-decay benchmark, where arbitrarily weak decay collapses the stationary benchmark from $1$ to $1/2$.