Totalitarian random Tug-of-War games in graphs

Fernando Charro; Marcos Ant\'on; Peiyong Wang

arxiv: 1907.09219 · v1 · pith:BPISTSYZnew · submitted 2019-07-22 · 🧮 math.AP

Totalitarian random Tug-of-War games in graphs

Marcos Ant\'on , Fernando Charro , Peiyong Wang This is my paper

Pith reviewed 2026-05-24 18:15 UTC · model grok-4.3

classification 🧮 math.AP

keywords tug-of-war gamesgraphsgame valueinfinity harmonic functionsviscosity solutionscomparison principlerandom gamesJensen extremal equations

0 comments

The pith

A variant of random Tug-of-War on graphs in which one player can force the opponent to choose the next position for a fixed payoff possesses a value.

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

The paper examines a random Tug-of-War game played on graphs where one participant, at each turn, may either run a standard random round or instead grant the opponent the right to pick the new position in return for a fixed payment. It sets out to establish that this game admits a value. A reader would care because the construction is tied directly to Jensen's extremal equations, which underpin the uniqueness proof for infinity-harmonic functions. The argument proceeds by combining a discrete comparison principle, viscosity techniques, and probabilistic reasoning. The result therefore supplies an existence statement for the value in this modified discrete setting.

Core claim

In the totalitarian random Tug-of-War game on graphs, one player holds the option at every step to play a classical random Tug-of-War round or, alternatively, to receive a fixed payoff while allowing the opposing player to select the subsequent position; the paper proves that this game possesses a value by means of a discrete comparison principle together with viscosity methods and probabilistic arguments, and notes its connection to Jensen's extremal equations that appear in the uniqueness theory for infinity-harmonic functions.

What carries the argument

The totalitarian choice mechanism, which at each turn lets one player decide between a standard random Tug-of-War step and granting the opponent position selection in exchange for a fixed payoff.

If this is right

The value of the game exists and can be characterized on any finite graph under the stated rules.
The value function satisfies a discrete version of Jensen's extremal equation.
Existence of the value supplies a new discrete model whose continuous limit may recover infinity-harmonic functions.
The same comparison and viscosity arguments extend to related graph games that incorporate similar choice options.

Where Pith is reading between the lines

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

The existence result may furnish a new discrete approximation scheme for infinity-Laplace equations on graphs that could be tested numerically against known continuum solutions.
Because the totalitarian option introduces an asymmetric control, the construction could be compared with other asymmetric tug-of-war variants already studied in the continuous setting.
If the discrete value converges under suitable graph refinement, the limit object would satisfy a continuous Jensen-type equation whose uniqueness properties remain to be verified.

Load-bearing premise

The discrete comparison principle continues to hold after the payoff structure and move rules are altered by the introduction of the totalitarian choice option.

What would settle it

A concrete finite graph together with payoff parameters on which the two players' value functions fail to coincide, or on which the discrete comparison principle ceases to apply to the modified game.

Figures

Figures reproduced from arXiv: 1907.09219 by Fernando Charro, Marcos Ant\'on, Peiyong Wang.

**Figure 1.** Figure 1: Game positions of the game on a segment with multiple running nodes. a solution of which is vi = ǫ min{(n+ 1)−i, i} −K. On the other hand, since ui is a solution to (2.2) by hypothesis, it is in particular a supersolution and bounded from above due to the first part of the proof. Then, by Theorem 1.2 it follows that vi ≤ ui for all i ∈ N and the proof is finished. In order to prove that the discrete Total… view at source ↗

**Figure 2.** Figure 2: Game positions after relabeling the original nodes xi as yi−k, for k ≤ i ≤ n + 1. Proof. We argue by strong mathematical induction. Let Pi be the property stated in the lemma, that is: Pi : “For any pair of strategies SI , SII such that Player I allows Player II to move at xi while Player II moves towards the terminal node x0 at all xj with 1 ≤ j ≤ i, we have that uk = F0 + k ǫ for all 0 ≤ k ≤ i”. Assume P… view at source ↗

**Figure 3.** Figure 3: Game positions of the Y-game with multiple running nodes. 3.2. Star-shaped graphs. Now we study the Totalitarian Tug-of-War game in a star-shaped graph consisting of an arbitrary number of (arbitrarily long) graph segments glued together at a common endpoint. The simplest of these is the Y graph resulting from gluing together three graph segments, see [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗

read the original abstract

In this work we discuss a random Tug-of-War game in graphs where one of the players has the power to decide at each turn whether to play a round of classical random Tug-of-War, or let the other player choose the new game position in exchange of a fixed payoff. We prove that this game has a value using a discrete comparison principle and viscosity tools, as well as probabilistic arguments. This game is related to Jensen's extremal equations, which have a key role in Jensen's celebrated proof of uniqueness of infinity harmonic functions.

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

The paper adds a 'totalitarian' choice rule to random Tug-of-War on graphs and claims a value exists, but the comparison principle step for the modified payoffs is the part that needs the closest check.

read the letter

The main new piece is the game rule where one player can, at any turn, take a fixed payoff and force the opponent to pick the next vertex instead of running the usual random Tug-of-War step. The authors prove the game still has a value and link the result to Jensen's extremal equations that appear in his uniqueness proof for infinity-harmonic functions. They work with the standard toolkit of discrete comparison principles, viscosity solutions, and probabilistic arguments on graphs. That connection to the infinity-Laplace literature is the clearest point of contact with prior work. The setup is cleanly stated and the variant is genuinely different from the symmetric Tug-of-War versions already in the literature. The proofs appear to follow the expected lines for this subfield. The soft spot is whether the discrete comparison principle extends directly once the payoff structure includes the new binary choice. That choice changes the dynamic programming equation and the monotonicity properties that comparison arguments usually rely on. The abstract invokes the principle without spelling out the adaptation, so the existence claim rests on that extension being valid. If the full paper only cites the standard version without re-checking the altered case, that would be a gap worth flagging. This is aimed at people already working on stochastic games or discrete infinity-harmonic functions on graphs. A reader in that niche could use the example to test how rule changes affect value functions, but it is unlikely to matter outside that circle. The work is formally grounded enough and engages the literature honestly, so it should go to peer review rather than a desk reject. Referees can verify whether the comparison principle holds for the totalitarian modification.

Referee Report

1 major / 0 minor

Summary. The manuscript introduces a variant of random Tug-of-War games on graphs, called totalitarian, in which one player may at each turn elect either a classical random Tug-of-War round or a fixed payoff while forcing the opponent to select the next vertex. It claims to prove that this game possesses a value, established via a discrete comparison principle together with viscosity techniques and probabilistic arguments, and relates the value function to Jensen's extremal equations that appear in the uniqueness proof for infinity-harmonic functions.

Significance. If the existence result is rigorously established, the work enlarges the class of discrete games whose values are known to exist and supplies an additional discrete model whose continuous limit is governed by Jensen-type equations; the explicit combination of comparison-principle, viscosity, and probabilistic methods would constitute a methodological contribution provided the necessary adaptations are supplied.

major comments (1)

[Abstract / existence argument] The existence of the value is asserted to follow from a discrete comparison principle, yet the abstract supplies no indication that the principle has been re-established or suitably modified for the altered dynamic-programming equation and monotonicity properties induced by the new binary choice (the option to accept a fixed payoff and cede vertex selection). Standard comparison arguments for Tug-of-War rely on payoffs determined solely by the two players' moves; the totalitarian modification changes both the equation and the ordering used in the comparison, so the applicability of the unmodified principle is load-bearing for the central claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for identifying an important point of clarification regarding the discrete comparison principle. We address the major comment below and outline the revisions we will make.

read point-by-point responses

Referee: [Abstract / existence argument] The existence of the value is asserted to follow from a discrete comparison principle, yet the abstract supplies no indication that the principle has been re-established or suitably modified for the altered dynamic-programming equation and monotonicity properties induced by the new binary choice (the option to accept a fixed payoff and cede vertex selection). Standard comparison arguments for Tug-of-War rely on payoffs determined solely by the two players' moves; the totalitarian modification changes both the equation and the ordering used in the comparison, so the applicability of the unmodified principle is load-bearing for the central claim.

Authors: We agree that the abstract is too terse on this point and does not explicitly signal the necessary adaptations. In the body of the manuscript (Section 3), we prove a discrete comparison principle that is modified to handle the new dynamic-programming equation arising from the binary choice: at each step the controlling player may either play a standard random Tug-of-War step or accept a fixed payoff and force the opponent to choose the next vertex. The proof proceeds by considering the two cases separately, adjusting the ordering of the comparison functions to incorporate the fixed-payoff option, and verifying the required monotonicity properties under this enlarged set of moves. The viscosity and probabilistic arguments are likewise adapted to the modified equation. We will revise the abstract to state that a suitable (rather than the unmodified) discrete comparison principle is established for the totalitarian game, and we will add a short clarifying paragraph in the introduction that highlights the changes to the standard argument. revision: yes

Circularity Check

0 steps flagged

No circularity; proof invokes external comparison principles and viscosity theory

full rationale

The paper establishes existence of a game value via a discrete comparison principle together with viscosity and probabilistic arguments. These tools are standard external machinery in the literature on infinity-harmonic functions and Tug-of-War games; the abstract and provided context contain no equations or claims that define the value in terms of itself, fit a parameter to a subset of data then rename the fit as a prediction, or reduce the central result to a self-citation chain. The derivation therefore remains independent of its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the proof draws on standard background results from analysis and probability on graphs; no free parameters, new entities, or ad-hoc axioms are identifiable from the given text.

axioms (2)

standard math Standard properties of finite undirected graphs and random walks on them
Invoked implicitly when defining the game positions and moves.
domain assumption Existence and comparison properties for viscosity solutions of the related extremal equations
Used to transfer the game value to the PDE side.

pith-pipeline@v0.9.0 · 5607 in / 1303 out tokens · 23785 ms · 2026-05-24T18:15:04.216590+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[1]

Gunnar Aronsson, On the partial diﬀerential equation u2 xuxx +2uxuyuxy +u2 yuyy = 0, Arkiv f¨ or Matematik7 (1968), 395–425

work page 1968
[2]

Souganidis, Convergence of approximation schemes for fully nonlinear second order equations , Asymptotic analysis 4 (1991), 271–283

Guy Barles and Panagiotis E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations , Asymptotic analysis 4 (1991), 271–283

work page 1991
[3]

DiBenedetto, and Juan J

Tilak Bhattacharya, E. DiBenedetto, and Juan J. Manfredi , Limits as p → ∞ of ∆pup = f and related extremal problems , Nonlinear PDE’s, Rendiconti del Seminario Matematico. Universit` a e Politecnico Torino, Fasciolo Speciale, 1989 , pp. 15–68

work page 1989
[4]

Crandall, A Visit with the ∞-Laplace Equation, Lecture Notes in Mathematics 1927 (2008), 75–122

Michael G. Crandall, A Visit with the ∞-Laplace Equation, Lecture Notes in Mathematics 1927 (2008), 75–122

work page 1927
[5]

Evans, The 1-Laplacian, the ∞-Laplacian and Diﬀerential Games , Contemp

Lawrence C. Evans, The 1-Laplacian, the ∞-Laplacian and Diﬀerential Games , Contemp. Math 446 (2007), 245–254

work page 2007
[6]

Evans and W

Lawrence C. Evans and W. Gangbo, Diﬀerential equations methods for the Monge– Kantorovich mass transfer problem , Memoirs of the American Mathematical Society 137 (1999), 1–66

work page 1999
[7]

Evans and Ovidiu Savin, C1,α regularity for inﬁnite harmonic functions in two dimensions, Calculus of Variations and Partial Diﬀerential Equations 32 (2008), 325–347

Lawrence C. Evans and Ovidiu Savin, C1,α regularity for inﬁnite harmonic functions in two dimensions, Calculus of Variations and Partial Diﬀerential Equations 32 (2008), 325–347

work page 2008
[8]

Evans and Charles K

Lawrence C. Evans and Charles K. Smart, Everywhere diﬀerentiability of inﬁnity harmonic functions, Calculus of Variations and Partial Diﬀerential Equations 42 (2011), 289–299

work page 2011
[9]

Garc ´ ıa-Azorero, Juan J

J. Garc ´ ıa-Azorero, Juan J. Manfredi, I. Peral, and Julio D. Rossi, The Neumann problem for the ∞-Laplacian and the Monge–Kantorovich mass transfer proble m, Nonlinear Analysis: Theory, Methods & Applications 66 (2007), 349–366

work page 2007
[10]

TOTALITARIAN RANDOM TUG-OF-W AR GAMES IN GRAPHS 25

Robert Jensen, Uniqueness of Lipschitz extensions: minimizing the sup nor m of the gradient , Archive for Rational Mechanics and Analysis 123 (1993), 51–74. TOTALITARIAN RANDOM TUG-OF-W AR GAMES IN GRAPHS 25

work page 1993
[11]

thesis, University of Jyv¨ askyl¨ a, 1998

Petri Juutinen, Minimization problems for Lipschitz functions via viscosi ty solutions , Ph.D. thesis, University of Jyv¨ askyl¨ a, 1998

work page 1998
[12]

Bernhard Kawohl, On a family of Torsional Creep Problems , Journal f¨ ur die Reine und Angewandte Mathematik 410 (1990), 1–22

work page 1990
[13]

Le Gruyer and J

E. Le Gruyer and J. C. Archer, Harmonious extensions , SIAM J. Math. Anal. 29 (1998), no. 1, 279–292

work page 1998
[14]

Peter Lindqvist, Notes on the inﬁnity laplace equation , Springer, 2016

work page 2016
[15]

Adam M. Oberman, Convergent diﬀerence schemes for degenerate elliptic and p arabolic equations: Hamilton–Jacobi equations and free boundary pr oblems, SIAM Journal on Nu- merical Analysis 44 (2006), 879–895

work page 2006
[16]

Wi lson, Tug-of-war and the inﬁnity Laplacian , Journal of the American Mathematical Society 22 (2009), 167–210

Yuval Peres, Oded Schramm, Scott Sheﬃeld, and David B. Wi lson, Tug-of-war and the inﬁnity Laplacian , Journal of the American Mathematical Society 22 (2009), 167–210

work page 2009
[17]

Rossi, Tug-of-war games

Julio D. Rossi, Tug-of-war games. Games that pde people like to play. , Lecture notes CAPDE (2010), 1–47

work page 2010
[18]

Ovidiu Savin, C1 regularity for inﬁnity harmonic functions in two dimension s, Archive for Rational Mechanics and Analysis 176 (2005), 351–361

work page 2005
[19]

Jos´ e Miguel Urbano, An Introduction to the ∞-Laplacian, Short Course (2013), 1–30

work page 2013
[20]

Changyou W ang, An Introduction of Inﬁnity Harmonic Functions , (2008)

work page 2008
[21]

Yifeng Yu, A remark on C2 inﬁnity-harmonic functions , Electronic Journal of Diﬀerential Equations 2006 (2006), 1–4. Universitat Polit `ecnica de Catalunya, Departament de Matem `atiques, Diagonal 647, 08028 Barcelona, Spain E-mail address : m.anton.a@outlook.com Fernando Charro: Department of Mathematics, W ayne State Uni versity, Detroit, MI 48202, USA ...

work page 2006

[1] [1]

Gunnar Aronsson, On the partial diﬀerential equation u2 xuxx +2uxuyuxy +u2 yuyy = 0, Arkiv f¨ or Matematik7 (1968), 395–425

work page 1968

[2] [2]

Souganidis, Convergence of approximation schemes for fully nonlinear second order equations , Asymptotic analysis 4 (1991), 271–283

Guy Barles and Panagiotis E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations , Asymptotic analysis 4 (1991), 271–283

work page 1991

[3] [3]

DiBenedetto, and Juan J

Tilak Bhattacharya, E. DiBenedetto, and Juan J. Manfredi , Limits as p → ∞ of ∆pup = f and related extremal problems , Nonlinear PDE’s, Rendiconti del Seminario Matematico. Universit` a e Politecnico Torino, Fasciolo Speciale, 1989 , pp. 15–68

work page 1989

[4] [4]

Crandall, A Visit with the ∞-Laplace Equation, Lecture Notes in Mathematics 1927 (2008), 75–122

Michael G. Crandall, A Visit with the ∞-Laplace Equation, Lecture Notes in Mathematics 1927 (2008), 75–122

work page 1927

[5] [5]

Evans, The 1-Laplacian, the ∞-Laplacian and Diﬀerential Games , Contemp

Lawrence C. Evans, The 1-Laplacian, the ∞-Laplacian and Diﬀerential Games , Contemp. Math 446 (2007), 245–254

work page 2007

[6] [6]

Evans and W

Lawrence C. Evans and W. Gangbo, Diﬀerential equations methods for the Monge– Kantorovich mass transfer problem , Memoirs of the American Mathematical Society 137 (1999), 1–66

work page 1999

[7] [7]

Evans and Ovidiu Savin, C1,α regularity for inﬁnite harmonic functions in two dimensions, Calculus of Variations and Partial Diﬀerential Equations 32 (2008), 325–347

Lawrence C. Evans and Ovidiu Savin, C1,α regularity for inﬁnite harmonic functions in two dimensions, Calculus of Variations and Partial Diﬀerential Equations 32 (2008), 325–347

work page 2008

[8] [8]

Evans and Charles K

Lawrence C. Evans and Charles K. Smart, Everywhere diﬀerentiability of inﬁnity harmonic functions, Calculus of Variations and Partial Diﬀerential Equations 42 (2011), 289–299

work page 2011

[9] [9]

Garc ´ ıa-Azorero, Juan J

J. Garc ´ ıa-Azorero, Juan J. Manfredi, I. Peral, and Julio D. Rossi, The Neumann problem for the ∞-Laplacian and the Monge–Kantorovich mass transfer proble m, Nonlinear Analysis: Theory, Methods & Applications 66 (2007), 349–366

work page 2007

[10] [10]

TOTALITARIAN RANDOM TUG-OF-W AR GAMES IN GRAPHS 25

Robert Jensen, Uniqueness of Lipschitz extensions: minimizing the sup nor m of the gradient , Archive for Rational Mechanics and Analysis 123 (1993), 51–74. TOTALITARIAN RANDOM TUG-OF-W AR GAMES IN GRAPHS 25

work page 1993

[11] [11]

thesis, University of Jyv¨ askyl¨ a, 1998

Petri Juutinen, Minimization problems for Lipschitz functions via viscosi ty solutions , Ph.D. thesis, University of Jyv¨ askyl¨ a, 1998

work page 1998

[12] [12]

Bernhard Kawohl, On a family of Torsional Creep Problems , Journal f¨ ur die Reine und Angewandte Mathematik 410 (1990), 1–22

work page 1990

[13] [13]

Le Gruyer and J

E. Le Gruyer and J. C. Archer, Harmonious extensions , SIAM J. Math. Anal. 29 (1998), no. 1, 279–292

work page 1998

[14] [14]

Peter Lindqvist, Notes on the inﬁnity laplace equation , Springer, 2016

work page 2016

[15] [15]

Adam M. Oberman, Convergent diﬀerence schemes for degenerate elliptic and p arabolic equations: Hamilton–Jacobi equations and free boundary pr oblems, SIAM Journal on Nu- merical Analysis 44 (2006), 879–895

work page 2006

[16] [16]

Wi lson, Tug-of-war and the inﬁnity Laplacian , Journal of the American Mathematical Society 22 (2009), 167–210

Yuval Peres, Oded Schramm, Scott Sheﬃeld, and David B. Wi lson, Tug-of-war and the inﬁnity Laplacian , Journal of the American Mathematical Society 22 (2009), 167–210

work page 2009

[17] [17]

Rossi, Tug-of-war games

Julio D. Rossi, Tug-of-war games. Games that pde people like to play. , Lecture notes CAPDE (2010), 1–47

work page 2010

[18] [18]

Ovidiu Savin, C1 regularity for inﬁnity harmonic functions in two dimension s, Archive for Rational Mechanics and Analysis 176 (2005), 351–361

work page 2005

[19] [19]

Jos´ e Miguel Urbano, An Introduction to the ∞-Laplacian, Short Course (2013), 1–30

work page 2013

[20] [20]

Changyou W ang, An Introduction of Inﬁnity Harmonic Functions , (2008)

work page 2008

[21] [21]

Yifeng Yu, A remark on C2 inﬁnity-harmonic functions , Electronic Journal of Diﬀerential Equations 2006 (2006), 1–4. Universitat Polit `ecnica de Catalunya, Departament de Matem `atiques, Diagonal 647, 08028 Barcelona, Spain E-mail address : m.anton.a@outlook.com Fernando Charro: Department of Mathematics, W ayne State Uni versity, Detroit, MI 48202, USA ...

work page 2006