Optimal single threshold stopping rules and sharp prophet inequalities
Pith reviewed 2026-05-24 02:22 UTC · model grok-4.3
The pith
Sharp constants in prophet inequalities for single-threshold stopping rules are the values of an infinite zero-sum game on the unit square.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The sharp constants in the ratio- and difference-type prophet inequalities are determined by the optimal values of an infinite two-person zero-sum game on the unit square with particular payoff kernels, while the solutions to the game provide optimal stopping rules and least favorable distributions. This formulation also allows a systematic way to tackle restricted classes of distributions and leads to a numerically efficient algorithmic paradigm that computes the constants with any prescribed level of accuracy.
What carries the argument
An infinite two-person zero-sum game on the unit square whose payoff kernels encode the ratio or difference achieved by any single-threshold stopping rule against an arbitrary distribution.
If this is right
- Optimal single-threshold stopping rules are recovered directly from the equilibrium strategies of the game.
- The least favorable distributions that attain the sharp bounds appear as part of the same game solution.
- The framework supplies sharp constants for any restricted class of distributions by restricting the strategy sets of the game.
- The constants can be computed to arbitrary numerical accuracy by solving finite approximations to the infinite game.
Where Pith is reading between the lines
- The same game construction could be modified to obtain bounds for stopping rules that use more than one threshold.
- The resulting sharp constants might serve as benchmarks when comparing single-threshold rules against other online selection algorithms.
- Explicit solution of the game for particular payoff kernels could produce closed-form expressions for the prophet constants in special cases.
Load-bearing premise
The performance of every single-threshold stopping rule against every possible distribution is captured exactly by the value of the described zero-sum game on the unit square.
What would settle it
A concrete distribution together with a single-threshold rule whose achieved ratio or difference strictly exceeds the value computed from the corresponding game on the unit square.
read the original abstract
This paper considers a finite horizon optimal stopping problem for a sequence of independent and identically distributed random variables, where the objective is to design stopping rules that attempt to select the random variable with the highest value in the sequence. The performance of any stopping rule may be benchmarked relative to the selection of a ``prophet" that has perfect foreknowledge of the largest value. Such comparisons are typically stated in the form of ``prophet inequalities." In this paper we develop a game-theoretic characterization that supports a principled approach for deriving sharp non-asymptotic prophet inequalities for single threshold stopping rules. We demonstrate that sharp constants in the ratio- and difference-type prophet inequalities are determined by the optimal values of infinite two-person zero-sum game on the unit square with particular payoff kernels, while the the solutions to the game provide optimal stopping rules and least favorable distributions. Among other things, this formulation also allows a systematic way to tackle restricted classes of distributions. The proposed framework leads to a numerically efficient algorithmic paradigm that allows computing sharp constants in prophet inequalities with any prescribed level of accuracy.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to develop a game-theoretic characterization for sharp non-asymptotic prophet inequalities in finite-horizon i.i.d. optimal stopping problems restricted to single-threshold stopping rules. Sharp constants in both ratio-type and difference-type inequalities are asserted to equal the values of certain infinite two-person zero-sum games on the unit square whose payoff kernels are described as particular; the saddle-point strategies of these games are claimed to yield both the optimal stopping rules and the least-favorable distributions. The framework is also said to support a numerically efficient algorithm that computes the constants to any prescribed accuracy and extends to restricted classes of distributions.
Significance. If the claimed exact correspondence between the game values and the prophet constants holds, the work supplies a systematic, non-asymptotic method for deriving sharp constants together with a practical numerical procedure; both features would be useful additions to the prophet-inequality literature. The ability to treat restricted distribution families is an additional practical strength.
major comments (2)
- [Abstract] Abstract: the central claim that the infinite zero-sum game on the unit square determines the sharp prophet constants requires an explicit verification that (i) the game possesses a value, (ii) this value coincides with the prophet ratio or difference constant, and (iii) every saddle-point strategy pair maps to a valid distribution F and threshold t whose performance exactly matches the game payoff. The abstract asserts the characterization but supplies neither the explicit kernels nor the minimax argument; the manuscript must therefore contain a self-contained proof that the reduction incurs no gaps.
- [Game-theoretic characterization] Game-theoretic characterization (abstract and subsequent sections describing the payoff kernels): the reduction implicitly invokes a minimax theorem and compactness/convexity conditions on the strategy sets. The manuscript should state the precise regularity assumptions on the kernels (continuity, measurability, etc.) and confirm that the resulting mixed strategies over the unit square produce attainable single-threshold rules and distributions without boundary artifacts.
minor comments (1)
- [Abstract] The abstract contains the typographical repetition “the the solutions.”
Simulated Author's Rebuttal
We thank the referee for the thoughtful and detailed report. The comments highlight the need for greater explicitness in the game-theoretic reduction. We agree that the characterization benefits from a self-contained verification and will revise the manuscript to include the requested details on the minimax argument, kernel properties, and mapping from saddle points. Our point-by-point responses follow.
read point-by-point responses
-
Referee: [Abstract] Abstract: the central claim that the infinite zero-sum game on the unit square determines the sharp prophet constants requires an explicit verification that (i) the game possesses a value, (ii) this value coincides with the prophet ratio or difference constant, and (iii) every saddle-point strategy pair maps to a valid distribution F and threshold t whose performance exactly matches the game payoff. The abstract asserts the characterization but supplies neither the explicit kernels nor the minimax argument; the manuscript must therefore contain a self-contained proof that the reduction incurs no gaps.
Authors: We accept that the abstract is a summary and that the reduction requires explicit verification of (i)-(iii). The body of the manuscript develops the payoff kernels and argues that the game value equals the prophet constant via the correspondence between strategies and (F,t) pairs. To address the gap, we will add a dedicated subsection (or appendix) that states the minimax theorem applied, verifies the value coincidence, and explicitly constructs the mapping from saddle-point strategies to attainable distributions and thresholds, confirming no boundary artifacts arise. This will render the argument self-contained. revision: yes
-
Referee: [Game-theoretic characterization] Game-theoretic characterization (abstract and subsequent sections describing the payoff kernels): the reduction implicitly invokes a minimax theorem and compactness/convexity conditions on the strategy sets. The manuscript should state the precise regularity assumptions on the kernels (continuity, measurability, etc.) and confirm that the resulting mixed strategies over the unit square produce attainable single-threshold rules and distributions without boundary artifacts.
Authors: We agree that the regularity assumptions and compactness/convexity conditions should be stated explicitly rather than left implicit. In the revision we will specify the continuity and measurability properties of the kernels, confirm that the strategy sets satisfy the hypotheses of the relevant minimax theorem, and verify that every mixed-strategy pair yields a valid single-threshold rule and distribution F without introducing unattainable boundary cases. These clarifications will be inserted in the section introducing the game. revision: yes
Circularity Check
No circularity: game reformulation is an independent mathematical equivalent
full rationale
The paper derives a zero-sum game on the unit square whose payoff kernels are constructed from the single-threshold stopping problem and i.i.d. distributions; the game value is then shown to equal the sharp prophet constant. This is a standard equivalence reduction rather than a self-definitional loop or fitted-input prediction. No self-citations are load-bearing, no parameters are fitted then relabeled as predictions, and no ansatz is smuggled via prior work. The derivation chain remains self-contained once the kernel construction and minimax application are accepted; the result is not forced by definition of its own inputs.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The random variables are independent and identically distributed.
invented entities (1)
-
Infinite two-person zero-sum game on the unit square with particular payoff kernels
no independent evidence
Reference graph
Works this paper leans on
-
[1]
Assaf, D. , Goldstein, L. and Samuel-Cahn, E. (2002). Ratio prophet inequalities when the mortal has seve ral choices. Ann. Appl. Probab. 12, 972–984. Bruss, F. T. and Ferguson, T. S. (1996). Half-prophets and Robbins’ problem of minimizing t he expected rank. Athens Conference on Applied Probability and Time Series Analysis , Vol. I (1995), 1–17. Lect. N...
work page 2002
-
[2]
Springer-Verlag, New York. Chow, Y. S. , Robbins, H. and Siegmund, D. (1971). Great Expectations: the Theory of Optimal Stopping. Houghton Mifflin Co., Boston, Massachusets. Correa, J. , Foncea, P. , Hoeksma, R. , Oosterwijk, T. and Vredeveld, T. (2018). Recent developments in prophet inequal- ities. ACM SIGecom Exchanges 17, 61–70. Correa, J. , Foncea, P. ...
work page 1971
-
[3]
, 191–207, Contemp. Math., 125, Amer. Math. Soc., Providenc e, RI. Jones, M. (1990). Prophet inequalities for cost of observation stopp ing problems. J. Multivariate Anal. 34, 238–253. Karlin, S. (1959). Mathematical Methods and Theory in Games, Programming and E conomics. Vol. II: The Theory of Infinite Games. Addison-W esley Publishing Co., Inc., Reading...
work page 1990
-
[4]
Princeton University Pr ess, Princeton, NJ. 25 Lucier, B. (2017). An economic view of prophet inequalities. ACM SIGecom Exchanges 16, 26–49. Meyerthole, A. and Schmitz, N. (2000). Games against a prophet for stochastic processes. Game Theory, Optimal Stopping, Probability and Statistics: Papers in Honor of Thomas S. Fer guson. Editors F. T. Bruss, L. Le C...
work page 2017
-
[5]
The MOSEK Optimization Toolbox for MATLAB Manual
Mosek ApS . The MOSEK Optimization Toolbox for MATLAB Manual. Ver.9.0. , http://docs.mosek.com/9.0/toolbox/index.html Samuel–Cahn, E. (1984). Comparison of threshold stop rules and maximum for i ndependent nonnegative random variables. Ann. Probab. 12, 1213–1216. Samuel–Cahn, E. (1992). A difference prophet inequality for bounded i.i.d. r andom variables, ...
work page 1984
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.