When opportunities lose value, a simple rule measures how long to wait

Choosing an opportunity means giving up the chance to choose a better one later. Waiting has another cost when later opportunities are worth less. In a mathematical preprint, Jung-hun Kim and Vianney Perchet study this tension and identify a simple way to set a selection threshold: count future opportunities according to their discounted value, rather than treating every chance equally.

Their paper, Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards, examines a theoretical benchmark called a prophet inequality. A decision-maker sees random rewards one at a time and can accept only one, without returning to rejected offers. An imaginary prophet sees the entire sequence and takes its maximum. The comparison concerns their expected rewards, not a promise about what happens in every individual sequence.

One distribution, shrinking rewards

The model starts with independent draws from the same known distribution of nonnegative rewards, with finite positive mean. Time is divided into phases. Within each phase, rewards have the same scale; between phases, a known multiplier can reduce that scale. Both the phase lengths and discounts are known in advance.

The main analysis uses equal-length phases and a common multiplier between consecutive phases. This isolates the effect of accumulated discounting without also changing the underlying distribution of opportunities.

The authors distinguish two deceptively similar strategies. A fixed-value threshold accepts the first observed reward above one unchanged amount. A single-quantile policy instead targets the same upper fraction of the reward distribution throughout. Its monetary threshold falls alongside the reward scale. It therefore remains equally selective relative to each phase’s distribution, even as the amounts shrink.

Counting discounted chances

The central quantity is an “effective horizon,” called B. It is the sum, over all observations, of their discount weights. Equivalently, multiply each phase’s length by its cumulative reward multiplier and add the results. Without discounting, B equals the actual number of observations.

The proposed rule chooses a threshold that each new draw meets with probability 1/B, conditional on the process reaching that draw. It accepts the first qualifying reward. When the distribution has a probability mass exactly at the threshold, randomized acceptance of ties supplies the required probability.

Only that target probability is determined by the phase profile alone. Converting it into an actual reward threshold still requires knowing the base distribution.

To justify the calibration, the authors prove that the discounted prophet’s expected reward is bounded above by a stationary benchmark with effective horizon B. For integer B, this benchmark is the expected maximum of B independent base rewards. For noninteger B, they define a mathematical extension using the distribution function. The comparison is an inequality between expected maxima, not a claim that discounting literally removes observations.

What the guarantees mean

For a fixed number of equal-length phases and a fixed common discount multiplier, the authors derive matching upper and lower bounds as the number of observations grows. The 1/B rule attains the best worst-case guarantee among single-quantile policies, even when competing policies can choose their acceptance probability using the known distribution.

With no discounting, the guarantee is 1 − 1/e, approximately 63.2% of the prophet’s expected reward. This is the benchmark for the restricted policy class, not for every possible stopping strategy. If the multiplier is zero, only the first phase matters, recovering the same asymptotic benchmark.

The difficult regime lies between those endpoints. As the number of phases grows and each phase-to-phase multiplier approaches one, while the cumulative multiplier across all phases approaches zero, the guarantee approaches one-half. Small individual discounts can therefore create a substantial overall loss.

Using rare, very large rewards mixed with a common smaller reward, the authors also bound the performance of the optimal dynamic-programming strategy. This establishes that the same limiting one-half barrier applies to arbitrary stopping rules in that regime, rather than merely exposing a weakness of the simple policy.

Extensions and limits

The comparison extends to unequal phase lengths and heterogeneous discounts. The accompanying sharpness result has a narrower scope: acceptance probabilities determined by the phase profile, independently of the base distribution.

For an infinite sequence discounted by a factor gamma at every observation, the calibration becomes acceptance probability 1 − gamma. It attains the known optimal worst-case ratio 1/(1 + gamma), established by Boshuizen in 1994. The contribution here is an explicit quantile calibration, not discovery of that ratio or optimality for every individual distribution.

The paper reports numerical illustrations with 100,000 observations, but its guarantees rest on proofs under the stated assumptions, not real-world trials. This report uses the extracted text of arXiv version 2, revised November 6, 2026. The work remains a preprint; PDF text extraction may omit figures and damage mathematical layout.