pith. sign in

arxiv: 2606.30118 · v1 · pith:URT6ZLX2new · submitted 2026-06-29 · 💻 cs.GT · cs.DM· cs.DS· econ.TH· math.OC

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

Jung-hun Kim , Vianney Perchet This is my paper

Pith reviewed 2026-06-30 04:09 UTC · model grok-4.3

classification 💻 cs.GT cs.DMcs.DSecon.THmath.OC
keywords prophet inequalitiesdiscounted rewardscompetitive ratioi.i.d. vs non-i.i.d.threshold policiesstopping rulesonline algorithms
0
0 comments X

The pith

Discounted i.i.d. rewards in prophet inequalities reach a 1/2 competitive ratio barrier matching the non-i.i.d. case.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies prophet inequalities where base rewards are i.i.d. but then multiplicatively discounted over time. It shows that this form of nonstationarity removes the classical i.i.d. advantage, driving the competitive ratio down to 1/2. Focusing on single-quantile threshold policies, the ratio transitions from the usual 1-1/e to 1/2 as discounting accumulates across many phases in a regime with common decay and equal phases. The same 1/2 limit holds for any stopping rule, so the discounted i.i.d. setting is as hard as the fully non-i.i.d. setting. The authors supply threshold rules that meet the bound by adjusting to the discounting-induced effective horizon and extend the calibration to heterogeneous decays.

Core claim

In prophet inequalities with multiplicatively discounted i.i.d. rewards, under a canonical regime of common decay factor and equal-length phases, the competitive ratio for single-quantile threshold policies drops to a 1/2 barrier as discounting accumulates; the same barrier holds for arbitrary stopping rules, so i.i.d. base rewards under discounting are as hard as the non-i.i.d. case. Single-quantile policies achieve the tight bound by calibrating acceptance to the effective horizon from discounting. A similar discontinuous drop from 1 to 1/2 occurs in an infinite-horizon continuous-decay benchmark under arbitrarily weak decay.

What carries the argument

Single-quantile threshold policies calibrated to the effective horizon induced by discounting, within a regime of common decay factor and equal phase lengths.

If this is right

  • The classical 1-1/e guarantee for i.i.d. prophet inequalities no longer applies once discounting is present.
  • Arbitrary stopping rules cannot beat the 1/2 ratio in the canonical regime.
  • Single-quantile threshold policies attain the tight 1/2 bound after calibration to the discounting horizon.
  • The breakdown extends to heterogeneous decay factors and unequal phase lengths.
  • In infinite-horizon continuous decay, even arbitrarily weak decay forces the ratio to 1/2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Discounting may create similar hardness in other online selection or stopping problems that currently rely on i.i.d. assumptions.
  • The result suggests examining whether time-dependent scaling factors in general online algorithms produce abrupt drops in performance.
  • Numerical checks with moderate numbers of phases and varying decay rates could confirm how quickly the ratio approaches 1/2.
  • The canonical regime may serve as a worst-case template for designing robust policies under mild nonstationarity.

Load-bearing premise

The 1/2 barrier and matching algorithms are derived under a canonical regime with a common-decay factor and equal-length phases.

What would settle it

An explicit stopping rule achieving strictly better than 1/2 competitive ratio against i.i.d. base rewards under the canonical discounting regime with many phases would falsify the claim.

Figures

Figures reproduced from arXiv: 2606.30118 by Jung-Hun Kim, Vianney Perchet.

Figure 1
Figure 1. Figure 1: Upper bound on the competitive ratio as a function of the decay factor. [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Competitive ratio versus decay factor γe. 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.90 0.99 0.0 0.2 0.4 0.6 0.8 1.0 C o m p e titiv e R a tio Competitive Ratio vs (S=100000) Algorithm 1 Theoretical asymptotic bound (c) S = n = 100000 [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Competitive ratio versus the decay factor [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
read the original 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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies prophet inequalities where base rewards are i.i.d. but subject to multiplicative discounting over time. Focusing on single-quantile threshold policies, it establishes that the competitive ratio transitions from the classical 1-1/e to a 1/2 barrier as discounting accumulates over many phases in a canonical regime with a common decay factor and equal-length phases. It further proves that this 1/2 barrier holds for arbitrary stopping rules in the same regime, showing that discounted i.i.d. instances can match the hardness of the fully non-i.i.d. case. The authors design single-quantile rules attaining the tight bounds via calibration to an effective horizon induced by discounting, extend the calibration to heterogeneous decay factors and unequal phase lengths, and demonstrate a similar discontinuous breakdown in an infinite-horizon continuous-decay benchmark where arbitrarily weak decay reduces the ratio from 1 to 1/2.

Significance. If the results hold, the work is significant because it demonstrates that even a weak, structured form of nonstationarity arising from discounting can eliminate the classical i.i.d. advantage in prophet inequalities and force the ratio down to the non-i.i.d. 1/2 barrier. The transition result for single-quantile policies together with the matching upper bound for arbitrary policies supplies a clean characterization. The algorithmic constructions that calibrate to the effective horizon, along with the extensions to heterogeneous decays, unequal phases, and the continuous benchmark, provide both theoretical insight and practical guidance. The existential claim that i.i.d. discounted rewards 'can be as hard' is directly supported by the high-level structure without visible internal inconsistency.

minor comments (2)
  1. The definition of the canonical regime (common decay factor, equal-length phases) is invoked repeatedly in the transition and persistence arguments; a self-contained formal statement of the regime parameters and the effective-horizon calibration rule would improve readability.
  2. The continuous-decay benchmark is presented as an infinite-horizon limit; a brief discussion of how the 1/2 collapse relates to the finite-phase transition (e.g., via a limiting argument) would strengthen the connection between the two settings.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our paper. The summary accurately captures the main contributions regarding the transition to the 1/2 barrier under discounting for both single-quantile policies and arbitrary stopping rules. We are grateful for the recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The abstract and described structure derive the 1/2 competitive-ratio barrier via direct analysis of single-quantile policies under common-decay equal-length phases, followed by an upper bound for arbitrary stopping rules. No equations reduce a claimed prediction to a fitted input by construction, no self-citation chain is load-bearing for the central transition result, and the 'as hard as non-i.i.d.' statement follows from the exhibited bounds rather than renaming or ansatz smuggling. The derivation remains independent of the target claim.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract introduces no fitted parameters, no new axioms beyond standard competitive-analysis assumptions, and no invented entities.

pith-pipeline@v0.9.1-grok · 5760 in / 1079 out tokens · 52869 ms · 2026-06-30T04:09:18.297772+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 9 canonical work pages · 2 internal anchors

  1. [1]

    ACM Transactions on Economics and Computation , volume=

    Prophet inequalities with linear correlations and augmentations , author=. ACM Transactions on Economics and Computation , volume=. 2023 , publisher=

    2023

  2. [2]

    arXiv preprint arXiv:2007.06110 , year=

    Unknown IID prophets: Better bounds, streaming algorithms, and a new impossibility , author=. arXiv preprint arXiv:2007.06110 , year=

    work page arXiv 2007

  3. [3]

    Mathematics of Operations Research , volume=

    Optimal stopping of a random sequence with unknown distribution , author=. Mathematics of Operations Research , volume=. 2022 , publisher=

    2022

  4. [4]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Bandit algorithms for prophet inequality and pandora's box , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  5. [5]

    ACM SIGecom Exchanges , volume=

    Recent developments in prophet inequalities , author=. ACM SIGecom Exchanges , volume=. 2019 , publisher=

    2019

  6. [6]

    arXiv preprint arXiv:2205.05519 , year=

    Prophet inequality on IID distributions: beating 1-1/e with a single query , author=. arXiv preprint arXiv:2205.05519 , year=

    work page arXiv

  7. [7]

    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Linear bandits with limited adaptivity and learning distributional optimal design , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

  8. [8]

    Advances in neural information processing systems , volume=

    Improved algorithms for linear stochastic bandits , author=. Advances in neural information processing systems , volume=

  9. [9]

    Foundations of computational mathematics , volume=

    User-friendly tail bounds for sums of random matrices , author=. Foundations of computational mathematics , volume=. 2012 , publisher=

    2012

  10. [10]

    Semiamarts and finite values , author=

  11. [11]

    Probability on Banach spaces , volume=

    On semiamarts, amarts, and processes with finite value , author=. Probability on Banach spaces , volume=. 1978 , publisher=

    1978

  12. [12]

    The Annals of Probability , pages=

    Comparisons of stop rule and supremum expectations of iid random variables , author=. The Annals of Probability , pages=. 1982 , publisher=

    1982

  13. [13]

    Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Beating 1-1/e for ordered prophets , author=. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=. 2017 , doi=

    2017

  14. [14]

    the Annals of Probability , pages=

    Comparison of threshold stop rules and maximum for independent nonnegative random variables , author=. the Annals of Probability , pages=. 1984 , publisher=

    1984

  15. [15]

    Proceedings of the forty-second ACM symposium on Theory of computing , pages=

    Multi-parameter mechanism design and sequential posted pricing , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=

  16. [16]

    Proceedings of the 2017 ACM Conference on Economics and Computation , pages=

    Posted price mechanisms for a random stream of customers , author=. Proceedings of the 2017 ACM Conference on Economics and Computation , pages=

    2017

  17. [17]

    Proceedings of the 2019 ACM Conference on Economics and Computation , pages=

    Prophet inequalities for iid random variables from an unknown distribution , author=. Proceedings of the 2019 ACM Conference on Economics and Computation , pages=

    2019

  18. [18]

    Contemporary Mathematics , volume=

    A survey of prophet inequalities in optimal stopping theory , author=. Contemporary Mathematics , volume=

  19. [19]

    ACM SIGecom Exchanges , volume=

    An economic view of prophet inequalities , author=. ACM SIGecom Exchanges , volume=. 2017 , publisher=

    2017

  20. [20]

    Proceedings of the 13th ACM Conference on Electronic Commerce , pages=

    Online prophet-inequality matching with applications to ad allocation , author=. Proceedings of the 13th ACM Conference on Electronic Commerce , pages=

  21. [21]

    arXiv preprint arXiv:2205.10302 , year=

    Individual fairness in prophet inequalities , author=. arXiv preprint arXiv:2205.10302 , year=

    work page arXiv

  22. [22]

    Advances in Neural Information Processing Systems , volume=

    Lookback prophet inequalities , author=. Advances in Neural Information Processing Systems , volume=

  23. [23]

    arXiv preprint arXiv:2011.14929 , year=

    Windowed Prophet Inequalities , author=. arXiv preprint arXiv:2011.14929 , year=

    work page arXiv 2011

  24. [24]

    Theory of Probability & Its Applications , volume=

    The problem of choice and the sptimal stopping rule for a sequence of independent trials , author=. Theory of Probability & Its Applications , volume=. 1966 , publisher=

    1966

  25. [25]

    The Annals of Statistics , volume=

    A statistical version of prophet inequalities , author=. The Annals of Statistics , volume=. 1998 , publisher=

    1998

  26. [26]

    arXiv preprint arXiv:2505.18828 , year=

    Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality , author=. arXiv preprint arXiv:2505.18828 , year=

    work page arXiv

  27. [27]

    Foundations and Trends

    An introduction to matrix concentration inequalities , author=. Foundations and Trends. 2015 , publisher=

    2015

  28. [28]

    arXiv preprint arXiv:1911.07945 , year=

    Optimal single-choice prophet inequalities from samples , author=. arXiv preprint arXiv:1911.07945 , year=

    work page arXiv 1911

  29. [29]

    Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    The two-sided game of googol and sample-based prophet inequalities , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    2020

  30. [30]

    Mathematics of Operations Research , volume=

    Sample-driven optimal stopping: From the secretary problem to the iid prophet inequality , author=. Mathematics of Operations Research , volume=. 2024 , publisher=

    2024

  31. [31]

    Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Competitive analysis with a sample and the secretary problem , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    2020

  32. [32]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    Prophet inequalities require only a constant number of samples , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

  33. [33]

    Optimal single threshold stopping rules and sharp prophet inequalities

    Optimal single threshold stopping rules and sharp prophet inequalities , author=. arXiv preprint arXiv:2404.12949 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  34. [34]

    Proceedings of the twenty-ninth annual acm-siam symposium on discrete algorithms , pages=

    Prophet secretary for combinatorial auctions and matroids , author=. Proceedings of the twenty-ninth annual acm-siam symposium on discrete algorithms , pages=. 2018 , organization=

    2018

  35. [35]

    Operations research , volume=

    Tight guarantees for static threshold policies in the prophet secretary problem , author=. Operations research , volume=. 2023 , publisher=

    2023

  36. [36]

    Foundations and Trends in Machine Learning , volume=

    Learning in repeated auctions , author=. Foundations and Trends in Machine Learning , volume=. 2022 , publisher=

    2022

  37. [37]

    Journal of economic literature , volume=

    Time discounting and time preference: A critical review , author=. Journal of economic literature , volume=. 2002 , publisher=

    2002

  38. [38]

    Management science , volume=

    Optimal dynamic pricing of inventories with stochastic demand over finite horizons , author=. Management science , volume=. 1994 , publisher=

    1994

  39. [39]

    The American economic review , volume=

    Congestion theory and transport investment , author=. The American economic review , volume=. 1969 , publisher=

    1969

  40. [40]

    Economica , pages=

    Optimal advertising policy under dynamic conditions , author=. Economica , pages=. 1962 , publisher=

    1962

  41. [41]

    Management science , volume=

    A new product growth for model consumer durables , author=. Management science , volume=. 1969 , publisher=

    1969

  42. [42]

    Beating 1-1/e for Ordered Prophets

    Beating 1-1/e for Ordered Prophets , author=. arXiv preprint arXiv:1704.05836 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  43. [43]

    Proceedings of the twentieth annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Secretary problems: weights and discounts , author=. Proceedings of the twentieth annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2009 , organization=

    2009

  44. [44]

    Stochastic analysis and applications , volume=

    Prophet regions for discounted, uniformly bounded random variables , author=. Stochastic analysis and applications , volume=. 2006 , publisher=

    2006

  45. [45]

    arXiv preprint arXiv:2407.11752 , year=

    IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates , author=. arXiv preprint arXiv:2407.11752 , year=

    work page arXiv