📈 economics

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

This paper demonstrates that even arbitrarily weak multiplicative discounting on i.i.d. rewards can eliminate the classical $1-1/e$ advantage of the stationary setting, reducing the competitive ratio to a fundamental $1/2$ barrier that matches the difficulty of the fully non-i.i.d. case, while providing optimal threshold policies to achieve these tight bounds.

Original authors: Jung-hun Kim, Vianney Perchet

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jung-hun Kim, Vianney Perchet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a game where you have to pick the best prize from a line of boxes. You can't see what's inside the boxes until you open them one by one. Once you open a box and take the prize, the game ends. If you keep waiting, you might miss the best one. If you take a box too early, you might get something small.

This is the classic "Prophet Inequality" problem. In the ideal, boring version of this game, every box contains a prize drawn from the exact same distribution (like rolling a fair die every time). In this scenario, a smart player can guarantee getting about 63% (specifically $1 - 1/e$ ) of the value that a "Prophet" (a magical being who can see all the boxes at once) would get.

The Twist: The "Fading Prize" Game

This paper studies a slightly different, more realistic version of the game. Imagine that the prizes inside the boxes aren't just random; they are fading over time.

Box 1 has a full-sized prize.
Box 2 has a prize that is slightly smaller (maybe 90% of the original size).
Box 3 is even smaller (81% of the original), and so on.

This happens in real life: a job offer might expire, a house might get damaged by weather, or a stock might lose value as time passes. The paper asks: Does this fading make the game much harder? Can we still get that 63% guarantee?

The Big Discovery: The "Hard Mode" Trap

The authors found a surprising and somewhat scary result: Yes, it makes the game much harder.

Even if the prizes only fade by a tiny, almost unnoticeable amount, if the game goes on for a long time, the "fading" effect accumulates. The paper proves that in this long-term fading scenario, the best you can hope for drops from 63% down to 50%.

Think of it like this:

Stationary Game (No fading): You are playing against a fair opponent. You can use a simple rule: "I'll skip the first 37% of boxes, then take the next one that beats the best I've seen so far." This works great.
Fading Game: The rules of the game are secretly changing. The "best I've seen so far" is a moving target because the value of future boxes is shrinking. The paper shows that no matter how clever your rule is, if the game is long enough and the fading is real, you are forced into a situation that is just as hard as the worst-case scenario where every single box has a completely different, unpredictable value distribution. In that worst-case scenario, the best anyone can do is 50%.

The "Effective Horizon" Solution

The authors didn't just say "it's harder"; they also designed a new strategy to handle it.

They realized that because the prizes are fading, the "future" feels shorter than it actually is. It's like looking at a long road that gets foggy the further you go; the distant parts of the road don't really count as much as the near parts.

They created a concept called the "Effective Horizon."

Instead of counting the total number of boxes (say, 1,000), you calculate a "discounted" number. If the prizes fade fast, your effective horizon might feel like only 100 boxes.
Their new strategy is simple: Adjust your patience based on this "Effective Horizon." Instead of waiting for the first 37% of the actual boxes, you wait for the first 37% of the effective (faded) boxes.

By calibrating your decision to this "effective" length, they proved you can achieve the best possible score allowed by the math (the 50% barrier in the long run, or the specific number between 50% and 63% depending on how fast the prizes fade).

The "Discontinuous Breakdown"

One of the most striking findings is about the boundary between "no fading" and "fading."

If there is zero fading, you can get 100% of the Prophet's value in an infinite game (because you can just wait forever for a near-perfect prize).
The paper shows that if you introduce even the tiniest amount of fading, the guarantee instantly collapses from 100% down to 50%. It's like a light switch: a tiny crack in the wall lets the whole house fall apart.

Summary in Plain English

The Problem: We studied a game where you pick the best item from a sequence, but the items lose value over time.
The Shock: Even a tiny bit of value loss, if it happens over a long time, destroys the advantage of the "standard" game. The best performance guarantee drops from ~63% to 50%.
The Hard Truth: This 50% limit isn't just because we used a simple strategy; even a super-computer with perfect logic cannot beat this 50% limit in the long run. The problem becomes as hard as the most chaotic, unpredictable version of the game.
The Fix: The authors found a simple rule to play this game optimally: Don't count the boxes; count the "value" of the boxes. Adjust your waiting time based on how fast the prizes are fading. This "Effective Horizon" rule gets you the best possible score the math allows.

In short: Time is money, and in this game, time is also a difficulty multiplier. If you don't account for the fact that future rewards are worth less, you will lose half your potential winnings.

Technical Summary: I.i.d. Prophet Inequalities with Discounted Rewards

Problem Statement
This paper investigates prophet inequalities in a setting where the decision maker observes a sequence of non-negative random rewards that are subject to multiplicative discounting over time. While the base rewards are drawn from an independent and identically distributed (i.i.d.) distribution, the observed rewards decay as time progresses, introducing a structured form of nonstationarity. The goal is to design an online stopping rule that maximizes the expected reward relative to a "prophet" who knows all future realizations in advance. The performance is measured by the competitive ratio (CR), defined as the ratio of the gambler's expected reward to the prophet's expected maximum.

The study focuses on single-quantile threshold policies, which fix an acceptance quantile in advance and accept the first observation exceeding the corresponding quantile threshold of the current (decayed) distribution. The paper specifically addresses the transition between the classical stationary i.i.d. setting (where the optimal CR is $1 - 1/e$ ) and the fully non-i.i.d. setting (where the optimal CR degrades to $1/2$ ).

Methodology and Framework
The authors model the time horizon $n$ as being partitioned into $S$ phases. Within each phase $s$ , the observed reward $X_i$ is defined as $X_i = \Gamma_{s-1} Y_i$ , where $Y_i$ are i.i.d. samples from a base distribution $D$ , and $\Gamma_{s-1}$ represents the cumulative decay factor up to that phase.

The analysis proceeds through three primary lenses:

Canonical Setting: A symmetric case with a common decay factor $\gamma$ and equal-length phases.
General Setting: Heterogeneous decay factors and unequal phase lengths.
Infinite-Horizon Benchmark: A continuous decay model where $S = n = \infty$ .

The methodology relies on constructing "hard" instances (specific two-point distributions) to derive upper bounds on the competitive ratio for any single-threshold policy. Conversely, the authors design specific threshold algorithms calibrated to an effective horizon to establish matching lower bounds. They also utilize dynamic programming (DP) analysis to determine if the performance limits are intrinsic to the model or merely artifacts of the single-threshold restriction.

Key Contributions and Results

Fundamental Limits under Reward Decay:
The paper establishes a tight worst-case upper bound for single-quantile threshold policies in the canonical setting. The results reveal a sharp transition in performance:
- In the stationary limit ( $\gamma = 1$ ), the bound recovers the classical $1 - 1/e$ .
- As discounting accumulates over many phases (specifically in the regime where the number of phases $S \to \infty$ and the decay factor $\gamma \to 1$ such that the cumulative effect is significant), the competitive ratio collapses to a fundamental barrier of $1/2$ .
- This $1/2$ barrier matches the optimal worst-case guarantee for fully non-i.i.d. sequences, suggesting that even arbitrarily weak discounting, when accumulated over a long horizon, renders the problem as hard as the general non-i.i.d. case.
Optimality via Effective-Horizon Calibration:
The authors design a single-threshold algorithm that achieves the tight upper bounds derived above. The core insight is the effective-horizon principle: a decaying reward sequence behaves, in terms of expected maxima, like a stationary i.i.d. sequence observed over a shorter "effective horizon" $B$ , defined as the sum of the discounted masses of opportunities.
- The algorithm calibrates the acceptance quantile to $1/B$ rather than the raw horizon length $1/n$ .
- This calibration is shown to be optimal for the canonical setting and is extended to handle heterogeneous decay factors and unequal phase lengths, where the effective horizon is weighted by phase proportions and cumulative decay.
Intrinsic Limitation of the Model:
A critical contribution is the proof that the $1/2$ barrier is not an artifact of restricting the policy class to single thresholds. By analyzing the optimal dynamic programming (DP) policy, the authors show that in the boundary regime ( $S \to \infty, \gamma \to 1$ ), even the optimal stopping rule cannot exceed a competitive ratio of $1/2$ . This confirms that the difficulty arises from the structure of the discounted rewards themselves.
Infinite-Horizon Continuous Decay:
In the infinite-horizon setting with continuous decay, the paper demonstrates a discontinuous breakdown. While the stationary infinite-horizon setting allows for a competitive ratio of 1 (attainable up to $\epsilon$ ), introducing arbitrarily weak decay causes the competitive ratio to collapse immediately to $1/(1+\gamma)$ , which approaches $1/2$ as $\gamma \to 1$ . The single-threshold rule based on the effective horizon $B_\infty = 1/(1-\gamma)$ is proven to be optimal in this regime.

Significance and Claims
The paper claims that its primary significance lies in demonstrating that i.i.d. prophet inequalities with slightly discounted rewards can be as hard as the fully non-i.i.d. case.

Erasure of Stationarity Advantage: The authors argue that the classical advantage of the stationary i.i.d. setting (the $1 - 1/e$ guarantee) is fragile. Structured nonstationarity induced by discounting is sufficient to erase this advantage, driving the performance guarantee down to the fundamental $1/2$ barrier associated with arbitrary non-identical distributions.
Robustness of Single-Threshold Policies: Despite the collapse in performance guarantees, the paper shows that single-threshold policies remain the optimal strategy class. By calibrating to the effective horizon induced by discounting, these simple policies achieve the tightest possible bounds, matching the performance of optimal dynamic programming rules in the worst-case scenarios.
Theoretical Bridge: The work provides a precise characterization of the transition from stationarity to nonstationarity, isolating discounting as a mechanism that interpolates between the two extremes of prophet inequality theory.

The paper concludes that discounting alone fundamentally reshapes the achievable guarantees, transforming a problem with a known $1 - 1/e$ solution into one with a $1/2$ impossibility bound, even when the underlying base distribution remains i.i.d.

More like this