Pith. sign in

REVIEW 1 major objections 4 minor 2 cited by

The Competition Complexity of Prophet Secretary

T0 review · 1 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read For the prophet secretary problem, fully adaptive algorithms have (1−ε)-competition complexity Θ(√ln(1/ε)), with time-based and single-threshold classes strictly worse.

desk verdict Tight results for the random-arrival competition complexity of prophet secretary, but the main lower bound for general algorithms rests on a false Stirling estimate that must be fixed. read the letter →

arxiv 2411.10892 v1 pith:I6PGVCG6 submitted 2024-11-16 cs.GT

Tomer Ezra , Tamar Garbuz This is my paper · ORCID
classification cs.GT MSC 60G4091B26
keywords prophetsecretarycompetitioncomplexityresourceaugmentationrandomorderarrivalsthresholdalgorithmsadaptiveoptimalstoppingonline
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

This paper asks how many independent copies of each reward a decision-maker needs to see, in a random-order prophet secretary problem, to recover a (1−ε) fraction of the expected maximum of the original instance. It establishes that this number, the (1−ε)-competition complexity, depends sharply on how adaptive the algorithm is: Θ(ln(1/ε)) for single-threshold rules, Θ(ln(1/ε)/ln ln(1/ε)) for time-based and activation-based rules, and Θ(√ln(1/ε)) for fully general adaptive algorithms. The result separates the random-order model from the i.i.d. and block-arrival models, where general algorithms need only Θ(ln ln(1/ε)). If the theorem is right, extra copies are used most efficiently by algorithms that adapt to which rewards have already appeared, and the algorithm classes behind the best-known prophet-secretary competitive ratios are not optimal for competition complexity.

What carries the argument

The central construction is a continuous-time adaptive two-threshold algorithm. It defines q(t) as the probability that no reward arriving at or after time t exceeds the lower threshold τ2, namely q(t)=∏_{i,j}(1−(1−q_i)·1[t_{i,j}≥t]) with q_i=Pr[V_i≤τ2], and sets the switching time S to be the last t with q(t)≤ε. Before S the algorithm uses the high threshold τ1, after S the lower threshold τ2; the identity q(0)=ε⁸ makes S well-defined, and Hoeffding-style estimates on the events that the algorithm never reaches 2/k or that S comes too early carry the stochastic-domination argument for all values of x. The lower-bound machinery is a two-type hard instance in which all k deterministic rewards of value 1 and all k random rewards of value 1+√ε arrive in a uniformly random order, with the 'bad' event being that all deterministic rewards arrive first.

What would settle it

Evaluate (k!)²/(2k)! at k=3 and k=10: the paper's bound 1/(4k) gives 0.0833 and 0.025, while the true values are 0.05 and about 5.4×10⁻⁶. The concrete check is whether replacing the false bound with the asymptotic Θ(√k/4^k) still exceeds $3e^{{−√ln(1/ε)}}$ for k≈√ln(1/ε)/2; if it does, the lower-bound theorem can be repaired, and if it does not, the lower bound as expressed would not follow.

Watch

Extended reading notes

Core claim

The central discovery is the tight characterization of competition complexity across four nested classes of algorithms, summarized by Theorem 5.1 for general algorithms: their (1−ε)-competition complexity is Θ(√ln(1/ε)). The upper bound is an explicit adaptive algorithm that works for every product distribution: it starts with a high threshold τ1 at the 3/4-quantile of the prophet's value and switches at a random time S to a much lower threshold τ2 at the $e^{{−ℓ}}$-quantile, where ε=$e^{{−ℓ²}}$ and S is the last time at which the probability that no remaining reward exceeds τ2 is at most ε. The lower bound is a hard instance with k deterministic rewards of value 1 and k random rewards of value 1+√ε with failure probability p=$e^{{−√ln(1/ε)}}$; the paper argues that with k≈√ln(1/ε)/2 copies, a 'bad' arrival order forces any algorithm to lose the √ε gap. The lower bound is stated even for algorithms that know the random arrival order in advance.

Load-bearing premise

The lower-bound proof leans on the estimate that all k deterministic rewards outrank all k random rewards in arrival order with probability at least 1/(4k); that estimate is false for k≥3, so the proof as written needs a corrected Stirling comparison to stand.

Editorial extensions

If this is right

  • For any product distribution, an explicit general algorithm achieves the optimal (1−ε)-approximation with k=Θ(√ln(1/ε)) copies; no algorithm in the other three classes can match this asymptotically.
  • Single-threshold rules require k=Θ(ln(1/ε)), so replacing a static threshold with adaptive switching reduces the required copies from logarithmic to square-root-logarithmic in 1/ε.
  • Time-based threshold and activation-based rules both require k=Θ(ln(1/ε)/ln ln(1/ε)); they are strictly more powerful than single-threshold rules but strictly less powerful than general algorithms.
  • The random-order model is harder than the i.i.d. and block-arrival models for general algorithms, Θ(√ln(1/ε)) versus Θ(ln ln(1/ε)) copies, while single-threshold rules show no such separation.
  • Under the standard virtual-value reduction, the same asymptotic copy bounds transfer to approximating optimal expected revenue in sequential auctions subject to a regularity condition.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One extension of the paper's approach is that its hard-instance construction can likely be repaired: replacing the false Stirling bound with the correct asymptotic (k!)²/(2k)!=Θ(√k/4^k) still beats the comparison against p=e^{−√ln(1/ε)} by an exponential margin for large 1/ε, so the Θ(√ln(1/ε)) theorem appears to survive with changed constants.
  • A direct testable separation is to simulate the hard instance against a personalized static-threshold algorithm, the strongest pre-activation class; the paper's activation-based lower bound suggests it would need the log/log-log rate, and the simulation would quantify the constants.
  • The lower bound's robustness to knowing the arrival order suggests an information-complexity interpretation: copies of each reward can substitute for knowledge of the order, and quantifying that trade-off exactly is a natural next step.
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

1 major / 4 minor

Summary. The paper studies the (1−ε)-competition complexity of the single-choice prophet secretary problem under random arrival order. The model gives the online algorithm k independent copies of each reward and asks for the smallest k such that some algorithm in a given class achieves expected value at least (1−ε) times the expected offline maximum of the original instance. The paper considers four classes of algorithms: single-threshold, time-based threshold, activation-based, and general adaptive algorithms. It claims tight asymptotic bounds of Θ(ln(1/ε)) for single-threshold algorithms, Θ(ln(1/ε)/ln ln(1/ε)) for time-based and activation-based algorithms, and Θ(√ln(1/ε)) for general algorithms. The proofs use a continuous-time arrival model, stochastic-domination comparisons to the prophet, and explicit hard instances with two reward types. The appendices contain proofs of the preliminary coupling lemmas and the activation-based lower bound.

Significance. If the results are correct, the paper gives a complete asymptotic characterization of competition complexity for the four most natural classes of prophet-secretary algorithms. The claimed separation between time-based/activation-based algorithms and general adaptive algorithms is a substantial and somewhat surprising structural finding, as is the contrast with the block-arrival model. The upper-bound constructions are explicit and simple, and the lower-bound instances are concrete. The technical machinery based on Lemmas 2.1 and 2.2 is clean and appears reusable. However, the lower-bound proof for general algorithms contains a false Stirling-based inequality that is load-bearing for Theorem 5.1; the construction appears repairable, but the submitted proof as written does not establish the Ω(√ln(1/ε)) bound.

major comments (1)
  1. [Section 5.2, Eq. (18), Lemma 5.2] The proof of the general-algorithm lower bound relies on the inequality (k!)²/(2k)! ≥ 1/(4k), stated after applying Stirling's approximation. This inequality is false for k ≥ 3; for example, for k = 3 the left-hand side is 0.05, while 1/(4k) ≈ 0.0833. The correct asymptotic behavior is (k!)²/(2k)! ∼ √(πk)/4^k, which is exponentially smaller than 1/(4k). Consequently, the displayed chain leading to E[ALG] ≤ 1 + √ε − √ε/(4k) is not justified, and the proof of the Ω(√ln(1/ε)) lower bound in Lemma 5.2 does not go through as written. This is a load-bearing step, since it is the only lower-bound argument supporting Theorem 5.1. The gap appears repairable: replacing 1/(4k) with the valid lower bound 4^{-k} (up to a polynomial factor) still suffices for sufficiently small ε, because for k = (1/2)√ln(1/ε) one has 4^{-k} = e^{−(ln 4/2)√ln(1/ε)}, which dominates 3p = 3e^{−√ln(1/ε)}. The authors should rework this part with correct constants and write out the repaired chain.
minor comments (4)
  1. [Section 5.1, Eq. (13)] The parenthetical remark that the expectation in the Hoeffding application is “3ℓ” is incorrect; the expectation of ∑ w_i 1[t_i < 2/k] is 2ℓ. The Hoeffding bound itself remains valid with the deviation term 7ℓ² − 3ℓ, so this is a typographical issue, but it should be fixed.
  2. [Section 5.1, Eq. (12)] The claim that the final inequality holds “for every n, k” is not true for k = 1, and the n dependence is not immediate. In the actual application k is large (k = 8ℓ), so the argument is unaffected, but the statement should either be restricted to the relevant range or accompanied by a short justification.
  3. [Section 5.2, Lemma 5.2] The proof assumes that k = √ln(1/ε)/2 is an integer and later says “for sufficiently small ε (such that k ≥ 4)”. Since k is a function of ε, the statement would be cleaner if it explicitly said “up to rounding” or let k be an integer parameter and then chose ε accordingly.
  4. [Throughout] Several LaTeX control sequences appear literally in the text, including “/BD”, “/C6”, and “bracehtipupleft”/“bracehtipdownright”. These typesetting artifacts make some displayed equations difficult to parse and should be cleaned before any final version.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new competition-complexity bounds are derived from in-text proofs or genuinely prior external results, and the flagged Stirling issue in Lemma 5.2 is a correctness gap rather than a circular step.

full rationale

Walking the derivation chain: Theorem 3.1's lower bound is imported from [6], an overlapping-author paper, but it is a prior, independent result for i.i.d. instances; using a restricted instance class only strengthens the lower bound, and the result is not derived from the present paper. The upper bound of Theorem 3.1 is proved in-text. Section 2.1 cites Correa et al. [13], but Lemmas 2.1 and 2.2 and Corollary 2.1 are re-proved in Appendix B, so the stochastic-domination machinery is self-contained rather than an appeal to authority. Lemma 4.1, Lemma 4.2, Lemma 5.1, and Theorem C.1 each give explicit constructions and full proofs; no parameter is fitted to a target quantity and then re-presented as a prediction. No equation is definitionally equal to its conclusion. The one notable mathematical issue is Lemma 5.2's Stirling estimate (k!)²/(2k)! ≥ 1/(4k), which fails for k ≥ 3; this is a genuine correctness gap in the lower-bound proof, but it is not circularity, because the proof does not assume its own conclusion and the construction is not defined in terms of the target theorem. Thus no specific circular step can be exhibited, and the appropriate finding is no significant circularity.

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

No free parameters are fitted to data; the paper is a worst-case asymptotic analysis with explicit algorithm constructions and adversarial instances. The model assumptions (known distributions, continuous-time equivalence, continuity) are standard in the prophet secretary literature. The key mathematical tools (Stirling, Hoeffding, the replacement lemmas) are either cited or proved in the appendix. One imported result from the authors' prior work [6] is used for a lower bound.

assumptions (5)
  • standard math Stirling approximation and Hoeffding's inequality are valid as stated (Theorems 2.1 and 2.2).
    Used throughout the proofs of the lower and upper bounds.
  • domain assumption The continuous-time arrival model is equivalent to the discrete-time random-permutation model for the purposes of competition complexity (Section 2).
    The paper argues by coupling; all positive and negative results are transferred between the two models.
  • domain assumption Distributions can be assumed continuous without loss of generality (Section 2, 'Simplifying Assumptions').
    Standard tie-breaking argument; hard instances use point masses but are claimed adaptable to continuous distributions.
  • domain assumption The lower bound for single-threshold algorithms in the i.i.d. case from Brustle et al. [6] is correct (Theorem 3.1).
    The paper imports this lower bound directly for the random-arrival model.
  • standard math Lemma 2.1 and Lemma 2.2 (replacement lemmas for threshold stopping probabilities) are correct.
    Proved in Appendix B; they are the backbone of the upper bound arguments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Competition Complexity of Prophet Secretary." pith.science (2026). https://pith.science/paper/I6PGVCG6

@misc{pith2026241110892,
  author       = {Pith},
  title        = {Pith review of: The Competition Complexity of Prophet Secretary},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I6PGVCG6}},
  note         = {Machine review of arXiv:2411.10892}
}
abstract

We study the classic single-choice prophet secretary problem through a resource augmentation lens. Our goal is to bound the $(1-\epsilon)$-competition complexity for different classes of online algorithms. This metric asks for the smallest $k$ such that the expected value of the online algorithm on $k$ copies of the original instance, is at least a $(1 - \epsilon)$-approximation to the expected offline optimum on the original instance (without added copies). We consider four natural classes of online algorithms: single-threshold, time-based threshold, activation-based, and general algorithms. We show that for single-threshold algorithms the $(1-\epsilon)$-competition complexity is $\Theta(\ln(\frac{1}{\epsilon}))$ (as in the i.i.d. case). Additionally, we demonstrate that time-based threshold and activation-based algorithms (which cover all previous approaches for obtaining competitive-ratios for the classic prophet secretary problem) yield a sub-optimal $(1-\epsilon)$-competition complexity of $\Theta\left(\frac{\ln(\frac{1}{\epsilon})}{\ln\ln(\frac{1}{\epsilon})}\right)$, which is strictly better than the class of single-threshold algorithms. Finally, we find that the $(1-\epsilon)$-competition complexity of general adaptive algorithms is $\Theta(\sqrt{\ln(\frac{1}{\epsilon})})$, which is in sharp contrast to $\Theta(\ln\ln(\frac{1}{\epsilon}))$ in the i.i.d. case.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation

    cs.GT 2026-02 conditional novelty 8.0 of 10

    A new 'manipulation potential' metric measures how many truthful additional votes equal one strategic lie; Borda Count has the smallest value among scoring rules, and Condorcet rules the largest.

  2. Posted Pricing and Competition in Large Markets

    cs.GT 2025-05 conditional novelty 7.0 of 10

    For i.i.d. valuations in the large-market limit, a fixed price captures at least 0.712 of optimal welfare for one item (tight), and optimal dynamic pricing needs only a constant factor more bidders to match the benchmark.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · cited by 2 Pith papers

  1. [1]

    Arnosti and W

    N. Arnosti and W. Ma. Tight guarantees for static thresho ld policies in the prophet secretary problem. Operations research, 71(5):1777–1788, 2023

    work page 2023

  2. [2]

    Y. Azar, A. Chiplunkar, and H. Kaplan. Prophet secretary : Surpassing the 1-1/e barrier. In Proceedings of the 2018 ACM Conference on Economics and Computation , pages 303–318, 2018

    work page 2018

  3. [3]

    Babaioff, K

    M. Babaioff, K. Goldner, and Y. A. Gonczarowski. Bulow-kl emperer-style results for welfare maximiza- tion in two-sided markets. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Di screte Algorithms, pages 2452–2471. SIAM, 2020

    work page 2020

  4. [4]

    Beyhaghi and S

    H. Beyhaghi and S. M. Weinberg. Optimal (and benchmark-o ptimal) competition complexity for addi- tive buyers over independent items. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 686–696, 2019

    work page 2019

  5. [5]

    Brustle, J

    J. Brustle, J. Correa, P. Duetting, and V. Verdugo. The co mpetition complexity of dynamic pricing. Mathematics of Operations Research , 2023. 17

    work page 2023

  6. [6]

    The Competition Complexity of Prophet Inequalities

    J. Brustle, J. Correa, P. Dütting, T. Ezra, M. Feldman, an d V. Verdugo. The competition complex- ity of prophet inequalities. CoRR, abs/2402.11084, 2024. doi: 10.48550/ARXIV.2402.11084. URL https://doi.org/10.48550/arXiv.2402.11084

    work page Pith review arXiv doi:10.48550/arxiv.2402.11084 2024

  7. [7]

    Bubna and A

    A. Bubna and A. Chiplunkar. Prophet inequality: Order se lection beats random order. In Proceedings of the 24th ACM Conference on Economics and Computation , pages 302–336, 2023

    work page 2023

  8. [8]

    Bulow and P

    J. Bulow and P. Klemperer. Auctions versus negotiations . American Economic Review , 86(1):180–94, 1996

    work page 1996

Show all 29 references
  1. [9]

    Cai and R

    L. Cai and R. R. Saxena. 99% revenue with constant enhance d competition. In Proceedings of the 22nd ACM Conference on Economics and Computation , pages 224–241, 2021

    2021

  2. [10]

    Chawla, J

    S. Chawla, J. D. Hartline, D. L. Malec, and B. Sivan. Mult i-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of com puting, pages 311– 320, 2010

    2010

  3. [11]

    Z. Chen, Z. Huang, D. Li, and Z. G. Tang. Prophet secretar y and matching: the significance of the largest item. arXiv preprint arXiv:2411.01191 , 2024

    2024 arXiv

  4. [12]

    Correa, P

    J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. V redeveld. Posted price mechanisms for a ran- dom stream of customers. In Proceedings of the 2017 ACM Conference on Economics and Comp utation, pages 169–186, 2017

    2017

  5. [13]

    Correa, R

    J. Correa, R. Saona, and B. Ziliotto. Prophet secretary through blind strategies. Mathematical Pro- gramming, 190(1):483–521, 2021

    2021

  6. [14]

    Cristi and B

    A. Cristi and B. Ziliotto. Prophet inequalities requir e only a constant number of samples. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 491–502, 2024

    2024

  7. [15]

    Derakhshan, E

    M. Derakhshan, E. Ryu, S. M. Weinberg, and E. Xue. Settli ng the competition complexity of additive buyers over independent items. arXiv preprint arXiv:2403.03937 , 2024

    2024 arXiv

  8. [16]

    Dütting, E

    P. Dütting, E. Gergatsouli, R. Rezvan, Y. Teng, and A. Ts igonias-Dimitriadis. Prophet secretary against the online optimal. In Proceedings of the 24th ACM Conference on Economics and Comp utation, pages 561–581, 2023

    2023

  9. [17]

    A. Eden, M. Feldman, O. Friedler, I. Talgam-Cohen, and S . M. Weinberg. The competition complexity of auctions: A bulow-klemperer result for multi-dimension al bidders. In Proceedings of the 2017 ACM Conference on Economics and Computation , pages 343–343, 2017

    2017

  10. [18]

    Ehsani, M

    S. Ehsani, M. Hajiaghayi, T. Kesselheim, and S. Singla. Prophet secretary for combinatorial auctions and matroids. In Proceedings of the twenty-ninth annual acm-siam symposium on discrete algorithms , pages 700–714. SIAM, 2018

    2018

  11. [19]

    Esfandiari, M

    H. Esfandiari, M. Hajiaghayi, V. Liaghat, and M. Monemi zadeh. Prophet secretary. SIAM Journal on Discrete Mathematics, 31(3):1685–1701, 2017

    2017

  12. [20]

    Ezra and T

    T. Ezra and T. Garbuz. The competition complexity of pro phet inequalities with correlations. arXiv preprint arXiv:2409.06868, 2024

    2024 arXiv

  13. [21]

    Feldman, O

    M. Feldman, O. Friedler, and A. Rubinstein. 99% revenue via enhanced competition. In Proceedings of the 2018 ACM Conference on Economics and Computation , pages 443–460, 2018

    2018

  14. [22]

    H. Fu, C. Liaw, and S. Randhawa. The vickrey auction with a single duplicate bidder approximates the optimal revenue. In Proceedings of the 2019 ACM Conference on Economics and Comp utation, pages 419–420, 2019. 18

    2019

  15. [23]

    H. Fu, Z. G. Tang, H. Wu, J. Wu, and Q. Zhang. Random order v ertex arrival contention resolution schemes for matching, with applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) . Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2021

    2021

  16. [24]

    Giambartolomei, F

    G. Giambartolomei, F. Mallmann-Trenn, and R. Saona. Pr ophet inequalities: separating random order from order selection. arXiv preprint arXiv:2304.04024 , 2023

    2023 arXiv

  17. [25]

    E. Harb. Fishing for better constants: The prophet secr etary via poissonization. arXiv preprint arXiv:2307.00971, 2023

    2023 arXiv

  18. [26]

    Lee and S

    E. Lee and S. Singla. Optimal online contention resolut ion schemes via ex-ante prophet inequalities. In 26th Annual European Symposium on Algorithms (ESA 2018) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018

    2018

  19. [27]

    Liu and C.-A

    S. Liu and C.-A. Psomas. On the competition complexity o f dynamic mechanism design. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Al gorithms, pages 2008–2025. SIAM, 2018

    2008

  20. [28]

    MacRury, W

    C. MacRury, W. Ma, and N. Grammel. On (random-order) onl ine contention resolution schemes for the matching polytope of (bipartite) graphs. Operations Research, 2024

    2024

  21. [29]

    bad” if all the random rewards (rewards of the sec ond type) arrive after time 2 k . The probability of a “bad

    R. B. Myerson. Optimal auction design. Mathematics of operations research , 6(1):58–73, 1981. A Proof of Case 1 of Lemma 4.1 Let pi = Pr[Vi ≤ x]. By the Union bound, it holds that Pr[OPT > x] ≤ ∑ i∈[n] Pr[Vi > x] = ∑ i∈[n] (1 − pi). (19) On the other hand, we note that since x...

    1981

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.