{"id":"f942941b-4b04-4f33-b516-e9a8213487c3","arxiv_id":"2607.05085","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Constant-competitive multi-choice min-prophet needs O(min{ln ln M, ln n}) expected selections in random order (tight up to low-order logs even for i.i.d.), Ω(n/ln n) for adversarial order, and n for any deterministic budget.","lead":"For the hard minimization version of prophet inequalities, constant competitiveness is possible with only O(min{ln ln M, ln n}) expected choices under random order, but needs nearly linear choices under adversarial order. This quantifies a sharp exponential gap between order models and between expected vs deterministic choice budgets.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly flags the continuous-distribution hypothesis of Algorithm 1 as the most delicate modelling assumption, yet the paper already supplies the standard fix (perturbation or randomization) and the subsequent analysis is unaffected. That assumption is therefore not load-bearing for the asymptotic claims. All other steps—threshold existence, Jensen on the harmonic number of records, the heavy-tailed interval partition, and the deterministic n-1 impossibility—check out under direct inspection. Consequently the ACCEPT verdict stands; the only residual gap is the open question (already stated by the authors) of whether the adversarial lower bound can be improved when ln ln M = o(n).","tokens_in":22901,"tokens_out":472,"duration_ms":21127,"concrete_test":"Re-derive the competitive-ratio lower bound of Claim 5.6 for the critical interval index k = T (where T = ln ln β/(2 ln ln ln β)-1) starting from the explicit integral for C_k in Claim 5.5 and the Pr(S_k ∩ G) ≥ 1/ln ln β bound; confirm that the powers of (ln ln β) cancel to leave a pure ln ln β factor. If the cancellation fails by more than a constant, the Ω(ln ln M / ln ln ln M) term weakens.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims (Theorems 3.1, 4.1, 5.1, 6.1) rest on standard known-distribution prophet assumptions and carefully constructed heavy-tailed instances. The continuous-distribution hypothesis for the threshold algorithm (Section 4) is explicitly handled by the paper via atom perturbation or randomization at atoms; the record-minima analysis then applies to the relevant samples under random order. The i.i.d. lower-bound partition into doubly-logarithmic intervals (Claims 5.4–5.6) and the adversarial nearly-linear construction both close cleanly, with the CR blow-up calculations cancelling exactly as claimed. No hidden circularity, missing case, or unjustified interchange of limits appears in the load-bearing arguments.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.5","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.","tokens_in":23067,"tokens_out":1005,"duration_ms":51560,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Abstract / §1"},{"comment":"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.","section":"§4"},{"comment":"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.","section":"Appendix 10"},{"comment":"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.","section":"§6"},{"comment":"Figures 1 and 2 are referenced but not rendered in the supplied manuscript; either include them or remove the references.","section":"§5 / §6"},{"comment":"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.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a clean, self-contained contribution that fits well in a theory venue (SODA/STOC/EC or a journal such as MOR/SICOMP). No concerns about novelty disclosure or citation patterns. The open problems in the conclusion are genuine and well-posed; they do not weaken the present claims."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles the multi-choice complexity of the min-prophet (cost prophet) problem. The new quantitative facts are sharp: adversarial order needs Ω(n/ln n) expected choices for constant competitiveness, while random order (and even i.i.d.) needs only O(min{ln ln M, ln n}) and the matching lower bound is Ω(min{ln ln M / ln ln ln M, ln n / ln ln n}). Deterministic budgets of n-1 choices are useless even for i.i.d.; the multi-unit extension for i.i.d. is a clean bonus.\n\nWhat works well is the elementary threshold + record-minima upper bound (Section 4) and the carefully engineered heavy-tailed constructions that force the algorithm to hit every doubly-logarithmic interval (Section 5) or nearly every early variable (Section 3). The competitive-ratio calculations cancel cleanly, the continuous-distribution hypothesis is handled by the usual atom-perturbation argument, and the appendices supply the missing expectation calculations. No circularity, no free parameters, and the citation pattern is appropriate for the subfield.\n\nSoft spots are minor and already flagged by the authors: the upper bound needs known distributions and a threshold that can be realized (or randomized at atoms), and the multi-unit analysis is only for i.i.d. Those do not undermine the main theorems. The open questions they list (adversarial upper bound in terms of M, deterministic budget in terms of M) are natural next steps rather than holes.\n\nThis is for people who work on prophet inequalities, online selection, or optimal stopping. The proofs are self-contained and short enough for a reading group. I would send it to peer review without hesitation; a serious referee will find the arguments solid and the gaps exponential enough to be robust. Engage with it.","headline":"Clean, nearly tight multi-choice complexity for min-prophet: exponential adversarial/random-order gap and expected-vs-deterministic separation, with complete proofs.","tokens_in":23644,"tokens_out":471,"would_cite":true,"duration_ms":8829,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","60G40","91B26"],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["prophet inequality","min prophet","cost prophet","multi-choice","prophet secretary","random order","competitive analysis","optimal stopping"],"falsifier":"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.","tokens_in":23826,"feed_emoji":"📉","tokens_out":674,"duration_ms":5224,"temperature":0.7,"pith_summary":"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.","feed_headline":"Min-prophet needs only log-log choices in random order","feed_subtitle":"Adversarial order still forces nearly linear selections for any constant ratio","key_machinery":"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.","core_discovery":"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.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Min-prophet constant ratio needs only O(min{ln ln M, ln n}) random-order picks","Random-order multi-choice min-prophet: O(log log M) expected selections suffice","Constant-competitiveness min-prophet with log-log choices under random arrival","i.i.d. min-prophet still requires nearly Ω(log log M) expected multi-choices","Adversarial min-prophet forces Ω(n/ln n) expected selections for any constant ratio"],"cache_read_input_tokens":9472,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Min-prophet constant ratio needs only O(min{ln ln M, ln n}) random-order picks","Random-order multi-choice min-prophet: O(log log M) expected selections suffice","Constant-competitiveness min-prophet with log-log choices under random arrival","i.i.d. min-prophet still requires nearly Ω(log log M) expected multi-choices","Adversarial min-prophet forces Ω(n/ln n) expected selections for any constant ratio"]},"model":"grok-4.5","effort":"low","cost_usd":0.00602,"raw_usage":{"total_tokens":1632,"prompt_tokens":895,"num_sources_used":0,"completion_tokens":131,"cost_in_usd_ticks":60200000,"prompt_tokens_details":{"text_tokens":895,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":606,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":895,"tokens_out":131,"duration_ms":5073,"temperature":1.0,"reasoning_tokens":606,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T09:02:17.807046+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}