{"id":"0b559954-ae6b-4f89-b4a4-7e18d434f176","arxiv_id":"2411.10892","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The (1-epsilon)-competition complexity of prophet secretary is Theta(ln(1/epsilon)) for single-threshold algorithms, Theta(ln(1/epsilon)/ln ln(1/epsilon)) for time-based and activation-based algorithms, and Theta(sqrt(ln(1/epsilon))) for fully adaptive algorithms.","lead":"This paper determines how many extra copies of each prize an online algorithm needs in the prophet secretary problem to capture almost all of the best prize's value. It proves that simple threshold rules need Theta(ln(1/epsilon)) copies, while fully adaptive algorithms need only Theta(sqrt(ln(1/epsilon))) copies, a new separation between arrival models.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.2's lower bound for general algorithms uses a false Stirling estimate: (k!)²/(2k)! ≥ 1/(4k) fails for k≥3; the bad-order probability is exponentially smaller. This is a real gap in the proof of Theorem 5.1's Ω(√ln(1/ε)) bound, though the construction appears repairable with a 4^{-k} bound.","rationale":"The reader's verdict of CONDITIONAL identifies exactly the load-bearing weakness: Lemma 5.2's proof of the general lower bound relies on the false Stirling-based inequality (18). I re-derived the probability of the 'bad' permutation: it is (k!)²/(2k)!, which for k=3 is 1/20, below the claimed 1/(4k)=1/12, and asymptotically ~√(πk)/4^k. Since this inequality is the only step that converts the bad-order probability into the claimed √ε/(4k) gap in E[ALG], the lower bound proof as written fails. This is a genuine correctness gap in the central Theorem 5.1, so the paper should not be accepted without correction. However, the underlying construction is evidently repairable: even the very crude valid lower bound 4^{-k} dominates p=e^{-√ln(1/ε)} when k=½√ln(1/ε), so the hard instance still separates k=O(√ln(1/ε)) from the (1−ε) benchmark. The upper-bound algorithms in Sections 3–5.1 appear sound, and the other complexity classes are not affected. Thus CONDITIONAL is the right verdict, and my read does not change it.","tokens_in":23351,"tokens_out":17848,"duration_ms":169422,"concrete_test":"Check the exact values: compute (k!)²/(2k)! for k=3,4,5 and compare with 1/(4k) and with 4^{-k}; confirm (18) is false. Then redo the final comparison in Lemma 5.2 with P_k=(k!)²/(2k)! (or the safe lower bound P_k≥4^{-k}) for k=⌈½√ln(1/ε)⌉: verify that P_k > 3e^{-√ln(1/ε)} for all sufficiently small ε, e.g., by evaluating the asymptotic ratio P_k/e^{-√ln(1/ε)} as ε→0. If the inequality holds, the construction survives and Theorem 5.1's lower bound is repairable as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The lower bound for general algorithms (Lemma 5.2, Eq. (18)) asserts Pr[bad]=(k!)²/(2k)! ≥ 1/(4k), via Stirling. This is false: for k=3, (3!)²/6! = 36/720 = 0.05 < 1/12 ≈ 0.083, and asymptotically (k!)²/(2k)! ~ √(πk)/4^k, exponentially smaller than 1/(4k). The proof then concludes E[ALG] ≤ 1+√ε − √ε·Pr[bad] ≤ 1+√ε − √ε/(4k), and needs this to fall below (1−ε)E[OPT]. Since the displayed probability bound is false, the submitted proof that k=½√ln(1/ε) copies are insufficient does not go through. The gap is load-bearing because it is the only lower-bound argument for the Θ(√ln(1/ε)) result. It appears repairable: using the cruder valid bound Pr[bad] ≥ 4^{-k} still gives 4^{-k}=e^{-(ln4/2)√ln(1/ε)}, which dominates 3p=3e^{-√ln(1/ε)} for small ε, so the hard instance can likely be fixed without changing the theorem. No similar gap was found in the upper bounds or in the other algorithm classes.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":23416,"tokens_out":14183,"duration_ms":141558,"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":[{"comment":"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.","section":"Section 5.2, Eq. (18), Lemma 5.2"}],"minor_comments":[{"comment":"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.","section":"Section 5.1, Eq. (13)"},{"comment":"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.","section":"Section 5.1, Eq. (12)"},{"comment":"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.","section":"Section 5.2, Lemma 5.2"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main issue is localized to Lemma 5.2 and is likely fixable without changing the theorem or the high-level construction. I recommend major revision rather than rejection. I did not find similar gaps in the upper-bound proofs or in the lower bounds for the other algorithm classes; those parts appear sound. The paper is a good fit for the journal and, once the Stirling bound is corrected, would make a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's my read on the Ezra-Garbuz prophet secretary competition complexity paper. The headline is that it fills in the random-arrival column of the competition complexity table for four algorithm classes: single-threshold Theta(ln(1/eps)), time-based and activation-based Theta(ln(1/eps)/ln ln(1/eps)), and general Theta(sqrt(ln(1/eps))). If the main theorem is right, it is a genuine resolution of a question that was open for the random-order model, and the contrast with the i.i.d. Theta(ln ln(1/eps)) is a real insight.\n\nThe paper has real value beyond the main theorem. The upper-bound proofs are careful and constructive: the adaptive algorithm in Section 5.1 is implementable because the switching time depends only on arrival times, and the stochastic domination argument is standard but handled cleanly. The time-based and activation-based characterizations are genuinely tight and they sharpen the earlier work on i.i.d. and block arrivals. The related-work discussion is accurate, and the paper does not oversell its implications.\n\nThe soft spot is the one the stress test flagged: Lemma 5.2's lower bound for general algorithms. Equation (18) asserts (k!)^2/(2k)! >= 1/(4k) using Stirling. For k=3, the left side is 0.05 and 1/(4k) is about 0.083; asymptotically the left side is ~sqrt(pi*k)/4^k, exponentially smaller. That inequality is plainly false, and it is the load-bearing step that produces the Omega(sqrt(ln(1/eps))) lower bound. The proof as written does not go through. The good news is that the construction appears repairable: replacing 1/(4k) with 4^{-k} still gives the required domination of 3p = 3e^{-sqrt(ln(1/eps))} for small eps, so the theorem itself is plausible and likely correct. But the submitted proof has a real gap, and the authors need to fix it before the result should be cited as proven.\n\nOther issues are minor: the comment that '3*ell is the expectation' in the Hoeffding application should read 2*ell, and one inequality in equation (12) holds only for k >= 2. Neither affects the upper bounds.\n\nWho is this for? Anyone working on prophet inequalities, competition complexity, or online auctions with resource augmentation. The results are central enough that the paper deserves a serious referee, and I would accept it into the review process. My recommendation is major revision: require the authors to repair the Stirling bound in Lemma 5.2, or to provide a different lower-bound argument for Theorem 5.1.\n\nI would bring this to a reading group, and I would cite it once the lower-bound proof is fixed.","headline":"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.","tokens_in":24198,"tokens_out":2023,"would_cite":false,"duration_ms":20199,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60G40","91B26"],"pacs":[],"model":"deepseek-v4-flash","headline":"For the prophet secretary problem, fully adaptive algorithms have (1−ε)-competition complexity Θ(√ln(1/ε)), with time-based and single-threshold classes strictly worse.","keywords":["prophet secretary","competition complexity","resource augmentation","random order arrivals","threshold algorithms","adaptive algorithms","optimal stopping","online algorithms"],"falsifier":"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.","tokens_in":22884,"feed_emoji":"🎯","tokens_out":11943,"duration_ms":116176,"temperature":0.7,"pith_summary":"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.","feed_headline":"Adaptive algorithms need √ln(1/ε) copies to beat the prophet","feed_subtitle":"The extra-copy requirement drops quadratically when thresholds adapt to arrivals, versus time-based rules.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies the stopping-probability inequalities and blind-strategy machinery used to prove the upper bounds.","marker":"[13]"},{"why":"It introduces the prophet secretary model that the paper augments with independent copies.","marker":"[19]"},{"why":"It gives the earlier i.i.d. and block-arrival competition complexity results and the single-threshold lower bound that the paper extends and compares against.","marker":"[6]"},{"why":"It introduces the competition complexity measure for dynamic pricing and proves that exact competition complexity is unbounded, motivating the (1−ε) relaxation.","marker":"[5]"},{"why":"It introduces the activation-based algorithm class whose competition complexity the paper characterizes in its appendices.","marker":"[11]"},{"why":"It provides the single-threshold (1−1/e) baseline without copies that justifies the ε≤1/e regime.","marker":"[18]"}],"fun_headline_variants":["Adaptive algorithms halve prophet gap with √ln(1/ε) copies","Copies needed drops to √ln(1/ε) for adaptive prophet strategies","Prophet edge: adaptivity slices copy cost to √ln(1/ε)","√ln(1/ε) copies suffice for adaptive prophet winning","Adaptive threshold beats prophet with Θ(√ln(1/ε)) copies"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive algorithms halve prophet gap with √ln(1/ε) copies","Copies needed drops to √ln(1/ε) for adaptive prophet strategies","Prophet edge: adaptivity slices copy cost to √ln(1/ε)","√ln(1/ε) copies suffice for adaptive prophet winning","Adaptive threshold beats prophet with Θ(√ln(1/ε)) copies"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000148,"raw_usage":{"total_tokens":1237,"prompt_tokens":1043,"completion_tokens":194,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":659,"completion_tokens_details":{"reasoning_tokens":91}},"tokens_in":659,"tokens_out":194,"duration_ms":2885,"temperature":1.0,"reasoning_tokens":91,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:12:47.457895+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Correa, R","cited_arxiv_id":null,"evidence_quote":"It supplies the stopping-probability inequalities and blind-strategy machinery used to prove the upper bounds."},{"cited_title":"Esfandiari, M","cited_arxiv_id":null,"evidence_quote":"It introduces the prophet secretary model that the paper augments with independent copies."},{"cited_title":"The Competition Complexity of Prophet Inequalities","cited_arxiv_id":"2402.11084","evidence_quote":"It gives the earlier i.i.d. and block-arrival competition complexity results and the single-threshold lower bound that the paper extends and compares against."},{"cited_title":"Brustle, J","cited_arxiv_id":null,"evidence_quote":"It introduces the competition complexity measure for dynamic pricing and proves that exact competition complexity is unbounded, motivating the (1−ε) relaxation."},{"cited_title":"Prophet Secretary and Matching: the Significance of the Largest Item","cited_arxiv_id":"2411.01191","evidence_quote":"It introduces the activation-based algorithm class whose competition complexity the paper characterizes in its appendices."},{"cited_title":"Ehsani, M","cited_arxiv_id":null,"evidence_quote":"It provides the single-threshold (1−1/e) baseline without copies that justifies the ε≤1/e regime."}],"review_version":1}