{"id":"8f8a8e05-63b3-4319-a598-0cda2e18d560","arxiv_id":"2411.13206","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"For a random zero-sum sequence, an online player can guarantee expected payoff proportional to the square root of its length, and this rate is worst-case optimal.","lead":"Players watch a randomly shuffled zero-sum list of numbers and may stop anytime to collect the sum of all unseen numbers; this paper proves the largest guaranteed expected payoff grows with the square root of the list length. The same rate is achieved by a simple rule that checks the running sum at the halfway point, and it is optimal in the worst case for any zero-sum multiset.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 6's reduction to the balanced binary case is not established as stated: zero entries break the count-balancing step, and the same-sign averaging limit is asserted without proof.","rationale":"The reader's weakest assumption correctly identifies the smoothing-convergence step in Section 6 as the main unformalized link in the general lower bound. I agree that the proof of Theorem 1 is conditional on making this step rigorous. My stress-test adds a second, more concrete defect in the same argument: the count-balancing step is literally false when the multiset contains zero entries, because n = n+ + n− is assumed and the stated number of cross-sign averaging steps cannot produce n+ = n− = n/2 if zeros are present. This does not disprove the theorem—small zero-containing examples such as {1,−1,0,0} still satisfy the lower bound—but it shows the proof as written does not cover the full statement of Theorem 1. The displayed asymptotic constant for Algorithm 3 in Section 5 is also wrong, as the reader noted, but that is a typo-level defect that does not threaten the Θ(√n) conclusion. The DP optimality of Algorithm 2 and the binomial identities in Appendix A are solid, and Lemma 4 is correct (in fact it follows from convexity of g), so the core mathematical architecture is credible. The appropriate verdict remains CONDITIONAL: the paper should be accepted only if the authors supply a rigorous treatment of the averaging limit and explicitly handle zero entries and odd n. Since this matches the reader's CONDITIONAL verdict, I recommend no change to that verdict.","tokens_in":9580,"tokens_out":20416,"duration_ms":225140,"concrete_test":"Run an exact-enumeration test on all zero-sum multisets of size n = 4 and n = 6 with entries in {−3,−2,−1,0,1,2,3}. For each multiset, compute f(M) = E[max(0, sum of a random half)] and check f(M) ≥ c·µ√n for a fixed positive constant, say c = 0.1; this tests Theorem 1 directly on the small cases the proof claims to cover. Then, for M = {1,−1,0,0}, verify that the Section 6 balancing assertion n+ = n− = n/2 is false (n+ = n− = 1 while n/2 = 2), showing the proof as written cannot handle zero entries. Finally, for the zero-free balanced example M = {1,2,3,10,−1,−2,−3,−10}, iteratively average the largest and smallest same-sign entries, recomputing f exactly by enumeration at each step; if f is not nonincreasing or the multisets do not converge to B = {±2.5 repeated 4 times}, the compactness step fails. This distinguishes a genuine counterexample to Theorem 1 from a fixable proof gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1 claims the Ω(µ√n) lower bound for every zero-sum multiset, but the proof in Section 6 has two load-bearing gaps. First, the section opens by setting n = n+ + n−, which silently excludes zero entries. For a zero-sum multiset with z > 0 zeros, after the (n+−n−)/2 cross-sign averaging steps the text asserts n+ = n− = n/2; in fact n+ = n− = (n−z)/2 < n/2, so the multiset is not the balanced binary case analyzed in Section 5. For example, M = {1,−1,0,0} has n+ = n− = 1 but n/2 = 2, and the stated balancing procedure cannot produce the multiplicities claimed. The conclusion f(M) ≥ f(B) with B = {µ^{n/2}, −µ^{n/2}} therefore does not follow for zero-containing multisets. Second, for the zero-free balanced case the proof says it is 'not hard to see' that repeated averaging of same-sign entries drives the multiset to B, relying on continuity and compactness. Continuity of f is true, but convergence of an arbitrary pairwise averaging process to the perfectly balanced multiset is not automatic and is not proved. Lemma 4 only gives f(M) ≥ f(M_k) along a chosen averaging sequence; without a demonstration that M_k → B, or that finite averaging can be stopped within ε while preserving the inequality direction, the chain f(M) ≥ f(B) is incomplete. The proof also assumes n even, with the odd case deferred. These are proof gaps rather than demonstrated counterexamples, but they mean the central claim is not yet established for all multisets named in Theorem 1.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a one-player stopping game in which a random permutation of a zero-sum multiset M of n reals is revealed one element at a time, and the player may stop at any point and collect the sum of the unrevealed elements. For the binary case M = {1^m, -1^m}, the paper gives three online algorithms: a threshold/lattice-path algorithm (Algorithm 1), an exactly optimal dynamic-programming algorithm (Algorithm 2), and a simple 'stop at the middle if the prefix sum is positive' algorithm (Algorithm 3). It proves that all three have expected payoff Θ(√n), with Algorithm 2 exactly optimal via a Bellman recurrence. For arbitrary zero-sum multisets, the paper claims that Algorithm 3 achieves expected payoff Ω(µ√n), where µ is the mean absolute value of the entries, and that this is worst-case optimal because the uniform sequence {µ^{n/2}, -µ^{n/2}} admits no algorithm with expected payoff better than O(µ√n). The binary analysis is the main solid contribution; the general-case proof is the part that needs attention.","tokens_in":9929,"tokens_out":16092,"duration_ms":160182,"significance":"If the general-case claim is completed, the paper would establish a clean and appealing asymptotic result: a very simple online algorithm attains the worst-case-optimal Θ(µ√n) expected payoff for every zero-sum multiset. The binary-case section is strong: the reflection-principle counts, the DP optimality equation, and the exact binomial identity of Lemma 3 are standard and check out, and the paper gives explicit constants and closed forms. I see no circularity in the argument: the lower and upper bounds come from independent combinatorial counts, and the threshold in Algorithm 1 is not fitted to force a target. However, the general-case proof in Section 6 has load-bearing gaps involving zero entries, the unproved convergence of the averaging process, and the omitted odd-n case. These gaps are fixable, but they currently prevent Theorem 1 from being established as stated.","major_comments":[{"comment":"The proof sets n = n+ + n−, which silently excludes zero entries, even though Theorem 1 is stated for every zero-sum multiset of reals and zeros are permitted. For M = {1, −1, 0, 0}, we have n+ = n− = 1 but n/2 = 2, so the balancing procedure cannot produce a multiset with n+ = n− = n/2, and the reduction to the binary multiset B fails. Since Algorithm 3 must also handle zero-containing multisets with µ > 0, this is a load-bearing gap, not a cosmetic omission.","section":"Section 6, first paragraph"},{"comment":"The proof that repeated pairwise averaging of same-sign entries drives the multiset to the balanced binary multiset B is not supplied. Continuity and compactness alone only yield a convergent subsequence of some averaging process; they do not show that the particular sequence obtained by arbitrary pairwise averages converges to B. Without such a convergence statement, or an explicit finite-step ε-approximation that preserves the inequality direction, the chain f(M) ≥ f(M_k) → f(B) is incomplete. A variance-decrease argument for the positive and negative parts would close this gap.","section":"Section 6, 'It is not hard to see...' paragraph"},{"comment":"The proof assumes n is even and explicitly omits the odd-n case ('the treatment for the case of odd n is similar, but somewhat more involved, and is therefore omitted'), while Theorem 1 claims the bound for arbitrary n. The stopping time n/2 is undefined for odd n, and the worst-case statement with n/2 copies of µ and −µ also presupposes even n. The theorem either needs a proof for odd n or a corrected statement with an explicit odd-n convention.","section":"Section 6, first paragraph and Theorem 1"}],"minor_comments":[{"comment":"The displayed asymptotic constant is misprinted: the exact expression 2m * C(2m-1,m-1)^2 / C(4m,2m) expands to sqrt(m/(2π)) + O(m^{-1/2}), equivalently sqrt(n/(8π)) + O(n^{-1/2}), not sqrt(m)/(2π) and not sqrt(n)/(8π). The table values for n = 32 and n = 64 agree with the corrected constant, so the error is in the displayed formula only.","section":"Section 5, asymptotic expansion after Eq. (7)"},{"comment":"The sentence 'the entries of T can be computed row by row, from top to bottom' appears to have the traversal direction backwards: the recurrence for T[i,j] uses T[i+1,j] and T[i,j+1], so the computation must proceed from larger i and j to smaller i and j, i.e., from the bottom rows upward.","section":"Section 4, Algorithm 2 description"},{"comment":"Algorithm 3 is analyzed in the dual version of the game (payoff is the sum of the revealed elements), whereas Theorem 1 is phrased for the original unrevealed-sum game. The two versions are related by a sign flip and, for zero-sum sequences, have equal expectations of the positive part and the negative part, but the paper should state this translation explicitly when applying the Section 5 analysis to Theorem 1.","section":"Sections 5 and 6"},{"comment":"The phrase 'equality is attained (apart from the hidden constant factor)' is imprecise; what is attained is the same asymptotic Θ-order, not equality of constants. The wording could be clarified.","section":"Theorem 1, last sentence"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the scope of a discrete-mathematics or algorithms venue, and the binary-case section is solid enough to be a useful standalone contribution. The advertised headline result, Theorem 1, is not yet fully proved because of the zero-entry, convergence, and odd-n gaps in Section 6. These are genuine proof gaps rather than demonstrated counterexamples, and I believe they are repairable within the manuscript's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read it. The binary-case analysis is the solid part: the game is a natural online stopping problem, and the paper gives three genuinely different algorithms, all with Θ(√n) expected payoff. The threshold argument via the reflection principle, the backward DP for the exact optimum, and the closed-form identity for the 'stop at n/2' rule all check out. Lemma 4 is correct—it is Jensen for the positive-part function—and the general strategy of averaging entries toward the balanced binary multiset is the right idea. The citation pattern is fine; the related work covers the relevant secretary/best-choice literature.\n\nThe general theorem, however, is not proved as stated. Section 6 opens with n = n+ + n−, which silently drops zero entries. If the multiset has z zeros, the cross-sign balancing stops at n+ = n− = (n−z)/2, not n/2, and the chain f(M) ≥ f(B) with B = {±μ each n/2 times} does not follow. This is fixable—you can average zeros with nonzero entries first, or track the zero count—but the printed proof covers only zero-free multisets. Second, the same-sign averaging limit is asserted ('it is not hard to see') with no explicit sequence. You need to specify an averaging process that drives each sign class to its mean, e.g., repeatedly average the current min and max (standard majorization), then use continuity. The claim is true, but the paper needs to say it. Finally, the odd-n case is waved off, and the displayed constant in Section 5 is wrong: the exact expression gives √(m/(2π)), not √m/(2π). Those are small defects.\n\nIf the Section 6 repairs are made, the paper delivers a clean new result. As is, a serious referee should send it back for revision rather than desk-reject: the binary results are worth having and the general claim is plausible and likely true. I'd encourage engagement.","headline":"Solid binary-case analysis, but the general theorem in Section 6 has fixable proof gaps around zero entries and the same-sign averaging limit.","tokens_in":10429,"tokens_out":11955,"would_cite":false,"duration_ms":124242,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","60G40","05A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A midpoint stopping rule achieves Θ(µ√n) expected payoff on every zero-sum multiset, and the rate is worst-case optimal.","keywords":["online algorithm","stopping time","optimality","asymptotic performance","lattice path","zero-sum sequence","random permutation","expected payoff"],"falsifier":"Compute the expected payoff of the midpoint rule for a zero-sum multiset with an equal number of positive and negative entries that is far from binary, such as {10,1,−1,−10}, and compare it with the balanced binary multiset of the same total absolute value; if f is ever larger after an averaging step, Lemma 4 fails. A more direct test is to compute the optimal expected payoff for the binary case with odd n, e.g., M having (n−1)/2 copies of 1 and (n+1)/2 copies of −1, for increasing odd n: if the growth is o(µ√n), then Theorem 1's claim for all n would be false.","tokens_in":9361,"feed_emoji":"🎲","tokens_out":12062,"duration_ms":102159,"temperature":0.7,"pith_summary":"This paper introduces a one-player stopping game: the entries of a random permutation of a zero-sum multiset are revealed one by one, and the player may stop at any time to collect the sum of the unrevealed entries. The main result is that a strategy which simply stops at the midpoint when the running sum is positive achieves expected payoff Ω(µ√n), where µ is the average absolute value of the entries, for any zero-sum multiset. In the binary case with only +1 and −1, the paper proves the tighter bound that three algorithms — a threshold rule, an exactly optimal dynamic program, and the midpoint rule — all have expected payoff Θ(√n). The general lower bound is shown to be worst-case optimal because the uniform binary multiset {µ,−µ} admits no strategy with expected payoff above O(µ√n).","feed_headline":"Stop at the midpoint: guaranteed Θ(√n) payoff on zero-sum inputs","feed_subtitle":"The payoff scales with the average absolute value and √n, and no strategy can beat that rate.","key_machinery":"The central object is the expected-payoff functional f(M) of the stop-in-the-middle rule, defined as the expectation of the positive part of the sum of the first n/2 revealed entries. The argument is carried by Lemma 4, which states that averaging any two distinct entries a < b into two copies of (a+b)/2 cannot increase f(M). This inequality, verified by a four-interval case check on the position of the remaining prefix sum, lets the proof deform an arbitrary zero-sum multiset into the binary multiset {µ,−µ} while only decreasing f. In the binary case, the key identity is the reflection principle (Lemma 2) counting lattice paths from (0,0) to (m,m) that reach the line y = x − t, which yields the tail probabilities behind both the threshold algorithm's lower bound and the general upper bound.","core_discovery":"The core discovery is a monotonicity lemma for the stop-in-the-middle payoff: replacing any two entries of the multiset by two copies of their average cannot increase the expected payoff of the midpoint rule. By repeatedly applying this replacement while preserving the zero-sum condition, any multiset can be pushed toward the balanced binary multiset with entries µ and −µ, each appearing n/2 times, and the expected payoff can only decrease along the way. Since the binary case is solved exactly by lattice-path counting — the reflection principle gives the probability that a random walk reaches a line y = x − t, yielding both the Θ(√n) lower and upper bounds — the bound transfers to all zero-sum multisets. The paper also computes the optimal strategy in the binary case via backwards dynamic programming, showing the optimal expected payoff is Θ(√n) and illustrating it on a deck of 52 cards.","pith_inferences":["The averaging lemma may extend to other payoff functions, such as the maximum of the running sum or the absolute value of the remaining sum, suggesting that the √n rate is a generic feature of online stopping on exchangeable zero-sum sequences.","The gap between the optimal payoff and the simple midpoint rule in the binary case (e.g., 2.62 vs 1.54 for n=52) indicates that more sophisticated strategies could improve the constant in the general case, even though the order of growth is fixed.","Because the paper's proof omits the odd n case, a natural next step is to derive the exact odd-n analogue; if the bound fails there, the theorem as stated needs an additional assumption, and if it holds, the smoothing argument likely has a cleaner formulation.","The worst-case optimality only benchmarks against the uniform binary sequence; for specific structured inputs (for example, many small values and one large value), the achievable payoff might be substantially larger than µ√n, which could be exploited."],"forward_implications":["In the binary ±1 case, the optimal expected payoff is Θ(√n), so no stopping rule can do asymptotically better than stopping when the path first reaches a line at distance Θ(√n) from the diagonal.","The simple threshold algorithm still delivers Θ(√n) when the length n is known only within a factor of two, so the stopping rule is robust to uncertainty about the horizon.","For arbitrary zero-sum multisets, the stop-in-the-middle rule gives a worst-case optimal Ω(µ√n) payoff with no bookkeeping, making it practical for online trading or simulation settings.","The dynamic programming algorithm for the binary case yields the exact optimal strategy in quadratic preprocessing time, and the paper's example suggests the optimal expected payoff on 52 cards is 2.62 units.","The tail-probability argument used for the upper bound applies to any online decision rule, establishing that the √n rate is inherent to the game rather than an artifact of the proposed strategies."],"supporting_citations":[{"why":"supplies the reflection principle used to count lattice paths reaching a fixed line, which yields both the lower bound for Algorithm 1 and the upper bound for all algorithms in the binary case.","marker":"[10, Ch. 1.3]"},{"why":"gives the tail-sum identity that bounds the expected payoff of any stopping rule by the sum of probabilities that the payoff exceeds each threshold t, the key to the upper bound.","marker":"[7, Lemma 2.9]"},{"why":"provides the Vandermonde convolution used to evaluate the combinatorial sum in Lemma 3, giving the closed form of the midpoint rule's expected payoff.","marker":"[4, Section 5.2]"}],"fun_headline_variants":["Midpoint rule wins: Θ(√n) payoff on any zero-sum multiset","Optimal stopping on zero-sum permutations: Θ(√n) payoff","Zero-sum stopping game: midpoint rule achieves Θ(√n)","Stop at midpoint: Θ(√n) guarantee for zero-sum sequences"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The general-case lower bound relies on an unproved smoothing step: after Lemma 4 shows averaging two entries cannot increase the expected payoff, the paper asserts without proof that the payoff functional is continuous and that repeated averaging of same-sign entries drives the multiset to the balanced binary multiset, so the lower bound only follows if this limiting argument is valid; the proof also assumes n is even and omits the odd-n case.","fun_headline_variants_meta":{"raw":{"variants":["Midpoint rule wins: Θ(√n) payoff on any zero-sum multiset","Optimal stopping on zero-sum permutations: Θ(√n) payoff","Zero-sum stopping game: midpoint rule achieves Θ(√n)","Stop at midpoint: Θ(√n) guarantee for zero-sum sequences"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000644,"raw_usage":{"total_tokens":3003,"prompt_tokens":1027,"completion_tokens":1976,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":643,"completion_tokens_details":{"reasoning_tokens":1896}},"tokens_in":643,"tokens_out":1976,"duration_ms":13866,"temperature":1.0,"reasoning_tokens":1896,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:43:37.597538+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the expected payoff of the midpoint rule for a zero-sum multiset with an equal number of positive and negative entries that is far from binary, such as {10,1,−1,−10}, and compare it with the balanced binary multiset of the same total absolute value; if f is ever larger after an averaging step, Lemma 4 fails. A more direct test is to compute the optimal expected payoff for the binary case with odd n, e.g., M having (n−1)/2 copies of 1 and (n+1)/2 copies of −1, for increasing odd n: if the growth is o(µ√n), then Theorem 1's claim for all n would be false.","supporting_citations":[],"review_version":1}