Pith. sign in

REVIEW 6 minor 36 references

Multi Choice Min Prophet

T0 review · 0 major / 6 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random order lets a min-prophet algorithm stay constant-competitive with only O(min{ln ln M, ln n}) expected choices; adversarial order forces nearly linear.

desk verdict Clean, nearly tight multi-choice complexity for min-prophet: exponential adversarial/random-order gap and expected-vs-deterministic separation, with complete proofs. read the letter →

arxiv 2607.05085 v1 pith:7AYDBMJT submitted 2026-07-06 cs.GT

Yossi Azar , Itamar Biran , Amos Fiat This is my paper · ORCID
classification cs.GT MSC 68W2760G4091B26
keywords prophetinequalitymincostmulti-choicesecretaryrandomordercompetitiveanalysisoptimalstopping
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The classical prophet inequality lets a maximizer keep half the prophet’s value with one irrevocable choice. Its minimization counterpart is far harder: even for identical distributions the competitive ratio can be exponential. This paper asks how many extra choices are needed to restore a constant ratio when the algorithm may keep several candidates and finally pay the best of them. It shows that arrival order is decisive. Under adversarial order any constant-competitive algorithm needs Ω(n / ln n) choices in expectation. Under random order (prophet secretary) a simple threshold rule needs only O(min{ln ln M, ln n}) expected choices, where M measures how much better the global minimum is than a single draw; the same bound is tight up to low-order logs already for i.i.d. variables. If the budget on choices must be deterministic rather than expected, n choices are necessary even for i.i.d. inputs. The same threshold idea extends to the multi-unit setting in which both sides keep the r cheapest items.

What carries the argument

A single threshold t chosen so that the expected number of values below t equals min{ln M + 1, n}, followed by the classical record-minima counting argument that bounds the number of updates by the harmonic series of that expectation.

What would settle it

Exhibit a family of continuous i.i.d. distributions for which every algorithm whose expected number of choices is o(min{ln ln M / ln ln ln M, ln n / ln ln n}) has competitive ratio that grows with n, or show a constant-competitive algorithm that uses only o(n / ln n) expected choices against adversarial order.

Watch

Extended reading notes

Core claim

In the multi-choice min-prophet problem a constant competitive ratio is achievable with O(min{ln ln M, ln n}) expected selections under random arrival, and this number is essentially necessary even for i.i.d. variables; under adversarial arrival the same guarantee requires Ω(n / ln n) expected selections, and any deterministic budget of n-1 selections yields an unbounded ratio.

Load-bearing premise

The algorithm must know every distribution in advance and be able to find a precise probability threshold, which the paper realises by assuming continuous distributions or infinitesimal perturbations of atoms.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies the multi-choice minimization (cost) prophet inequality: an online algorithm may select multiple variables from known independent distributions and pays the minimum among its selections, with the goal of achieving a constant competitive ratio against the offline minimum while minimizing the expected number of selections. For adversarial order it proves that any constant-competitive algorithm requires Ω(n/ln n) expected choices (Theorem 3.1). For the prophet-secretary (random-order) model it gives a simple threshold algorithm that is O(1)-competitive with only O(min{ln ln M, ln n}) expected choices, where M is the ratio of the smallest single-variable expectation to the expected global minimum (Theorem 4.1); a matching lower bound of Ω(min{ln ln M / ln ln ln M, ln n / ln ln n}) holds already for i.i.d. variables (Theorem 5.1). It further shows that any algorithm restricted to a deterministic budget of at most n-1 choices has unbounded competitive ratio even for i.i.d. inputs (Theorem 6.1). The techniques are extended to the multi-unit setting (sum of r selected values) for i.i.d. variables, again obtaining constant competitiveness with a small expected number of choices.

Significance. If correct, the results cleanly separate the minimization prophet inequality from its maximization counterpart and quantify a sharp exponential gap between adversarial and random order, as well as between expected and deterministic choice budgets. The introduction of the parameter M and the nearly tight bounds in terms of min{ln ln M, ln n} give a precise, distribution-sensitive measure of the power of multiple choices. The constructions (heavy-tailed distributions, doubly-logarithmic interval partitions, discrete super-exponential supports) and the elementary threshold-plus-record-minima analysis are transparent and reusable. Complete proofs are supplied for all main theorems (with short appendices for technical claims), which strengthens the contribution for the optimal-stopping and online-algorithms communities.

minor comments (6)
  1. [Abstract / §1] Abstract and introduction state the upper bound first as O(ln n) and later as O(min{ln ln M, ln n}); a single consistent statement of the refined bound would improve readability.
  2. [§4] Section 4 assumes continuous distributions (or infinitesimal perturbation of atoms) so that a threshold t with exact sum of probabilities can be found by binary search. While the paper notes this is standard, a one-sentence remark that the same competitive ratio and choice bound hold after an arbitrarily small additive perturbation of the competitive ratio would make the reduction fully explicit.
  3. [Appendix 10] In the multi-unit competitive-ratio argument (Appendix 10) the claim that the failure event contributes at most rM·(1/M) relies on the p-quantile t satisfying t = O(M). This follows at once from E[X] ≥ t(1-p), but is not written down; adding the one-line justification would remove any ambiguity.
  4. [§6] Theorem 6.1 is stated for arbitrary algorithms, yet the proof classifies only deterministic policies. A brief appeal to Yao’s principle (or the observation that a randomized algorithm is a distribution over deterministic ones) would close the argument for randomized algorithms that are hard-bounded by n-1 choices.
  5. [§5 / §6] Figures 1 and 2 are referenced but not rendered in the supplied manuscript; either include them or remove the references.
  6. Several minor typographical inconsistencies appear (e.g., missing spaces around mathematical operators, “than” for “then” in Appendix 10, and occasional mismatched parentheses in displayed equations). A careful copy-edit pass would polish the presentation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained combinatorial constructions and probabilistic proofs with no fitted parameters or self-referential predictions.

full rationale

The paper defines M directly from the input distributions (M = min_j E[X_j]/E[min_j X_j]), then constructs explicit threshold algorithms (Algorithm 1, Section 4) whose competitive ratio and expected choice count are proved from first principles via product bounds, Jensen on record minima, and Chernoff (for the multi-unit extension). Lower bounds (Theorems 3.1, 5.1, 6.1) are obtained by exhibiting concrete heavy-tailed i.i.d. or non-i.i.d. distributions and partitioning into intervals; the CR blow-ups follow by direct calculation of tail probabilities and conditional expectations (Claims 3.2–3.5, 5.2–5.6). No parameter is fitted to data and then re-used as a “prediction”; no uniqueness theorem or ansatz is imported from overlapping-author prior work to force the present claims; citations are standard background on classical prophet inequalities. The continuous-distribution hypothesis is handled by the paper’s own atom-perturbation remark and does not create a definitional loop. The entire derivation chain is therefore independent of its own outputs.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

Standard probabilistic assumptions of the prophet-inequality literature plus the definition of the difficulty parameter M. No free parameters are fitted; no new physical or mathematical entities are postulated beyond the algorithmic model itself.

assumptions (4)
  • domain assumption The n random variables are independent (not necessarily identical) with known distributions.
    Stated in Section 2; used throughout all upper and lower bounds.
  • domain assumption Distributions may be assumed continuous (or atoms may be infinitesimally perturbed) without changing the asymptotic claims.
    Explicitly invoked in Section 2 and before Algorithm 1 to justify existence of an exact probability threshold t.
  • domain assumption The algorithm must select at least one variable (otherwise cost is defined as infinity).
    Stated in Section 2; forces the single-choice baseline to be well-defined.
  • standard math Standard facts of probability: Chernoff bounds, Jensen's inequality for concave functions, harmonic-number bounds, record statistics of random permutations.
    Used in the competitive-ratio and expected-choice analyses of Sections 4 and 10.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multi Choice Min Prophet." pith.science (2026). https://pith.science/paper/7AYDBMJT

@misc{pith2026260705085,
  author       = {Pith},
  title        = {Pith review of: Multi Choice Min Prophet},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7AYDBMJT}},
  note         = {Machine review of arXiv:2607.05085}
}
abstract

We study the minimization counterpart of the classic prophet inequality, often termed the min prophet or cost prophet inequality. Unlike the maximization setting, where simple threshold algorithms achieve half of the prophet's value, the minimization setting is significantly harder, with an exponential lower bound even for i.i.d.\ variables. We study a multi-choice relaxation in which the algorithm may select multiple variables and gets to choose the best amongst them (the minimum amongst those selected). Our goal is to minimize the expected number of selections while achieving a constant competitive ratio. For adversarial order, we show that a constant competitive ratio requires a nearly linear number of choices in expectation, ergo, $\Omega(n/\ln n)$. In contrast, we show that for the prophet secretary model (random order) one can attain constant competitiveness while requiring only an exponentially smaller expected number of choices i.e. $O(\ln n)$. We give a refined analysis and define $M$ to be the ratio of the minimum expected value of any single variable to the expected minimum value of all variables (the prophet's value) and present an algorithm that achieves a constant competitive ratio with $O(\min\{\ln \ln M, \ln n\})$ choices in expectation for the prophet secretary. We show that this is tight up to low order log factors even for the special case of the i.i.d. model. We also show that if we insist on a deterministic bound on the number of choices then every constant competitive algorithm requires $n$ choices. This holds even in the i.i.d.\ setting Finally, we consider a variant where both the algorithm and the adversary choose $r$ values and pay their sum, this is the minimization multi unit version. We extend our techniques to the multi-unit variant for i.i.d.\ variables, achieving a constant competitive ratio with a small expected number of choices.

Figures

Figures reproduced from arXiv: 2607.05085 by the authors.

Figure 1
Figure 1. intervals for β = e n Proof. Assume by contradiction that there exists an algorithm which makes fewer than T choices in the first nT variables with probability of more than 1 ln ln ln β and that its compet￾itive ratio is constant. By looking at the disjoint intervals [1, n1], [n1 + 1, n2], ..., [nT −1 + 1, nT ]. Let E be the event that the algorithm makes fewer than T choices in the first nT variables. On event E it… view at source ↗
Figure 2
Figure 2. σk 19 [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 1 linked inside Pith

  1. [1]

    Kleinberg, and Brendan Lucier

    Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Haji- aghayi, Robert D. Kleinberg, and Brendan Lucier. Beating 1-1/e for ordered prophets. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors,Pro- ceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 61...

    2017

  2. [2]

    Multi-dimensional mechanism design via random order contention resolution schemes.SIGecom Exch., 17(2):46–53, 2019.→ cited on page 6

    Marek Adamczyk and Michal Wlodarczyk. Multi-dimensional mechanism design via random order contention resolution schemes.SIGecom Exch., 17(2):46–53, 2019.→ cited on page 6

    2019

  3. [3]

    Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers.SIAM J

    Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers.SIAM J. Comput., 43(2):930–972, 2014.→cited on page 2, 6

    2014

  4. [4]

    Tight guarantees for static threshold policies in the prophet secretary problem.Oper

    Nick Arnosti and Will Ma. Tight guarantees for static threshold policies in the prophet secretary problem.Oper. Res., 71(5):1777–1788, 2023.→cited on page 6

    2023

  5. [5]

    Two-choice optimal stop- ping.Advances in Applied Probability, 36(4):1116–1147, 2004.→cited on page 5

    David Assaf, Larry Goldstein, and Ester Samuel-Cahn. Two-choice optimal stop- ping.Advances in Applied Probability, 36(4):1116–1147, 2004.→cited on page 5

    2004

  6. [6]

    Simple ratio prophet inequalities for a mortal with multiple choices.Journal of Applied Probability, 37(4):1084–1091, 2000.→ cited on page 2, 6

    David Assaf and Ester Samuel-Cahn. Simple ratio prophet inequalities for a mortal with multiple choices.Journal of Applied Probability, 37(4):1084–1091, 2000.→ cited on page 2, 6

    2000

  7. [7]

    Prophet secretary: Surpassing the 1-1/e barrier

    Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Prophet secretary: Surpassing the 1-1/e barrier. In ´Eva Tardos, Edith Elkind, and Rakesh Vohra, editors,Pro- ceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 303–318. ACM, 2018.→cited on page 6

    2018

  8. [8]

    The competi- tion complexity of dynamic pricing.Math

    Johannes Brustle, Jos´ e Correa, Paul Duetting, and Victor Verdugo. The competi- tion complexity of dynamic pricing.Math. Oper. Res., 49(3):1986–2008, 2024.→ cited on page 2, 7 22

    1986

Show all 36 references
  1. [9]

    Devanur, and Thodoris Lykouris

    Shuchi Chawla, Nikhil R. Devanur, and Thodoris Lykouris. Static pricing for multi- unit prophet inequalities.Oper. Res., 72(4):1388–1399, 2024.→cited on page 6

    2024

  2. [10]

    Prophet secretary and matching: the significance of the largest item

    Ziyun Chen, Zhiyi Huang, Dongchen Li, and Zhihao Gavin Tang. Prophet secretary and matching: the significance of the largest item. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Dis- crete Algorithms, SODA 2025, New Orleans, ...

    2025

  3. [11]

    Posted price mechanisms for a random stream of customers

    Jos´ e Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vrede- veld. Posted price mechanisms for a random stream of customers. InProceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, page 169–186, New York, NY, USA, 2017. Association for...

    2017

  4. [12]

    Posted price mechanisms and optimal threshold strategies for random arrivals

    Jos´ e Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vrede- veld. Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res., 46(4):1452–1478, 2021.→cited on page 6

    2021

  5. [13]

    Prophet secretary for combinatorial auctions and matroids.SIAM J

    Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids.SIAM J. Comput., 53(6):1641–1662, 2024.→cited on page 6

    2024

  6. [14]

    Prophet inequal- ities with cancellation costs

    Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, and Jan Vondr´ ak. Prophet inequal- ities with cancellation costs. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June ...

    2024

  7. [15]

    Prophet secretary.SIAM J

    Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. Prophet secretary.SIAM J. Discret. Math., 31(3):1685–1701, 2017. →cited on page 2, 5, 6

    2017

  8. [16]

    Prophets and secretaries with overbooking

    Tomer Ezra, Michal Feldman, and Ilan Nehama. Prophets and secretaries with overbooking. In ´Eva Tardos, Edith Elkind, and Rakesh Vohra, editors,Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 319–320. ACM, 2018.→cit...

    2018

  9. [17]

    Prophet inequalities: Separating random order from order selection.CoRR, abs/2304.04024, 2023.→cited on page 2

    Giordano Giambartolomei, Frederik Mallmann-Trenn, and Raimundo Saona. Prophet inequalities: Separating random order from order selection.CoRR, abs/2304.04024, 2023.→cited on page 2

    2023 arXiv

  10. [18]

    Oracle-augmented prophet inequalities

    Sariel Har-Peled, Elfarouk Harb, and Vasilis Livanos. Oracle-augmented prophet inequalities. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors,51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, Tallinn, Estonia, July 8-...

    2024

  11. [19]

    New prophet inequalities via poissonization and sharding

    Elfarouk Harb. New prophet inequalities via poissonization and sharding. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 1222–1269. SIAM, 2025.→c...

    2025

  12. [20]

    Hill and Robert P

    Theodore P. Hill and Robert P. Kertz. Stop rules and supremum expectations of i.i.d. random variables.Annals of Probability, 10(2):336–345, 1982.→cited on page 2, 6

    1982

  13. [21]

    Tight guarantees for multiunit prophet inequalities and online stochastic knapsack.Oper

    Jiashuo Jiang, Will Ma, and Jiawei Zhang. Tight guarantees for multiunit prophet inequalities and online stochastic knapsack.Oper. Res., 73(3):1703–1721, 2025.→ cited on page 6

    2025

  14. [22]

    Stop rule and supremum expectations of i.i.d

    Robert P Kertz. Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality.Journal of Multivariate Analysis, 19(1):88–112, 1986.→cited on page 2

    1986

  15. [23]

    Matthew Weinberg

    Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities and applications to multi-dimensional mechanism design.Games Econ. Behav., 113:97– 115, 2019.→cited on page 6

    2019

  16. [24]

    Semiamarts and finite values.Bulletin of the American Mathematical Society, 83(4):745–747, July 1977.→cited on page 2, 6

    Ulrich Krengel and Louis Sucheston. Semiamarts and finite values.Bulletin of the American Mathematical Society, 83(4):745–747, July 1977.→cited on page 2, 6

    1977

  17. [25]

    On semiamarts, amarts, and processes with finite value

    Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. InProbability on Banach Spaces, volume 4, pages 197–266. Dekker, 1978.→cited on page 2, 6

    1978

  18. [26]

    Minimization is harder in the prophet world

    Vasilis Livanos and Ruta Mehta. Minimization is harder in the prophet world. In David P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 424–461. SIAM, 2024.→cited on page 2, 6

    2024

  19. [27]

    Minimization I.I.D

    Vasilis Livanos and Ruta Mehta. Minimization I.I.D. prophet inequality via extreme value theory: A unified approach. In Itai Ashlagi and Aaron Roth, editors,Pro- ceedings of the 26th ACM Conference on Economics and Computation, EC 2025, Stanford University, Stanford, CA, USA, ...

    2025

  20. [28]

    Minimization fractional prophet in- equalities for sequential procurement.Math

    Junjie Qin, Shai Vardi, and Adam Wierman. Minimization fractional prophet in- equalities for sequential procurement.Math. Oper. Res., 49(2):928–947, 2024.→ cited on page 6

    2024

  21. [29]

    Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for indepen- dent nonnegative random variables.The Annals of Probability, 12(4):1213–1216, 1984.→cited on page 2 24 8 Missing proofs from section 3 8.1 Proof of Claim 3.2 Proof.Let Y= min{X 1, X2, . . . , Xn}. N...

    1984

  22. [30]

    Find a thresholdt(e.g., by binary search) such that X i pi = min{max{4 lnM+r,5r}, n}, wherep i = Pr(Xi ≤t)

  23. [31]

    If onlyℓ < rsuch items appear, take the remainingr−ℓitems from the last arrivals

    Wait until the firstritems with values at mosttappear. If onlyℓ < rsuch items appear, take the remainingr−ℓitems from the last arrivals

  24. [32]

    Theorem 10.1.For i.i.d

    Thereafter, switch only if a newly observed value is strictly smaller than the highest value currently held among theritems. Theorem 10.1.For i.i.d. variables andr≤lnM, the algorithm above is constant competitive and uses O min rln lnM r , rln n r choices in expectation. Theor...

  25. [33]

    The analysis mirrors Section 4; scaling by 4 does not affect asymptotics

    P i pi = 4 lnM+r. The analysis mirrors Section 4; scaling by 4 does not affect asymptotics. Since the algorithm tracksrvalues, the expected number of choices isO rln lnM r + lnr =O rln lnM r

  26. [34]

    By the record-minima argument, the expected number of choices amongO(r) samples isr+r(H 4r −H r) =O(r)

    P i pi = 5r. By the record-minima argument, the expected number of choices amongO(r) samples isr+r(H 4r −H r) =O(r)

  27. [35]

    This regime occurs when all items are relevant (i.e., all below the threshold)

    P i pi =n. This regime occurs when all items are relevant (i.e., all below the threshold). In that case, every incoming item may potentially replace one of the currently heldritems, exactly following the record-minima process generalized to ther-unit case. As derived above, E[...

  28. [36]

    uniform [0,1] variables has expectationE[min j Xj] = 1/(n+ 1)

    The minimum ofni.i.d. uniform [0,1] variables has expectationE[min j Xj] = 1/(n+ 1). Hence M= 1/2 1/(n+ 1) = n+ 1 2 = Θ(n). Thus for a “nice” bounded distribution such asU[0,1], the difficulty parameterMgrows linearly withn. 31 A truncated heavy-tailed distribution.FixZ≤e n an...

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.