{"id":"208b2afe-604f-4353-bcbe-d9fface366bd","arxiv_id":"2602.18756","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The asymptotic k-selection prophet inequality ratio is an explicit function of the reward distribution's extreme value index, yielding a 1 - O(log k / k) worst-case guarantee and a divergent-regret caveat for the CE heuristic.","lead":"This paper derives an explicit formula for how much of a prophet's total reward an online algorithm can guarantee when it must accept up to k of n i.i.d. offers, with the ratio depending on the tail index of the reward distribution. It also shows that a widely used simple heuristic matches the optimal leading behavior but can incur unbounded regret when the number of offers grows much faster than the capacity.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Fixed-point limit in Prop 6.2 drops non-vanishing n(g_k(n)-g_k(n-1)) term; central ACR formula is not established without a convergence-rate proof.","rationale":"The reader's weakest assumption identifies the fixed-point limit in Proposition 6.2 as the core gap. My concern is a more concrete manifestation of that gap: the proof's equation (13) silently drops the n(g_k(n)-g_k(n-1)) term. This is not a matter of style; without a rate-of-convergence or compactness argument, the passage from the asymptotic identity (18) to the deterministic recursion (19) is invalid, and Theorem 3.1's gamma in (0,1) formula is unsupported. I independently checked that the k=1 case matches the known Kennedy-Kertz benchmark and that the recursion algebra for v_k is internally consistent, so the formula itself is plausible. The gamma>=1 issue is real but secondary, since the paper's main positive claims focus on gamma in (0,1). Given that the central theorem depends on a missing analytic step, conditional acceptance is appropriate: the authors should supply a rigorous proof of boundedness and convergence of the normalized DP values, or an alternative derivation of (6).","tokens_in":31875,"tokens_out":10745,"duration_ms":89143,"concrete_test":"Take F with Pareto tail \\bar F(x)=x^{-1/gamma}, gamma=1/2, so U(n)=n^gamma and the DP recursion in Lemma 6.1 can be evaluated exactly. For k=2 and n=10^3..10^7, compute g_2(n)=V^dp(n,2)/U(n) and check (a) whether n(g_2(n)-g_2(n-1))->0, and (b) whether g_2(n) converges to v_2/(1-gamma)^gamma with v_2=(1+sqrt(5))/2. If (a) fails, equation (13) is false as written. To decide the theorem rather than the proof, re-derive (18) using the exact recursion without dropping the n-difference term and prove by a contraction argument that the extra term is o(1); if no such proof exists, formula (6) remains unsupported for arbitrary F in the Frechet domain.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Proposition 6.2 is the only proof of the gamma in (0,1) case of Theorem 3.1, and its fixed-point step is not justified. In the proof, after defining g_k(n)=V^dp(n,k)/U(n), equation (13) asserts V^dp(n,k)-V^dp(n-1,k)=gamma/n U(n) g_k(n)[1+o(1)]. The exact expansion from U(n-1)/U(n)=1-gamma/n+o(1/n) is U(n)g_k(n)-U(n-1)g_k(n-1)=U(n)[gamma/n g_k(n) + (g_k(n)-g_k(n-1)) + o(1/n)]. After dividing by U(n)/n, the extra term n(g_k(n)-g_k(n-1)) appears. The proof drops it without showing it is o(1). Convergence of g_k(n) to a finite limit does not imply this (e.g. g_k(n)=c+(-1)^n/n converges but n(g_k(n)-g_k(n-1)) does not vanish). No boundedness, rate, or compactness of the normalized DP values is established, and the [1+o(1)] in (17) is commuted with the nonlinear power Delta_k^{-(1-gamma)/gamma} without uniform control. Therefore equations (18)-(19) identify at most a necessary condition for subsequential limits; the asserted convergence of the full sequence to v_k, and hence formula (6), lacks proof. The same gap is inherited by Corollary 3.3 and the large-k bound. Separately, the gamma not in (0,1) line of (6) is hard to interpret when gamma>=1, since mu_{n,k} and V^dp are both infinite for every n; the ratio ACR_k(F) is not defined in the usual sense.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the i.i.d. k-unit prophet inequality in the large-market regime, aiming to characterize the instance-dependent asymptotic competitive ratio ACR_k(F) under the extreme value condition. Theorem 3.1 asserts that ACR_k(F) depends on F only through its extreme value index gamma, with an explicit formula for gamma in (0,1) involving a recursively defined sequence v_k, and equals 1 otherwise. From this the authors derive a large-k worst-case guarantee 1 - (log k)/(8k)(1+epsilon), improving on the fixed-threshold guarantee 1 - 1/sqrt(2 pi k). The second half analyzes the Certainty-Equivalent (CE) heuristic, showing that its asymptotic ratio has the same leading-order large-k expansion as the optimal DP, but that its additive regret can diverge when k = o(n), via Theorem 4.4 and Proposition 4.5. The paper also discusses competition complexity.","tokens_in":32358,"tokens_out":6010,"duration_ms":58163,"significance":"If the main results are correct, this is a substantial contribution: an explicit, distribution-dependent asymptotic characterization for the multi-unit prophet inequality, a new large-k worst-case guarantee, and the first systematic analysis of the CE heuristic outside the fluid-scaling regime. The extreme-value reduction is elegant and the DP-recursion approach is natural. The paper is also commendable for focusing on instance-dependent rather than worst-case guarantees, and for making sharp distinctions between ratio and additive-regret performance. However, the proof of the central DP asymptotic, Proposition 6.2, contains a significant convergence gap, and the divergence result for the CE heuristic relies on an unproved positivity assertion backed only by a missing numerical figure. These issues must be repaired before the paper's main claims can be accepted.","major_comments":[{"comment":"The central fixed-point step is not justified. Writing g_k(n)=V^dp(n,k)/U(n), the exact expansion of V^dp(n,k)-V^dp(n-1,k) contains the term U(n)(g_k(n)-g_k(n-1)) in addition to (gamma/n)U(n)g_k(n-1)+o(U(n)/n). After dividing by U(n)/n, this yields gamma g_k(n-1) + n(g_k(n)-g_k(n-1)) + o(1). The proof drops the term n(g_k(n)-g_k(n-1)) without showing it is o(1); convergence of g_k(n) does not imply this. Consequently, Eqs. (18)-(19) identify only a necessary condition for subsequential limits, and the claimed convergence of the full sequence g_k(n) to v_k/(1-gamma)^gamma is not established. No boundedness, compactness, or convergence-rate argument is supplied, and the [1+o(1)] factors are commuted with the nonlinear power Delta_k^{-(1-gamma)/gamma}. Since Theorem 3.1, Corollary 3.3, and Proposition 3.2 all rest on Proposition 6.2, the gamma-in-(0,1) ACR formula is currently unproven.","section":"Proposition 6.2, Eqs. (13)–(19)"},{"comment":"The line '1, otherwise' is not meaningful for gamma >= 1. As the paper itself notes, gamma >= 1 occurs only when E[X] = infinity. In that case both V^dp(n,k) and the prophet value mu_{n,k} are infinite for every n, so the ratio V^dp(n,k)/mu_{n,k} is not defined in the usual sense. The statement needs either an explicit extended-real convention, a normalization, or a restriction of the theorem to the cases where the ratio is well-defined. This is not merely cosmetic, because the theorem is claimed for all extreme-value distributions on R_+.","section":"Theorem 3.1, Eq. (6), gamma >= 1"},{"comment":"The theorem's divergence conclusion depends on the positivity of c_gamma, but positivity is not proved. The proof states: 'by numerical validation, we can further know c_gamma > 0. See Figure 3.' Figure 3 is absent from the manuscript, and numerical validation cannot serve as a proof in a mathematical paper. Moreover, the proof's final step writes V^dp(n,k)-V^ce(n,k)=Theta((n/k)^gamma), which would require U(n) to be comparable to n^gamma; for a general regularly varying quantile U with index gamma, only divergence of the gap follows from c_gamma>0, not this exact order. The overclaim should be corrected or proved.","section":"Theorem 4.4 and proof (Section B.4)"},{"comment":"The proposition asserts a joint limit behavior V^dp(n,k)-V^ce(n,k)=Omega((n/k)^gamma) whenever k=o(n), but its proof relies on the claim that 'the large-k expansions for the competitive ratios remain valid along any sequence with k=o(n)' and on a statement that the recursions simplify 'in a way that is uniform.' No uniformity estimates or verification of the interchange of limits are provided. Since Theorem 3.1 and Theorem 4.1 are fixed-k asymptotic results, applying them along k=k(n)->infinity requires additional uniform control that is not established. As stated, the lower bound is not proven.","section":"Proposition 4.5 and proof (Section B.5)"}],"minor_comments":[{"comment":"The notation for the CE value function alternates between V^ce, V^{CE}, and V CE. Please standardize.","section":"Section 6.2, Eq. (8)"},{"comment":"In the definition of a_n = F^{-1}(1-1/(en)) - F^{-1}(1-1/n), the suffix 'x>1' appears to be a typo; presumably it should be n>1 or e>1.","section":"Theorem 6.9, gamma=0 formula"},{"comment":"The proof says 'existence follows from boundedness of hat g_j(.)' but boundedness is not established. A short argument or a citation to a uniform bound is needed.","section":"Proof of Proposition 6.6"},{"comment":"The proof refers to 'Figure 3' for the numerical positivity check, but no Figure 3 is included in the manuscript. If the authors intend to retain the numerical check as supporting evidence, the figure must be included; ideally the positivity of c_gamma should be proved analytically.","section":"Theorem 4.4 proof"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a timely and important problem, and the claimed results would be very interesting. However, the main DP asymptotic is presently unsupported because of the missing convergence argument in Proposition 6.2, and the CE divergence theorem relies on an unproved numerical positivity check. These are load-bearing, but they seem potentially repairable: one could try to prove convergence rates for g_k(n), or use monotonicity and a Tauberian argument, and one could attempt to prove c_gamma > 0 analytically for gamma in (0,1). I recommend major revision rather than rejection, but I would not accept the paper in its current form. I also suggest the authors re-examine the gamma >= 1 case, where the ratio is undefined without additional conventions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the main formula is probably correct, but the proof of the central theorem has a gap that needs fixing before I'd trust it. The CE-heuristic part is the most novel and is worth reading on its own.\n\nWhat's new: an explicit EVT-based characterization of ACR_k(F) for k>1, the log k/k worst-case bound, and a closed form for the CE heuristic outside the fluid-scaling regime, with a divergent-regret caveat. The k=1 limit matches Kennedy-Kertz, the numerics look sensible, and the competition-complexity section is a nice bonus.\n\nWhere it's soft: the proof of Proposition 6.2, which is the only proof of the gamma in (0,1) case, drops the n(g_k(n)-g_k(n-1)) term when going from the exact DP expansion to (13). Convergence of g_k(n) doesn't make that term vanish; you need a rate or compactness. The [1+o(1)] in (17) is then commuted with a nonlinear power, again without uniform control. So (18)-(19) only give a necessary condition for subsequential limits, and the full sequence convergence to v_k isn't established. This gap is inherited by Theorem 3.1 and the large-k corollaries.\n\nAlso, the gamma>=1 line of (6) is hard to interpret: those distributions have infinite mean, so both V^dp and mu_{n,k} are infinite and the ratio isn't defined. Theorem 4.4's c_gamma>0 is delegated to numerical validation with a missing Figure 3. Proposition 4.5 assumes the large-k expansions hold uniformly along k=o(n), which isn't proved.\n\nWho this is for: people working on prophet inequalities, DP asymptotics, or EVT-based online allocation. It deserves a serious referee; the subject is important and the formula is likely right. But I would not accept as is. The referee should insist on a rigorous fixed-point argument (or an explicit convergence-rate assumption), a treatment of gamma>=1, and a proof or clear computational claim for c_gamma.\n\nRecommendation: send it to peer review, with the expectation of major revision.","headline":"Main formula is probably right, but the proof of the central theorem has a real fixed-point gap; the CE-heuristic analysis is the most novel part and worth engaging.","tokens_in":32780,"tokens_out":3561,"would_cite":false,"duration_ms":32060,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60G40","60G70","90C40","62G32"],"pacs":[],"model":"deepseek-v4-flash","headline":"The optimal online k-selection policy in large i.i.d. markets has an asymptotic competitive ratio that depends only on k and the reward distribution's extreme value index γ.","keywords":["prophet inequalities","multi-secretary problem","extreme value index","asymptotic competitive ratio","certainty-equivalent heuristic","fixed-threshold policy","regular variation","competition complexity"],"falsifier":"For a distribution with power-law tail 1−F(x)=x^{-1/γ} (γ=0.7), evaluate the exact dynamic-program recursion for fixed k across n=10^2,…,10^7. If V^dp(n,k)/F^{-1}(1−1/n) does not converge to the claimed v_k/(1−γ)^γ, or converges to a different constant for some k, the closed-form formula fails; the power-law tail makes the recursion exact for every n.","tokens_in":31759,"feed_emoji":"📈","tokens_out":8383,"duration_ms":74140,"temperature":0.7,"pith_summary":"This paper tries to prove an instance-dependent answer to the classic k-unit prophet inequality for i.i.d. nonnegative rewards when the number of offers n is large. It claims that for any distribution satisfying the extreme value condition, the optimal online policy's asymptotic competitive ratio depends on the distribution only via its extreme value index γ, and it gives an explicit closed form for that ratio. Since the worst case over γ occurs at γ=1/2, this yields a uniform guarantee of at least 1−(log k)/(8k)(1+ε) for all sufficiently large k, improving on the tight 1−1/√(2πk) guarantee of fixed-threshold policies. The paper further characterizes the certainty-equivalent heuristic, finds that its leading-order competitive ratio matches the optimum for large k, but shows that its additive regret relative to the optimal dynamic program diverges when k=o(n).","feed_headline":"One tail index fixes online k-selection prophet gap","feed_subtitle":"One heavy-tail parameter determines how close an online policy can get to the prophet; worst-case loss is about log k/(8k).","key_machinery":"The central object is the one-step dynamic-programming recursion for the optimal value V^dp(n,k), together with its analogue for the certainty-equivalent heuristic. The proof normalizes V^dp(n,k) by U(n)=F^{-1}(1−1/n), the high quantile of the reward distribution; regular variation of U with index γ converts the update into a difference equation in the normalized values. The threshold τ_{n,k}=V^dp(n−1,k)−V^dp(n−1,k−1) enters the tail integral ∫_τ^∞ (1−F(u)) du, and the standard tail-integration result for regularly varying tails rewrites that integral as a power of the normalized threshold. Passing to limits yields the deterministic recursion solved by v_k. The whole reduction replaces the u","core_discovery":"Theorem 3.1 asserts that for F with extreme value index γ∈(0,1), ACR_k(F) = (1−γ)^{1−γ} v_k Γ(k)/Γ(k+1−γ), and that ACR_k(F)=1 for γ∉(0,1); here v_1=1 and for k>1, v_k−v_{k−1} is the unique positive root of x^{1/γ}+v_{k−1}x^{1/γ−1}−1=0. The argument normalizes the optimal dynamic-program values by the high quantile F^{-1}(1−1/n), which is regularly varying with index γ, and shows that the normalized values satisfy a deterministic recursion in the limit. The same machinery yields a closed form for the certainty-equivalent heuristic's ratio and, by Stirling-type expansions, the large-k expansion 1−γ(1−γ) log k/(2k)+O(1/k) for both policies. This expansion is what produces the tight worst-case","pith_inferences":["Editorial inference: if the convergence and compactness step for normalized value functions can be supplied, the same tail-index reduction should extend to broader tail classes, suggesting a general principle that only the tail index governs large-market online allocation.","Editorial inference: because the worst case occurs at γ=1/2, the hard instances are heavy-tailed with finite mean but infinite variance; practical policies that know only γ, not the full distribution, may inherit near-optimality.","Editorial inference: the divergent-regret result warns that fluid-scaling conclusions about the CE heuristic do not transfer to fixed instances with k much smaller than n; in such cases additive regret, not just the competitive ratio, should be tracked."],"forward_implications":["Large-market optimal competitive ratio becomes computable for any heavy-tailed distribution: evaluate a one-dimensional recursion and gamma functions.","The worst-case guarantee over distributions satisfying the extreme value condition is asymptotically 1−(log k)/(8k), beating the tight 1−1/√(2πk) bound of static thresholds; the worst case sits at γ=1/2.","The certainty-equivalent heuristic asymptotically matches the optimal policy's leading-order performance ratio for large k, even without the fluid-scaling assumption k∝n.","When k=o(n), the CE heuristic's additive regret relative to the optimal DP diverges like a positive power of n/k, so a near-1 competitive ratio can coexist with unbounded additive loss.","In heavy-tailed domains, both DP and CE need only a (1+O(log k/k)) inflation of market size to compensate their multiplicative loss."],"fun_headline_variants":["Heavy-tail index sets optimal k-selection prophet ratio","Prophet gap shrinks to log k/k for heavy-tailed rewards","One tail parameter fixes online prophet performance","Extreme value index dictates prophet inequality loss"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the normalized dynamic-program value functions actually converge as n grows, so one may pass to the limit inside the nonlinear recursion; the proof establishes this only for subsequences, not for every heavy-tailed distribution it covers.","fun_headline_variants_meta":{"raw":{"variants":["Heavy-tail index sets optimal k-selection prophet ratio","Prophet gap shrinks to log k/k for heavy-tailed rewards","One tail parameter fixes online prophet performance","Extreme value index dictates prophet inequality loss"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000291,"raw_usage":{"total_tokens":1616,"prompt_tokens":899,"completion_tokens":717,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":643,"completion_tokens_details":{"reasoning_tokens":667}},"tokens_in":643,"tokens_out":717,"duration_ms":7208,"temperature":1.0,"reasoning_tokens":667,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T21:51:59.601871+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a distribution with power-law tail 1−F(x)=x^{-1/γ} (γ=0.7), evaluate the exact dynamic-program recursion for fixed k across n=10^2,…,10^7. If V^dp(n,k)/F^{-1}(1−1/n) does not converge to the claimed v_k/(1−γ)^γ, or converges to a different constant for some k, the closed-form formula fails; the power-law tail makes the recursion exact for every n.","supporting_citations":[],"review_version":1}