I.i.d. Prophet Inequalities with Discounted Rewards: As Hard as the Non-i.i.d. Case

Jung-hun Kim, Vianney Perchet · 2026

Read I.i.d. Prophet Inequalities with Discounted Rewards: As Hard as the Non-i.i.d. Case by Jung-hun Kim, Vianney Perchet (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30118.txt.

Introduction

Jung-hun Kim and Vianney Perchet show that discounting future rewards quietly destroys a classic guarantee in online decision making. Prophet inequalities compare a gambler's stopping rule against an all-knowing prophet. With stationary identical rewards, the gambler can guarantee a known fraction. That fraction beats the harder non-identical case by a clear margin. Multiplicative discounting over time erodes the advantage.

Even identical base rewards become as hard as the non-identical case. The competitive ratio collapses from the classical guarantee to a one-half barrier. This happens as discounting accumulates over many equal phases. The barrier persists for arbitrary stopping rules, not just thresholds. Single-quantile threshold rules can still attain the tight bounds available. Their calibration uses an effective horizon induced by the discounting. Heterogeneous decay factors and unequal phase lengths are also handled. A continuous-decay benchmark shows the same discontinuous breakdown.

Catalog record

CREATORJung-hun Kim, Vianney Perchet
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE131 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.30118

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

I.i.d. Prophet Inequalities with Discounted Rewards: As Hard as the Non-i.i.d. Case 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 1-1/e guarantee to a fundamental 1 / 2 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 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 1 to 1 / 2 1/2 . 1 Introduction Prophet inequalities constitute a fundamental class of problems in online optimal stopping ( 16 ) . A decision maker (the “gambler”) sequentially observes a stream of non-negative random variables (the “rewards”), revealed one at a time, and must decide at each stage whether to accept the current reward and stop or to continue observing future rewards . Performance is benchmarked against a prophet , an omniscient agent who observes all realizations in advance and can always select the maximum reward. The goal of the gambler is to design an online stopping rule whose expected payoff is competitive with that of the prophet, typically measured through the competitive ratio. Owing to their rich mathematical structure and practical relevance, prophet inequalities have been extensively studied ( 9 ) and have found applications in areas such as posted-price mechanisms ( 18 ) , online advertisement allocation ( 2 ) , and hiring processes in labor markets ( 5 ) . The prophet-inequalities literature has established tight constant-factor guarantees. On one side, in stationary i.i.d. reward settings, the classical 1-1/e competitive-ratio bound is known to be tight for a class of single-threshold policies ( 9 ; 8 ) . On the other side, for independent but non-identically distributed (non-i.i.d.) reward sequences, the optimal competitive ratio degrades to 1/2 , as shown by 21 . Despite this extensive literature, existing results largely focus on these two extreme endpoints and have not addressed structured forms of nonstationarity that interpolate between them. We study a natural mechanism to bridge between the stationary i.i.d. and fully non-i.i.d. settings: rewards are discounted with time, i.e., the scale of the reward distribution decreases over time. This framework isolates a discounting-induced transition from stationarity to nonstationarity, allowing a precise characterization of how classical guarantees break down. In particular, we show that even arbitrarily small discounting, when accumulated over long horizons, rules out any competitive ratio exceeding 1/2 , matching the worst-case guarantee in the non-i.i.d. setting. In other words, i.i.d. prophet inequalities with slightly discounted rewards are as hard as the non-i.i.d. case. Beyond its theoretical interest, reward decay arises naturally in many practical environments where opportunities deteriorate over time due to time preferences, depreciation, congestion effects, or market saturation ( 11 ; 12 ; 22 ; 20 ; 7 ) . We shall focus on single-quantile threshold stopping policies. Such a policy fixes an acceptance quantile in advance and accepts the first observation whose value exceeds the corresponding quantile threshold of the current reward distribution. In the stationary i.i.d. setting, this is equivalent, up to tie-breaking, to using a fixed value threshold. Under reward decay, however, fixed-value and fixed-quantile thresholds no longer coincide. We formulate our policies in terms of a fixed acceptance quantile, and refer to them as single-threshold policies throughout. Threshold policies are a cornerstone of prophet inequalities due to their simplicity and sharp guarantees. In the stationary i.i.d. setting, single-threshold policies achieve the classical 1-1/e guarantee, which is tight within that policy class ( 8 ; 9 ) . In the independent non-i.i.d. setting, a fixed value-threshold rule attains the optimal worst-case competitive ratio 1/2 ( 21 ) (see also 10 ; 14 ). From an economic perspective, single-threshold stopping rules naturally correspond to standard posted-price mechanisms ( 4 ) , in which the decision maker commits to a fixed acceptance rule in advance. Such mechanisms are appealing due to their single-parameter structure, which reduces approximation to choosing a single price and yields transparent and tractable policies ( 19 ) . As a consequence, we will study the performance of the single-threshold policies under decaying rewards and characterize their achievable competitive ratios, to answer the following natural question: To what extent do single-threshold policies retain their classical performance guarantees under decaying rewards? We tackle this question by identifying the fundamental performance limits and designing single-threshold algorithms that match these limits in this setting. Our main contributions are the following. • Fundamental limits under reward decay. We derive a tight worst-case upper bound for single-quantile threshold policies under decaying rewards for a common decay factor and equal-length phases. These bounds reveal a sharp transition from the classical 1-1/e guarantee to a worst-case 1/2 barrier in the boundary regime between stationarity and discounting. This 1/2 barrier is worst-case optimal, matching the classical non-i.i.d. impossibility bound. We also show that the 1/2 barrier is not an artifact of single-threshold policies: any arbitrary stopping rules face the same worst-case barrier. • Single-threshold optimality via an effective-horizon principle. We design single-threshold algorithms that match the above upper bound for a common decay factor with equal-length phases. The key insight is an effective-horizon principle: at the level of the prophet benchmark (expected maxima), a decaying reward sequence behaves like a stationary i.i.d. sequence observed over a shorter horizon. Calibrating the acceptance quantile to this effective horizon yields tight guarantees. The same calibration extends to heterogeneous decay factors and unequal phase lengths. • Infinite-horizon continuous-decay benchmark. As a clean benchmark for the long-run effect of discounting, we study an infinite-horizon model with continuously decaying rewards. This benchmark reveals a sharp discontinuity: while the stationary infinite-horizon setting admits a trivial competitive ratio of 1 , introducing arbitrarily weak decay induces a sharp breakdown, yielding a worst-case competitive ratio of 1/2 . Moreover, we prove that our single-threshold rule is optimal in this benchmark and achieves this bound. 2 Related Work The study of prophet inequalities dates back to the seminal work of 17 . Subsequent work established sharp constant-factor benchmarks in the independent non-i.i.d. and stationary i.i.d. settings. In the independent but non-identically distributed (non-i.i.d.) case, 21 showed that a threshold stopping rule attains the optimal competitive ratio of 1/2 . In the i.i.d. setting, 15 established a competitive ratio of at least 1-1/e , later reinterpreted in algorithmic terms as a single-quantile threshold policy that accepts the first observation exceeding a suitable quantile ( 9 ; 10 ; 14 ) . Beyond single-threshold policies,

Read the complete text