A Stopping Game on Zero-Sum Sequences

Adrian Dumitrescu; Arsenii Sagdeev

REVIEW 3 major objections 4 minor 11 references

A Stopping Game on Zero-Sum Sequences

T0 review · 3 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 A midpoint stopping rule achieves Θ(µ√n) expected payoff on every zero-sum multiset, and the rate is worst-case optimal.

desk verdict Solid binary-case analysis, but the general theorem in Section 6 has fixable proof gaps around zero entries and the same-sign averaging limit. read the letter →

arxiv 2411.13206 v1 pith:DMCSZE3F submitted 2024-11-20 cs.DM math.CO

Adrian Dumitrescu , Arsenii Sagdeev This is my paper · ORCID

classification cs.DMmath.CO MSC 68W2760G4005A15

keywords onlinealgorithmstoppingtimeoptimalityasymptoticperformancelatticepathzero-sumsequencerandompermutationexpectedpayoff

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 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).

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

If 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.

Referee Report

3 major / 4 minor

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.

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 (3)

[Section 6, first paragraph] 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 6, 'It is not hard to see...' paragraph] 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 6, first paragraph and Theorem 1] 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.

minor comments (4)

[Section 5, asymptotic expansion after Eq. (7)] 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 4, Algorithm 2 description] 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.
[Sections 5 and 6] 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.
[Theorem 1, last sentence] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; the Section 6 gaps are proof gaps, not circular reasoning.

full rationale

The paper's derivation chain is not circular. The binary-case results are self-contained: Algorithm 1's lower bound is a direct consequence of the reflection-principle count Prob(E_t) and a lower bound on that probability, while its upper bound is a union bound over all stopping thresholds; Algorithm 2's optimality follows from a dynamic-programming recurrence with known boundary values; Algorithm 3's expected payoff is exactly counted via binomial products and evaluated by Vandermonde's identity. The general-case claim in Section 6 uses Lemma 4, an independently proved convexity inequality, and then compares the averaged multiset to the balanced binary multiset whose payoff was already computed in Section 5. No parameter is fitted to force a predicted outcome, no prediction is equivalent by construction to an input, and the paper contains no load-bearing self-citations or imported uniqueness theorem. The skeptical concerns about Section 6—the asserted continuity/compactness averaging step, the unhandled zero entries in n+ = n− = n/2 balancing, and the omitted odd-n case—are genuine proof gaps or correctness risks, not circularity: failing to prove convergence to the balanced multiset is a missing argument rather than a reduction of the conclusion to the assumption. Since none of the identified issues makes a claimed result equal its own inputs by definition or by fitting, the appropriate circularity score is 0.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

No data are fitted and no new entities are posited. The only hand-chosen parameter is the threshold t in Algorithm 1, which does not affect the asymptotic rate. The main hidden load is the unproved smoothing-convergence step for the general case and the even-n restriction.

free parameters (1)

threshold t in Algorithm 1 = floor(sqrt((m+1)/2)), order Θ(√m)
Chosen by hand to balance the reflection-principle probability; the Θ(√n) result holds for any t that is a constant multiple of √m, so this parameter is algorithmic rather than fitted to data.

assumptions (6)

standard math Reflection principle for lattice paths: the number of paths from (0,0) to (m,m) reaching y=x-t is C(2m,m-t).
Used in Lemma 2 and Equation (1) to lower-bound Algorithm 1.
standard math Vandermonde's identity.
Used in Appendix A to prove Lemma 3, the closed form for Algorithm 3's payoff.
standard math Stirling series expansion for binomial coefficients.
Used to convert exact binomial sums into Θ(√n) bounds in Sections 3 and 5; one such expansion in Section 5 is stated incorrectly.
domain assumption All n! permutations of the multiset are equally likely.
This is the definition of the game; all probability calculations condition on it.
standard math Backward induction dynamic programming is valid for finite-horizon optimal stopping.
Algorithm 2's optimality in Section 4 relies on Bellman-style equations with transition probabilities conditional on the remaining multiset.
ad hoc to paper f(M) is continuous and repeated pairwise averaging converges to the balanced binary multiset.
The Section 6 general proof asserts this smoothing-convergence step without a formal argument; the lower bound depends on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Stopping Game on Zero-Sum Sequences." pith.science (2026). https://pith.science/paper/DMCSZE3F

@misc{pith2026241113206,
  author       = {Pith},
  title        = {Pith review of: A Stopping Game on Zero-Sum Sequences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DMCSZE3F}},
  note         = {Machine review of arXiv:2411.13206}
}

abstract

We introduce and analyze a natural game formulated as follows. In this one-person game, the player is given a random permutation $A=(a_1,\dots, a_n)$ of a multiset $M$ of $n$ reals that sum up to $0$, where each of the $n!$ permutation sequences is equally likely. The player only knows the value of $n$ beforehand. The elements of the sequence are revealed one by one and the player can stop the game at any time. Once the process stops, say, after the $i$th element is revealed, the player collects the amount $\sum_{j=i+1}^{n} a_j$ as his/her payoff and the game is over (the payoff corresponds to the unrevealed part of the sequence). Three online algorithms are given for maximizing the expected payoff in the binary case when $M$ contains only $1$'s and $-1$'s. $\texttt{Algorithm 1}$ is slightly suboptimal, but is easier to analyze. Moreover, it can also be used when $n$ is only known with some approximation. $\texttt{Algorithm 2}$ is exactly optimal but not so easy to analyze on its own. $\texttt{Algorithm 3}$ is the simplest of all three. It turns out that the expected payoffs of the player are $\Theta(\sqrt{n})$ for all three algorithms. In the end, we address the general problem and deal with an arbitrary zero-sum multiset, for which we show that our $\texttt{Algorithm 3}$ returns a payoff proportional to $\sqrt{n}$, which is worst case-optimal.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 10 canonical work pages

[1]

secretary problem

Yuan Shih Chow, Sigaiti Moriguti, Herbert Robbins, and Stephen M. Samuels, Optimal selection based on relative rank (the “secretary problem”), Israel Journal of Mathematics 2(2) (1964), 81--90

work page 1964
[2]

Ferguson, Who solved the secretary problem? Statistical Science 4(3) (1989), 282–296

Thomas S. Ferguson, Who solved the secretary problem? Statistical Science 4(3) (1989), 282–296

work page 1989
[3]

Nicholas Georgiou, Ma gorzata Kuchta, Micha Morayne, and Jaros aw Niemiec, On a universal best choice algorithm for partially ordered sets, Random Structures and Algorithms 32(3) (2008), 263--273

work page 2008
[4]

Graham, Donald E

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, Reading, MA, 1990

work page 1990
[5]

Moser, Canadian Mathematical Bulletin 3(1) (1960), 35--39

Irwin Guttman, On a problem of L. Moser, Canadian Mathematical Bulletin 3(1) (1960), 35--39

work page 1960
[6]

Larsen and Morris L

Richard J. Larsen and Morris L. Marx, An Introduction to Probability and its Applications, Prentice--Hall, Englewood Cliffs, New Jersey, 1985

work page 1985
[7]

Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2nd edition, Cambridge University Press, 2017

2017
[8]

Leo Moser, On a problem of Cayley, Scripta Mathematica 22 (1956), 289--292

work page 1956

Show all 11 references

[9]

Frederick Mosteller, Fifty Challenging Problems in Probability with Solutions, Addison-Wesley, Reading, MA, 1965

1965
[10]

Sri Gopal Mohanty, Lattice Path Counting and Applications, Academic Press, New York, 1979

1979
[11]

James Preater, The best-choice problem for partially ordered objects, Operations Research Letters 25(4) (1999), 187--190

1999

Pith tools

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

[1] [1]

secretary problem

Yuan Shih Chow, Sigaiti Moriguti, Herbert Robbins, and Stephen M. Samuels, Optimal selection based on relative rank (the “secretary problem”), Israel Journal of Mathematics 2(2) (1964), 81--90

work page 1964

[2] [2]

Ferguson, Who solved the secretary problem? Statistical Science 4(3) (1989), 282–296

Thomas S. Ferguson, Who solved the secretary problem? Statistical Science 4(3) (1989), 282–296

work page 1989

[3] [3]

Nicholas Georgiou, Ma gorzata Kuchta, Micha Morayne, and Jaros aw Niemiec, On a universal best choice algorithm for partially ordered sets, Random Structures and Algorithms 32(3) (2008), 263--273

work page 2008

[4] [4]

Graham, Donald E

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, Reading, MA, 1990

work page 1990

[5] [5]

Moser, Canadian Mathematical Bulletin 3(1) (1960), 35--39

Irwin Guttman, On a problem of L. Moser, Canadian Mathematical Bulletin 3(1) (1960), 35--39

work page 1960

[6] [6]

Larsen and Morris L

Richard J. Larsen and Morris L. Marx, An Introduction to Probability and its Applications, Prentice--Hall, Englewood Cliffs, New Jersey, 1985

work page 1985

[7] [7]

Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2nd edition, Cambridge University Press, 2017

2017

[8] [8]

Leo Moser, On a problem of Cayley, Scripta Mathematica 22 (1956), 289--292

work page 1956