arxiv: 2605.11539 · v1 · submitted 2026-05-12 · 🧮 math.PR · math.CO

Recognition: no theorem link

A noisy min-max game on trees

Gourab Ray, Omer Angel, Yinon Spinka

Pith reviewed 2026-05-13 01:37 UTC · model grok-4.3

classification 🧮 math.PR math.CO

keywords noisy min-max gamed-ary treezero-sum gamevalue convergencepercolationdistributional iterationfixed pointsrandom cookies

0 comments

The pith

In a noisy min-max game on d-ary trees with random ±1 cookies, the first player's guaranteed value V_n converges in distribution for d at least 3 as n tends to infinity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies a zero-sum game on an infinite d-ary tree where each edge carries an independent random cookie of +1 or -1. Two players alternate moves down the tree for n turns each, with full knowledge of all cookies, and the first player's payoff equals the sum of cookies collected along the path. V_n is defined as the largest signed sum the first player can force. The central results establish that V_n stays tight for d equal to 2, converges in distribution for d at least 3, and converges almost surely for d at least 15. These limits arise from percolation arguments that work when the branching factor is large and from iterations on the distribution of possible values when the branching factor is small.

Core claim

As n tends to infinity the value V_n of the n-round game is tight for d=2, converges in distribution for d greater than or equal to 3, and converges almost surely for d greater than or equal to 15. The proofs combine percolation-type arguments for large d with iterations on distributions and interval arithmetic for small d; for d=2 the iteration admits a continuum of fixed points, in contrast to the case d greater than or equal to 3.

What carries the argument

The distributional iteration that tracks the law of the remaining game value after one move, together with percolation arguments that identify subtrees where the first player can force positive or negative sums.

If this is right

For d at least 15 the limiting random variable V is almost surely finite and well-defined.
For d at least 3 the sequence V_n converges in distribution to a random limit whose law satisfies a fixed-point equation derived from the one-step iteration.
Double-exponential tail decay holds for the distribution of V_n under the stated regimes.
The existence of a continuum of fixed points for the d=2 iteration produces qualitatively different behavior from the unique fixed point that appears for d at least 3.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The sharp threshold between tightness at d=2 and distributional convergence at d=3 suggests that d=2 may be a critical case whose limiting behavior, if it exists, could be described by a different scaling.
Numerical iteration of the distributional map for small d could be used to approximate the limiting law when convergence in distribution is proved.
The almost-sure convergence for large d makes it possible to define a limiting optimal strategy that depends only on the realized cookie configuration.
The same percolation-plus-iteration technique may apply to variants in which the cookie distribution is not symmetric or the game length is random.

Load-bearing premise

The cookies on the edges are i.i.d. uniform on plus one and minus one, and both players know the entire infinite tree in advance.

What would settle it

A direct computation or simulation for d=2 that exhibits V_n with variance growing without bound or with positive probability of escaping any fixed interval would falsify the tightness claim.

Figures

Figures reproduced from arXiv: 2605.11539 by Gourab Ray, Omer Angel, Yinon Spinka.

**Figure 1.** Figure 1: A 2 round game on the binary tree. Each edge is labeled with its cookie; each vertex is laveled with the value V2(x). The leaves are 0 by definition, though we study below also other assignments of leaf values. d ≥ 3. For d = 2 there is strong dependence on boundary conditions, which does not occur for d ≥ 3. For example, simulations show the following: if one places on the leaves values of 0 or 2 accordin… view at source ↗

read the original abstract

We study a noisy version of a min-max type zero-sum game on the $d$-ary tree. Each edge of the tree is assigned an i.i.d.\ cookie, distributed uniformly on $\{+1,-1\}$. The game is played as follows: starting at the root, two players alternate turns in choosing a child to move to, with the game ending after each player took $n$ turns. Both players have full knowledge of the cookies on the whole tree. The cookies along the traversed edges are picked up and placed in a shared cookie jar. The first player's payoff is the sum of the cookies in the cookie jar, while the second player pays that sum. The value $V_n$ of the $n$-round game is the largest signed sum which can be guaranteed by the first player. We analyze the value $V_n$ and show that as $n \to \infty$, the value is tight for $d=2$, converges in distribution for $d \ge 3$, and converges almost surely for $d \ge 15$. Along the way, we prove various tightness and double exponential tail decay results. The analysis is a mix of percolation-type arguments for large $d$, and iterations on distributions combined with interval arithmetic for small $d$. For $d=2$ we prove the existence of a continuum of fixed points for this iteration, highlighting surprising qualitative differences with the case $d \ge 3$. The question of convergence for $d=2$ remains open.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper pins down the limiting behavior of the game value V_n on d-ary trees, with tightness at d=2, distributional convergence for d>=3, and a.s. convergence for d>=15.

read the letter

This paper pins down the limiting behavior of the game value V_n on d-ary trees, with tightness at d=2, distributional convergence for d>=3, and a.s. convergence for d>=15. The analysis mixes percolation arguments for large d with distributional iterations plus interval arithmetic for small d, and it flags a continuum of fixed points only when d=2. Along the way it gives concrete tightness and double-exponential tail bounds that tie the game to branching-process ideas. These are the concrete new statements, and they are stated precisely enough to be checked against the methods described. The model uses i.i.d. uniform cookies and full information by definition, so that part introduces no extra assumption. The proofs rely on external tools like percolation rather than circular fitting, which keeps the logic clean. The open question on actual convergence for d=2 is noted honestly and does not undermine the fixed-point distinction they do prove. The interval-arithmetic step for small d is a practical verification tool; it would be stronger with explicit error bounds or shared code, but it is not a load-bearing flaw on its own. This work is aimed at probabilists who already care about stochastic games on trees or distributional fixed points. A specialist in percolation or branching processes would get direct value from the limits and the d=2 contrast, while a general reader would not. The paper shows clear thinking on its own terms and engages the relevant literature without overclaiming. I would send it to peer review.

Referee Report

2 major / 3 minor

Summary. The paper analyzes a zero-sum min-max game on the d-ary tree in which each edge carries an i.i.d. uniform {+1,-1} cookie. Two players with perfect information alternate n moves each; the first player’s payoff is the signed sum of cookies collected along the path. The value V_n is the largest payoff the first player can guarantee. The main theorems establish that, as n→∞, V_n is tight when d=2, converges in distribution when d≥3, and converges almost surely when d≥15. The proofs combine percolation arguments for large d with an iterative distributional analysis (supplemented by interval-arithmetic verification) for small d; for d=2 the iteration is shown to possess a continuum of fixed points, while convergence itself remains open.

Significance. If the stated limits hold, the work supplies a sharp dimensional threshold for the asymptotic behavior of perfect-information noisy games on trees. The percolation-based tail bounds for large d and the rigorous interval-arithmetic treatment of the distributional iteration for small d constitute concrete technical strengths. The qualitative distinction between the d=2 case (continuum of fixed points) and d≥3 is of independent interest and may inform related models in percolation and game theory on graphs.

major comments (2)

[§4] §4 (percolation argument for a.s. convergence): the threshold d≥15 is obtained by a first-moment calculation on a suitably defined bad event; it would be useful to see whether the same argument can be pushed below 15 or whether a matching lower bound construction exists, since the gap between distributional convergence (d≥3) and a.s. convergence (d≥15) is currently large.
[§5.2] §5.2 (distributional iteration for d=3,4): the interval-arithmetic verification that the iteration contracts the diameter of the support is central to the distributional-convergence claim; the manuscript should state explicitly the machine precision and the number of iterations performed, so that the bound can be independently reproduced.

minor comments (3)

[Abstract / Introduction] The abstract states that “various tightness and double-exponential tail decay results” are proved along the way; these should be listed with precise theorem numbers in the introduction.
[§2] Notation for the law of the cookie configuration and for the value function V_n is introduced without a dedicated “Notation” paragraph; a short table or list would improve readability.
[Conclusion] The open question of a.s. convergence for d=2 is mentioned only in the abstract and the final paragraph; a brief discussion of the technical obstacle (e.g., lack of uniform integrability or failure of the contraction) would help the reader.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the positive evaluation and constructive comments. We provide point-by-point responses to the major comments below.

read point-by-point responses

Referee: [§4] §4 (percolation argument for a.s. convergence): the threshold d≥15 is obtained by a first-moment calculation on a suitably defined bad event; it would be useful to see whether the same argument can be pushed below 15 or whether a matching lower bound construction exists, since the gap between distributional convergence (d≥3) and a.s. convergence (d≥15) is currently large.

Authors: The referee correctly identifies that our almost sure convergence result relies on a first-moment bound yielding d ≥ 15. This threshold is the smallest integer where the expected number of bad events decays sufficiently fast for the Borel-Cantelli lemma to apply. While we agree that closing the gap to the distributional convergence at d ≥ 3 would be valuable, achieving a lower threshold would necessitate either a more delicate analysis of the bad event or a different approach altogether. We believe the current result is already of interest as it provides a concrete (albeit not optimal) dimensional threshold for almost sure convergence. We do not plan to modify the threshold in the revision but will add a brief remark noting this as an open question. revision: partial
Referee: [§5.2] §5.2 (distributional iteration for d=3,4): the interval-arithmetic verification that the iteration contracts the diameter of the support is central to the distributional-convergence claim; the manuscript should state explicitly the machine precision and the number of iterations performed, so that the bound can be independently reproduced.

Authors: We thank the referee for pointing this out. To ensure reproducibility, we will explicitly state in the revised manuscript the machine precision used and the number of iterations performed in the interval-arithmetic verification for the cases d=3 and d=4. revision: yes

standing simulated objections not resolved

Pushing the almost sure convergence threshold below d=15 or providing a matching lower bound construction for the percolation argument.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives limiting statements for V_n (tightness at d=2, distributional convergence for d≥3, a.s. convergence for d≥15) via percolation-type arguments for large d and explicit distributional iterations with interval arithmetic for small d. These steps apply standard external tools to the i.i.d. cookie model and perfect-information game definition; no load-bearing claim reduces by construction to a fitted parameter, self-referential definition, or self-citation chain. The continuum of fixed points for d=2 is proved as a qualitative distinction from d≥3 rather than assumed. The analysis is self-contained against the stated model assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The model is built on standard probabilistic assumptions about the cookies and perfect information; no free parameters or new entities are introduced in the abstract.

axioms (2)

domain assumption Cookies on edges are i.i.d. uniform on {+1, -1}
Explicitly stated as the random input to the game.
domain assumption Both players know the entire tree of cookies before play begins
Part of the game definition in the abstract.

pith-pipeline@v0.9.0 · 5571 in / 1390 out tokens · 62119 ms · 2026-05-13T01:37:39.093645+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

[1]

Artificial Intelligence , volume=

Asymptotic properties of minimax trees and game-searching procedures , author=. Artificial Intelligence , volume=. 1980 , publisher=

work page 1980
[2]

, author=

A limit law for the root value of minimax trees. , author=. Electronic Communications in Probability [electronic only] , volume=

work page
[3]

Random Minimax Game Trees

Devroye, Luc and Kamoun, Olivier. Random Minimax Game Trees. Random Discrete Structures. 1996

work page 1996
[4]

and Bandyopadhyay, Antar , TITLE =

Aldous, David J. and Bandyopadhyay, Antar , TITLE =. Ann. Appl. Probab. , FJOURNAL =. 2005 , NUMBER =. doi:10.1214/105051605000000142 , URL =

work page doi:10.1214/105051605000000142 2005
[5]

Neumaier, A. , year=. Interval Methods for Systems of Equations , publisher=

work page
[6]

arXiv preprint arXiv:2409.02660 , year=

A min-max random game on a graph that is not a tree , author=. arXiv preprint arXiv:2409.02660 , year=

work page arXiv
[7]

Minimax functions on

Martin, James B and Stasi. Minimax functions on. Combinatorics, Probability and Computing , volume=. 2020 , publisher=

work page 2020
[8]

Galton--

Holroyd, Alexander E and Martin, James B , journal=. Galton--. 2021 , publisher=

work page 2021
[9]

The art of mathematics:

Bollob. The art of mathematics:. 2006 , publisher=

work page 2006