# Zero-sum Random Games on Directed Graphs

Luc Attia, Lyuben Lichev, Dieter Mitsche, Raimundo Saona, Bruno Ziliotto

► To cite this version:

Luc Attia, Lyuben Lichev, Dieter Mitsche, Raimundo Saona, Bruno Ziliotto. Zero-sum Random Games on Directed Graphs. Dynamic Games and Applications, 2025, 15 (5), pp.1517-1535. 10.1007/s13235-025-00636-4. hal-04568452

HAL Id: hal-04568452

https://hal.science/hal-04568452v1

Submitted on 15 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Zero-sum Random Games on Directed Graphs

Luc Attia*

Lyuben Lichev†

Dieter Mitsche‡

Raimundo Saona§

Bruno Ziliotto¶

January 30, 2024

## Abstract

This paper considers a class of two-player zero-sum games on directed graphs whose vertices are equipped with random payoffs of bounded support known by both players. Starting from a fixed vertex, players take turns to move a token along the edges of the graph. On the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that the value of the game converges almost surely to a constant at an exponential rate dominated in terms of the expansion. On the other hand, for the infinite $d$-ary tree that does not fall into the previous class of graphs, we show convergence at a double-exponential rate in terms of the expansion.

## 1 Introduction

The following class of two-player zero-sum games has been introduced in [8] under the name of *percolation games*. Each vertex of $\mathbb{Z}^d$ is equipped with a real-valued random variable called *payoff*. The realization of all these variables is known to the players at the start of the game. Initially, a token is placed at some vertex of $\mathbb{Z}^d$ and, at every stage, each player chooses an action. Then, the token is moved consecutively by Player 1 and by Player 2 according to the chosen actions. At the end of every stage, Player 2 pays to Player 1 the payoff of the corresponding vertex. Player 1 aims at maximizing the mean payoff over $n$ stages, while Player 2 aims at minimizing the same quantity, and the value of that game is denoted by $V_n$. The main result of [8] shows that, when payoffs are bounded i.i.d. random variables and the game is *oriented* (meaning that, at every move, the projection of the position of the token onto some fixed axis increases), then $(V_n)$ converges almost surely (a.s.) to a constant.

The class of percolation games is motivated by various reasons. First, it relates to the rich game-theoretic literature on the existence of a limit value in dynamic games (see for example the surveys [14, 15]). This topic is particularly delicate for dynamic games with infinite state space, where general positive results are scarce (see [9, 13, 18] for some recent advances, and [17] for several counterexamples). Second, percolation games connect to the important topic of stochastic homogenization of partial differential equations, for example, see [8, Section 4] for results on Hamilton-Jacobi equations. Moreover, from a probabilistic point of view, percolation games combine aspects of first-passage and last-passage percolation [3], and a related model of Probabilistic Finite Automaton has been studied in [11, 4]. Finally, it contributes to the growing literature on random games (see e.g. [7, 1, 2, 10]).

<footnote>*Paris Dauphine University, France.</footnote>

<footnote>†Univ. Jean Monnet, Saint-Etienne, France and Institute of Mathematics and Informatics, Bulgarian Academy of Science, Sofia, Bulgaria.</footnote>

<footnote>‡Univ. Jean Monnet, Saint-Etienne, France and Institute for Mathematical and Computational Engineering, Pontificia Universidad Católica, Chile.</footnote>

<footnote>§Institute of Science and Technology Austria, Austria.</footnote>

<footnote>¶CEREMADE, CNRS, Paris Dauphine University, France.</footnote>
In this paper, we consider a model with a structure similar to that of a percolation game but where the state space is not restricted to be the graph $\mathbb{Z}^d$. We introduce directed games where the state space of the game is the vertex set of an acyclic directed graph $\Gamma$ where players move the token along the edges of $\Gamma$ respecting their orientation. On the one hand, under certain assumptions of transitivity and sub-exponential growth of $\Gamma$, we prove that $V_n$ is exponentially concentrated around a given deterministic value (so, in particular, converges to that value a.s.) and relate the convergence rate to the speed of growth of the graph. On the other hand, we consider the infinite $d$-ary tree with $d \ge 2$ where each vertex has exactly $d$ children and every edge is directed from the parent to the child. These graphs do not belong to the previous class of transient games due to their exponential growth. In this case, we show a stronger double-exponential concentration of $V_n$ around its expected value.

## 2 Preliminaries

A directed game is a dynamical system that consists of a locally finite directed graph $\Gamma$ with infinite countable vertex set $Z$ called the state space, an initial state $z_0 \in Z$ and a collection of independent and identically distributed (i.i.d.) random variables $(G_z)_{z \in Z}$ called payoffs. We assume that $\Gamma$ has uniformly bounded degrees and contains neither directed cycles nor vertices with out-degree 0. The game is played by two players called Player 1 and Player 2. At the start of the game, the payoffs $(G_z)_{z \in Z}$ are sampled and presented to both players, who thus obtain perfect information. Then, a token is placed at the initial state $z_0$. For every integer $i \ge 0$, given that the token is positioned at a state $z \in Z$ before stage $i + 1$, the following happens:

* if $i$ is even, Player 1 moves the token to an out-neighbor $z'$ of $z$ in $\Gamma$,

* if $i$ is odd, Player 2 moves the token to an out-neighbor $z'$ of $z$ in $\Gamma$,

* Player 1 receives the payoff $G_{z'}$ from Player 2.

Note that, unlike the setting in [8], only one of the players performs a move at each round. We are mostly interested in the $n$-stage game consisting of the first $n$ stages for (typically large) integers $n$.

A strategy of Player 1 (resp. Player 2) is a function $\sigma: \bigcup_{m \ge 0} Z^{2m+1} \to Z$ (resp. $\tau: \bigcup_{m \ge 0} Z^{2m+2} \to Z$) with the property that, for every $m \ge 0$ and $(z_0, z_1, \dots, z_{2m+1}) \in Z^{2m+2}$, $\Gamma$ contains the edge from $z_{2m}$ to $\sigma(z_0, \dots, z_{2m})$ (resp. from $z_{2m+1}$ to $\tau(z_0, \dots, z_{2m+1})$). We denote by $\Sigma$ the collection of all strategies for Player 1 and by $\mathcal{T}$ the collection of all strategies for Player 2.

Given a pair of strategies $(\sigma, \tau) \in \Sigma \times \mathcal{T}$, we define inductively the trajectory of the token by setting $z_{2i+1} := \sigma(z_0, \dots, z_{2i})$ and $z_{2i+2} := \tau(z_0, \dots, z_{2i+1})$ for every $i \ge 0$. This allows us to define the $n$-stage payoff function $\gamma_n^{z_0}: \Sigma \times \mathcal{T} \to \mathbb{R}$ by setting

$$ \gamma_n^{z_0}(\sigma, \tau) := \frac{1}{n} \sum_{i=1}^{n} G_{z_i}. $$

Note that, for a fixed initial state, since the directed graph $\Gamma$ is locally finite, the $n$-stage game is played on a finite state space with perfect information. For every $z \in Z$, the $n$-value of the game with initial state $z_0 = z$ is defined as

$$ V_n(z) := \max_{\sigma \in \Sigma} \min_{\tau \in \mathcal{T}} \gamma_n^z(\sigma, \tau) = \min_{\tau \in \mathcal{T}} \max_{\sigma \in \Sigma} \gamma_n^z(\sigma, \tau), $$

where the classic minimax theorem [6, 16] applies to justify the above equality. Moreover, we will say that a strategy $\sigma \in \Sigma$ (resp. $\tau \in \mathcal{T}$) is optimal for the $n$-stage game (starting from $z$) if $\sigma$ maximizes $\min_{\tau \in \mathcal{T}} \gamma_n^z(\cdot, \tau)$ over $\Sigma$ (resp. if $\tau$ minimizes $\max_{\sigma \in \Sigma} \gamma_n^z(\sigma, \cdot)$ over $\mathcal{T}$).
A classic question in the game-theoretic literature is to ask for the convergence of the n-value as n grows to infinity. Since payoffs are random, $V_n$ is a random variable. Therefore, we are interested in whether the sequence $(V_n)$ converges a.s. to a constant.

In our model, if no further assumptions are imposed, it is possible that $(V_n)$ does not converge. For example, for all integers $m \ge 0$, set $n_m := 2^{2^m}$ and $n'_m := 2^{2^{m+1}}$ and consider the case where $\Gamma$ is a directed tree (all edges being directed away from the root) where each node with even height has only one child, while each node with odd height $k$ has two children if $k = 1$ or $k \in [n_m, n'_m)$ for some $m \ge 0$, and it has only one child if $k \in [n'_m, n_{m+1})$. Moreover, let the payoffs be i.i.d. Bernoulli random variables with parameter $1/2$. In particular, for every $m \ge 1$, in the $n_m$-stage game, Player 2 has only one choice most of the time, while in the $n'_m$-stage game, she has two choices most of the time. Since Player 2 can not uniformly pick a vertex with payoff 0 (if it is present), and pick an available vertex otherwise, one can show that a.s.

$$ \limsup_{m \to \infty} V_{n'_m} \le \frac{3}{8} < \frac{1}{2} = \lim_{m \to \infty} V_{n_m}. $$

Indeed, while Player 1 never has a choice in the $n'_m$-game (implying that the mean payoff over the odd states visited by the token a.s. converges to $1/2$), Player 2 can ensure with the above strategy that the mean payoff over the even states visited by the token a.s. converges to $1/4$, which yields that a.s. $\limsup_{m \to \infty} V_{n'_m} \le 3/8$. At the same time, for every $\varepsilon > 0$, Chernoff's bound for the Binomial distribution $Bin(n_m, 1/2)$ and a union bound over the $O(2^{n'_m-1})$ vertices at level $n_m$ in $\Gamma$ shows that $V_{n_m}$ is in the interval $[1/2 - \varepsilon, 1/2 + \varepsilon]$ with probability very close to 1. In particular, a.s. $(V_n)$ does not converge. Therefore, to ensure convergence, we will need further structural assumptions on the graph.

Before turning to our results, we provide some vocabulary. Given a vertex $z \in Z$, a *descendant* of $z$ (in $\Gamma$) is a vertex that can be reached from $z$ by a directed path in $\Gamma$. We say that $z$ and $z'$ are *equivalent* if the two subgraphs of $\Gamma$ induced by the descendants of $z$ and by the descendants of $z'$, respectively, are isomorphic (as directed graphs).

**Definition 1.** The graph $\Gamma$ is weakly transitive if there is a state $z^*$ and an integer $M$ such that the following holds: for each state $z \in Z$, in the game with initial state $z_0 = z$, each player has a strategy that, independently of the moves of the opponent, ensures that the token is placed at a state equivalent to $z^*$ after an even number of $\ell \le M$ stages.

Note that all vertex-transitive graphs are weakly transitive with $M = 0$. In the remainder of the paper, we always assume that $\Gamma$ is weakly transitive. The next two subsections present two types of directed games used in our main results.

## 2.1 Weakly transitive games with sub-exponential expansion

We continue with a few definitions. Given a state $z \in Z$, we consider a partition $\Pi_z := (Z_i(z))_{i \ge 0}$ of $Z$ such that: (i) $Z_0(z) = \{z\}$; and (ii), for all strategies $(\sigma, \tau) \in \Sigma \times \mathcal{T}$ for the game starting at $z$ and for all $i \ge 1$, the token can visit the set $Z_i(z)$ at most once. Since $\Gamma$ has no directed cycles, such a partition exists. For example, the trivial one where every part contains a single state satisfies this property. We call such partitions *adapted*. For every integer $n \ge 1$, we also set $Z_{[n]}(z) := \bigcup_{j=0}^n Z_j(z)$ and $Z^{(n)}(z)$ for the set of *reachable states* from $z$ after at most $n$ steps. Note that, when it is clear from the context, we omit $z$ from the notation and simply write $Z_n, Z^{(n)}$ and $Z_{[n]}$ for better readability.

Given a family of adapted partitions $\Pi := (\Pi_z)_{z \in Z}$ in a directed game, we define the *transient speed function* $h$ of $\Pi$ as

$$ h: n \in \mathbb{N} \mapsto \max_{z \in Z} \min \left\{ k \in \mathbb{N} : Z^{(n)}(z) \subseteq Z_{[k]}(z) \right\}. $$
Note that $h(n) \ge n$ for every integer $n \ge 1$ since, for every $z \in Z$, exactly $n$ of the sets $(Z_i(z))_{i \ge 1}$ are visited by the token after $n$ stages. Our main goal is to analyze directed games where the size of the sets $Z^{(n)}(z)$ does not increase too fast as $n$ grows to infinity.

**Definition 2 (δ-transient games).** Given a family of adapted partitions $\Pi$ with transient speed $h$, we define the function $\psi: \mathbb{N} \times (0, \infty) \to \mathbb{R}$ by

$$ \psi(n, t) := \exp\left(-\frac{t^2 n^2}{2h(n)}\right) \max_{z \in Z} |Z^{(2n)}(z)|. $$

For a fixed $\delta > 0$, a directed game on a graph $\Gamma$ with vertex set $Z$ is called $\delta$-transient if there exists a family of adapted partitions $\Pi$ of $Z$ and a sequence $(\varepsilon_n)_{n \ge 1}$ such that $\varepsilon_n + \psi(n, \varepsilon_n) = O(n^{-\delta})$. Such a family $\Pi$ is called a $\delta$-adapted family.

**Remark 1.** The concept of $\delta$-transient games is only relevant for $\delta \in (0, 1/2)$. Indeed, Definition 2 requires that $(\psi(n, \varepsilon_n))_n$ converges to zero. Therefore, since $h(n) \ge n$, this implies that $n = o(\varepsilon_n^2 n^2)$, so that $\varepsilon_n \in o(n^{1-1/2})$.

**Remark 2.** A sufficient condition under which a directed game is $\delta$-transient is the following: there exists an adapted partition $\Pi$ and real numbers $\alpha \in [0, 2-2\delta)$ and $\beta \in [0, 2-2\delta - \alpha)$ such that $h(n) = O(n^\alpha)$ and $\max_{z \in Z} |Z^{(n)}(z)| = \exp(O(n^\beta))$.

Note that the definition of a $\delta$-transient game is independent of the payoffs and only makes assumptions on the state space and the associated adapted partition. We now give a few examples of $\delta$-transient games.

### 2.1.1 Oriented directed games

Fix an integer $d \ge 1$, and denote by $e_i$ the $d$-dimensional vector with 1 in coordinate $i$ and 0 in all other $d-1$ coordinates. Given positive integers $n_1, \dots, n_d \ge 1$, a (directed) graph $\Gamma$ with vertex set $Z \subseteq \mathbb{Z}^d$ is called $(n_1, \dots, n_d)$-invariant (or simply invariant) if, for every $i \in [1, d]$, the translation at vector $n_i e_i$ is a graph isomorphism for $\Gamma$. A directed game is called oriented if its underlying graph $\Gamma$ is invariant and there exists $u \in \mathbb{R}^d \setminus \{0\}$ such that, for every directed edge $zw$ in $\Gamma$, we have $(w-z) \cdot u > 0$ (here, $\cdot$ denotes the usual scalar product of vectors in $\mathbb{R}^d$). We show the following proposition.

**Proposition 1.** Every oriented directed game is $\delta$-transient for all $\delta \in (0, 1/2)$.

The following two classes of games present particular examples of oriented directed games.

**Example 1 (Games on tilings).** A tiling is a periodic partition of the plane into translations of one or several polygonal shapes, called tiles, with vertices in $\mathbb{Z}^2$. Tilings naturally define planar graphs whose vertex set coincides with the corners of the tiles and two vertices are connected by an edge if these can be connected by following the boundary of a tile without meeting another vertex on the way. By equipping the edges of this graph with suitable orientations, one can generate many different oriented directed games, see e.g. Figure 1.

**Example 2 (Games on directed chains of graphs).** Fix a finite vertex-transitive graph $H$ with vertex set $V(H)$ and edge set $E(H)$, and a bi-infinite sequence of copies $(H_i)_{i \in \mathbb{Z}}$ of $H$. For every $i \in \mathbb{Z}$ and $u \in V(H)$, denote by $u_i$ the vertex in $H_i$ corresponding to $u$. We call an $H$-chain the graph $\Gamma_H$ with vertices $\bigcup_{i \in \mathbb{Z}} V(H_i)$ and edges $\{u_i v_{i+1} : i \in \mathbb{Z}, uv \in E(H)\}$.

Games on $H$-chains can be seen as instances of oriented directed games on $\mathbb{Z}$. Indeed, fixing $h = |V(H)|$, one may identify the vertices of $H_i$ with the integers in the interval $[ih + 1, (i+1)h]$ for all $i \in \mathbb{Z}$ in a translation-invariant way.
<figure><img src="image_2.png" /><figcaption>Figure 1: The figure depicts part of a tiling with two types of square tiles. The vertices and the edges of the planar graph originating from the tiling are depicted in blue and red, respectively. Each horizontal edge is oriented from left to right and every vertical edge is oriented from bottom to top. One may choose $z^*$ to be the bottom left vertex of a small square and $M = 6$.</figcaption></figure>

### 2.1.2 Weakly transitive games with controlled expansion

Fix an arbitrary infinite rooted tree $T$ with root $r$ and a family of vertex-disjoint infinite paths $(P_v)_{v \in V(T)}$ where the path $P_v$ starts at vertex $v$ in $T$. Define $\Gamma = T \cup (\bigcup_{v \in V(T)} P_v)$ as the tree rooted in $r$ and with all edges oriented away from $r$. Let $(Z_n)_{n \ge 0}$ be a partition of the vertex set $Z$ of $\Gamma$ where $Z_n$ consists of all vertices at distance $n$ from $r$ for all $n \ge 0$. Also, for every $z \in Z$ and $k \ge 2$, define $Z_k(z)$ to be the set of descendants of $z$ at distance $k$ from it while $Z_0(z) = \{z\}$ and $Z_1(z) = Z \setminus ((\bigcup_{k \ge 2} Z_k(z)) \cup Z_0(z))$. Note that, somewhat arbitrarily, we added all vertices not reachable from $z$ to $Z_1(z)$ to ensure that $(Z_i(z))_{i \ge 0}$ is a partition of $Z$. Then, $\Pi_z = (Z_i(z))_{i \ge 0}$ is an adapted partition and $\Pi = (\Pi_z)_{z \in Z}$ is an adapted family of partitions. Moreover, a single move of each player is sufficient to place the token at the second vertex of some infinite path among $(P_v)_{v \in V(T)}$. This implies that the game is weakly transitive.

Let us show that we can control the growth speed of $\max_{z \in Z} |Z^{(2n)}(z)|$. Consider a set of non-negative integers $L = \{\ell_i : i \ge 1\}$ with $\ell_1 < \ell_2 < \dots$ and let every vertex of $T$ in level $\ell$ have two children if $\ell \in L$ and one child otherwise. Moreover, suppose that $\ell_1 = 0$ and $(\ell_i - \ell_{i-1})_{i \ge 1}$ is a non-decreasing sequence. Then, one can readily check that, for every $n \ge 1$, $\max_{z \in Z} |Z^{(n)}(z)| = |Z^{(n)}(r)|$. Indeed, for every $k, n \ge 1$ and a vertex $z \in Z$ on level $k$, using the assumptions that $\ell_1 = 0$ and $(\ell_i - \ell_{i-1})_{i \ge 1}$ is a non-decreasing sequence, we get

$$ |Z^{(n)}(z) \setminus Z^{(n-1)}(z)| = 2^{|L \cap \{k, \dots, k+n-1\}|} \le 2^{|L \cap \{0, \dots, n-1\}|} = |Z^{(n)}(r) \setminus Z^{(n-1)}(r)|. $$

Thus, for every integer $n \ge 0$, $|Z^{(n)}(r)| = 1 + \sum_{i=0}^{n-1} 2^{|L \cap \{0, \dots, i\}|}$. Therefore, by a suitable choice of the set $L$, one can construct a tree $T$ with an arbitrary growth that is faster than linear but slower than exponential. In particular, for every $\delta \in (0, 1/2)$, this shows the existence of games that are $\delta$-transient but, for every $\delta' > \delta$, not $\delta'$-transient.

## 2.2 Directed games on $d$-ary trees

We turn our attention to a natural example of a directed game where the set of reachable states after $n$ steps grows exponentially with $n$. Note that, for all $\delta > 0$, it is not a $\delta$-transient game. Fix an integer $d \ge 2$ and let $T$ be an infinite $d$-ary tree, that is, a tree where every vertex has $d$ children, with vertex set $Z$ where every edge is oriented from the parent to the child. We fix an arbitrary initial vertex $z_0$ and, for every integer $i \ge 0$, we define $Z_i$ to be the set of vertices in $Z$ that can be reached from $z_0$ by exactly $i$ steps and also denote $Z_{\text{even}} := \bigcup_{i \ge 0} Z_{2i}$ and $Z_{\text{odd}} := \bigcup_{i \ge 0} Z_{2i+1}$. Note that, for every $n \ge 1$, the random variables $(V_n(z))_{z \in Z}$ have the same distribution. Thus, we often omit the dependence of $V_n$ in $z$.
## 2.3 Main results

Our first main result shows sharp concentration for the n-value of $\delta$-transient games around a deterministic constant.

**Theorem 1.** Fix $\delta \in (0, 1/2)$. Consider a $\delta$-transient directed game, a $\delta$-adapted family with transient speed $h$, and i.i.d. payoffs $(G_z)_{z \in Z}$ supported on the interval $[0, 1]$. Then, there exist constants $v_\infty \in [0, 1]$ and $K > 0$ such that, for all $n \ge 1$, $t \ge 0$, and $z \in Z$,

$$ \mathbb{P}(|V_n(z) - v_\infty| \ge t + Kn^{-\delta}) \le 2 \exp \left( -\frac{t^2 n^2}{2h(n)} \right). $$

Consequently, $(V_n)$ converges almost surely to $v_\infty$.

Our second main result shows that the n-value of the directed game on a d-ary tree is tightly concentrated around a constant.

**Theorem 2.** Fix an integer $d \ge 2$. Consider a directed game on the d-ary tree with i.i.d. payoffs supported on the interval $[0, 1]$. Then, there exists a real number $v_\infty \in [0, 1]$ such that, for every $\delta \in (0, 1/2)$, there exists $K > 0$ such that, for every $n \ge 1$ and $t \ge 0$,

$$ \mathbb{P}(|V_n - v_\infty| \ge t + 2t^2 + Kn^{-\delta}) \le \exp \left( -\frac{1}{6} \exp \left( \frac{t^2 n}{4} \right) \right). $$

Consequently, $(V_n)$ converges almost surely to $v_\infty$.

**Outline of the proofs.** The proofs of both theorems contain two main steps. The first step involves standard concentration arguments showing that $V_n$ is close to $\mathbb{E}[V_n]$ with high probability. While these are sufficient for Theorem 1, the stronger probabilistic bound in Theorem 2 requires an additional boosting obtained by dividing the first $n$ levels of the d-ary tree into two groups of consecutive levels and treating the $n$-stage game as two consecutive games on $k$ and $n-k$ stages respectively. The second step uses the structure of the underlying graph to show that $\mathbb{E}[V_n]$ satisfies a certain subadditivity assumption, which allows us to conclude that $(\mathbb{E}[V_n])_{n \ge 1}$ converges to a constant $v_\infty$, and moreover, $|\mathbb{E}[V_n] - v_\infty|$ is polynomially small. The proof of Proposition 1 relies on a simple explicit construction.

**Perspectives** The proofs of Theorems 1 and 2 have a similar structure but use different arguments. A challenging research question would be to prove convergence of $(V_n)$ and concentration bounds in any weakly transitive directed game, irrespective of the expansion speed of the underlying graph, thus unifying Theorems 1 and 2.

**Plan of the paper.** This paper is organized as follows. In Section 3, we state some classical results we will use later. Then, in Section 4, we prove Theorem 1, and in Section 5, we prove Theorem 2. In Section 6, we prove Proposition 1.

# 3 Classical results

In our proofs, we make use of the well-known *bounded difference inequality*, also known as *McDiarmid's inequality*, tightly related to *Azuma's inequality*.

**Lemma 1** (Corollary 2.27 in [12]). Fix a function $f: \Lambda_1 \times \dots \times \Lambda_N \to \mathbb{R}$ and let $Y_1, \dots, Y_N$ be independent random variables taking values in $\Lambda_1, \dots, \Lambda_N$, respectively. Suppose that there are positive constants $c_1, \dots, c_N$ such that, for every two vectors $z, w \in \Lambda_1 \times \dots \times \Lambda_N$ that differ only
in the k-th coordinate, we have $|f(z) - f(w)| \le c_k$. Then, for every $t \ge 0$, the random variable $X = f(Y_1, \dots, Y_N)$ satisfies

$$ \mathbb{P}(X - \mathbb{E}[X] \ge t) \le \exp\left(-\frac{t^2}{2 \sum_{i=1}^{N} c_i^2}\right). $$

$$ \mathbb{P}(X - \mathbb{E}[X] \le -t) \le \exp\left(-\frac{t^2}{2 \sum_{i=1}^{N} c_i^2}\right). $$

We also use the following result that states convergence of almost subadditive sequences.

**Lemma 2** (Theorem 23 in [5]). Fix an increasing function $\phi: \mathbb{N} \to (0, \infty)$ such that the sum of $(\phi(n)/n^2)_{n \ge 1}$ is finite, and a function $f: \mathbb{N} \to \mathbb{R}$ such that, for all $n \in \mathbb{N}$ and all integers $m \in [n/2, 2n]$, $f(n+m) \le f(n) + f(m) + \phi(n+m)$. Then, there exists $\ell \in \mathbb{R} \cup \{-\infty\}$ such that

$$ \frac{f(n)}{n} \xrightarrow{n \to \infty} \ell. $$

## 4 $\delta$-transient games: proof of Theorem 1

Fix an initial state $z_0$ and write $V_n = V_n(z_0)$, $Z_n = Z_n(z_0)$ for short. To begin with, we show that $V_n$ is well concentrated around its expected value. Note that the next lemma holds for weakly transitive games in general and will be reused in the next section.

**Lemma 3.** For every $t \ge 0$,

$$ \mathbb{P}(V_n - \mathbb{E}[V_n] \ge t) \le \exp\left(-\frac{t^2 n^2}{2h(n)}\right), $$

$$ \mathbb{P}(V_n - \mathbb{E}[V_n] \le -t) \le \exp\left(-\frac{t^2 n^2}{2h(n)}\right). $$

*Proof.* Define the (random) vectors $X_k = (G_z)_{z \in Z_k} \in [0, 1]^{|Z_k|}$. Then, since $Z^{(n)} \subseteq Z_{[h(n)]}$, $V_n$ can be written as $f(X_1, \dots, X_{h(n)})$ for some function $f: [0, 1]^{|Z_1|} \times \dots \times [0, 1]^{|Z_{h(n)}|} \to \mathbb{R}$. Moreover, for every integer $k \in [1, h(n)]$, the token visits the set $Z_k$ at most once and therefore, for every pair of strategies $(\sigma, \tau) \in \Sigma \times \mathcal{T}$, $\gamma_n^{z_0}(\sigma, \tau)$ varies by at most $1/n$ as a function of $X_k$. Hence, for every choice of vectors $(x_i)_{i=1}^{h(n)} \in [0, 1]^{|Z_1|} \times \dots \times [0, 1]^{|Z_{h(n)}|}$ and $x'_k \in [0, 1]^{|Z_k|}$,

$$ |f(x_1, \dots, x_k, \dots, x_{h(n)}) - f(x_1, \dots, x'_k, \dots, x_{h(n)})| \le \frac{1'}{n}, $$

Lemma 1 applied to $V_n$ finishes the proof. $\square$

In the remainder of the proof, we show that $\mathbb{E}[V_n]$ converges to a constant polynomially fast. Next, we state and prove an auxiliary lemma relating the values of games of different lengths.

**Lemma 4.** Fix integers $n \ge 1$ and $k \in [1, n]$. Then, $|V_n - V_{n-k}| \le k/n$.

*Proof.* Suppose that Player 1 (resp. Player 2) plays the first $n-k$ stages according to an optimal strategy for the $(n-k)$-stage game, and plays arbitrarily during the remaining $k$ stages of the $n$-stage game. Then, $nV_n \ge (n-k)V_{n-k}$ and $nV_n \le (n-k)V_{n-k} + k$. Hence, $|n(V_n - V_{n-k})| \le \max(kV_{n-k}, k - kV_{n-k}) \le k$, which implies the statement of the lemma. $\square$

The next lemma shows that starting from different initial states changes the $n$-value only slightly when $n$ is large.

**Lemma 5.** For every $z \in Z$, $|\mathbb{E}[V_n(z)] - \mathbb{E}[V_n(z^*)]| = O(n^{-\delta})$.
**Proof.** Denote by $E$ the set of states $z \in Z^{(M)}$ that are equivalent to $z^*$. By Definition 1, independently of the moves of Player 2, $E \neq \emptyset$, and Player 1 can ensure that the token is at a state in $E$ after an even number of $\ell \le M$ stages. Hence, using Lemma 4, we have

$$nV_n \ge (n-M) \min_{z \in E} V_{n-M}(z) \ge (n-M) \min_{z \in E} (V_n(z) - M/n) \ge \min_{z \in E} nV_n(z) - 2M. \quad (1)$$

Now, we bound from below the expectation of the right-hand side. Let $\Delta$ be the maximum out-degree of $\Gamma$. Then, $|E| \le |Z^{(M)}| \le 1 + \Delta + \dots + \Delta^M \le (M+1)\Delta^M$ together with the choice of $\varepsilon_n$ from Definition 2 imply that

$$\begin{aligned} \mathbb{E}\left[\min_{z \in E} V_n(z)\right] &\ge (\mathbb{E}[V_n(z^*)] - \varepsilon_n)(1 - \mathbb{P}(\exists z \in E : V_n(z) \le \mathbb{E}[V_n(z)] - \varepsilon_n)) \\ &\ge (\mathbb{E}[V_n(z^*)] - \varepsilon_n)(1 - (M+1)\Delta^M \psi(n, \varepsilon_n)) = \mathbb{E}[V_n(z^*)] - O(n^{-\delta}), \end{aligned} \quad (2)$$

where the second inequality comes from a union bound and the last equality is implied by the fact that $\varepsilon_n + (M+1)\Delta^M \psi(n, \varepsilon_n) = O(n^{-\delta})$. Thus, taking expectations on both sides of (1) and using (2) shows that

$$\mathbb{E}[V_n] \ge \mathbb{E}[V_n(z^*)] - O(n^{-\delta} + 2M/n) = \mathbb{E}[V_n(z^*)] - O(n^{-\delta}). \quad (3)$$

Similarly, Player 2 can ensure that the token reaches a state in $E$ after an even number of $\ell \le M$ stages. Hence,

$$nV_n \le (n-M) \max_{z \in E} V_{n-M}(z) + M \le \max_{z \in E} nV_n(z) + M. \quad (4)$$

At the same time, similarly to (2), $\mathbb{E}[\max_{z \in E} V_n(z)]$ is bounded from above by

$$(\mathbb{E}[V_n(z^*)] + \varepsilon_n)(1 - \mathbb{P}(\exists z \in E : V_n(z) \ge \mathbb{E}[V_n(z)] + \varepsilon_n)) + \mathbb{P}(\exists z \in E : V_n(z) \ge \mathbb{E}[V_n(z)] + \varepsilon_n),$$

which is at most $\mathbb{E}[V_n(z^*)] + (\varepsilon_n + (M+1)\Delta^M \psi(n, \varepsilon_n)) = \mathbb{E}[V_n(z^*)] + O(n^{-\delta})$. Combining this with (4) shows that $\mathbb{E}[V_n] \le \mathbb{E}[V_n(z^*)] + O(n^{-\delta})$, and together with the upper bound in (3) this finishes the proof. $\square$

Next, we show that the expected value of $V_n$ converges as $n \to \infty$.

**Lemma 6.** There is a constant $v_\infty$ independent of the initial state such that $|\mathbb{E}[V_n]-v_\infty| = O(n^{-\delta})$ as $n \to \infty$.

**Proof.** By Lemma 5, it is sufficient to show the lemma assuming $z_0 = z^*$. First, we show that $\mathbb{E}[V_n]$ converges to a limit $v_\infty \in \mathbb{R}$ as $n \to \infty$. By Lemma 3 and a union bound, for all $t \ge 0$,

$$\begin{aligned} \mathbb{P}(\exists z \in Z^{(2n)}, |V_n(z) - \mathbb{E}[V_n(z)|] \ge t) &\le \sum_{z \in Z^{(2n)}} \mathbb{P}(|V_n(z) - \mathbb{E}[V_n(z)|] \ge t) \\ &\le 2 \exp\left(-\frac{t^2 n^2}{2h(n)}\right) \max_{z \in Z} |Z^{(2n)}(z)| = 2\psi(n, t). \end{aligned} \quad (5)$$

By definition of $\delta$-transient game, there exists $(\varepsilon_n)_{n \in \mathbb{N}}$ such that $\varepsilon_n + \psi(n, \varepsilon_n) = O(n^{-\delta})$. Denote by $E$ the set of vertices in $Z^{(2n)}$ that are equivalent to $z^*$. Now, Lemma 5 implies that there is a constant $K' > 0$ such that, for every $n \ge 1$, $|\mathbb{E}[V_n(z)] - \mathbb{E}[V_n]| \le K'n^{-\delta}$. Combining this with (5), we get that

$$\begin{aligned} \mathbb{P}\left(\min_{z \in Z^{(2n)}} V_n(z) \le \mathbb{E}[V_n] - \varepsilon_n - K'n^{-\delta}\right) &\le \mathbb{P}\left(\min_{z \in Z^{(2n)}} |V_n(z) - \mathbb{E}[V_n(z)]| \ge \varepsilon_n\right) \\ &\le \mathbb{P}(\exists z \in E, |V_n(z) - \mathbb{E}[V_n(z)]| \ge \varepsilon_n) \\ &\le 2\psi(n, \varepsilon_n) = O(n^{-\delta}). \end{aligned}$$
In particular, it follows directly that

$$ 
\begin{aligned}
\mathbb{E}\left[\min_{z \in \mathbb{Z}^{(2n)}} V_n(z)\right] &\geq \left(\mathbb{E}[V_n] - \varepsilon_n - K'n^{-\delta}\right) \mathbb{P}\left(\min_{z \in \mathbb{Z}^{(2n)}} V_n(z) \geq \mathbb{E}[V_n] - \varepsilon_n - K'n^{-\delta}\right) \\
&\geq \left(\mathbb{E}[V_n] - \varepsilon_n - K'n^{-\delta}\right) (1 - 2\psi(n, \varepsilon_n)) \geq \mathbb{E}[V_n] - 2(\psi(n, \varepsilon_n) + \varepsilon_n) - K'n^{-\delta}.
\end{aligned}
$$

Now, fix an integer $m \in [1, 2n]$ and consider the $(m+n)$-stage game. Suppose that Player 1 plays according to an optimal strategy for the $m$-stage game up to stage $m$ and, once the $m$-stage game terminates at a state $z_m$, continues to play according to an optimal strategy for the subsequent $n$-stage game. Note that $z_m \in \mathbb{Z}^{(2n)}$, so the above strategy of Player 1 for the first $m+n$ steps guarantees a gain of $\frac{m}{m+n}V_m + \frac{n}{m+n}\min_{z \in \mathbb{Z}^{(2n)}} V_n(z)$. Thus,

$$ 
\begin{aligned}
(m+n)\mathbb{E}[V_{m+n}] &\geq m\mathbb{E}[V_m] + n\mathbb{E}\left[\min_{z \in \mathbb{Z}^{(2n)}} V_n(z)\right] \\
&\geq m\mathbb{E}[V_m] + n\mathbb{E}[V_n] - 2n(\psi(n, \varepsilon_n) + \varepsilon_n) - K'n^{1-\delta}.
\end{aligned}
\quad (6) $$

Since $\psi(n, \varepsilon_n) + \varepsilon_n = O(n^{-\delta})$, there is a constant $K'' > 0$ such that, for all $n \geq 1$,

$$ 2n(\psi(n, \varepsilon_n) + \varepsilon_n) + K'n^{1-\delta} \leq 2K''n^{1-\delta}. $$

Thus, using Lemma 2 with $f: n \mapsto -n\mathbb{E}[V_n]$ and $\phi: n \mapsto 2K''n^{1-\delta}$ (note that $\phi$ is increasing and $\sum_{n \geq 1} \phi(n)/n^2 = 2K''\sum_{n \geq 1} 1/n^{1+\delta} < \infty$) implies that $\mathbb{E}[V_n]$ converges to a limit $v_\infty \in \mathbb{R} \cup \{\infty\}$ as $n \to \infty$. Note that $v_\infty$ is in $[0, 1]$ since this is the support of all payoff variables.

Finally, using (6) with $m=n$, for every $n \geq 1$, we have that

$$ \mathbb{E}[V_{2n}] \geq \mathbb{E}[V_n] - (\psi(n, \varepsilon_n) + \varepsilon_n) - \frac{K'n^{-\delta}}{2} \geq \mathbb{E}[V_n] - K''n^{-\delta}. $$

In particular, for all integers $\ell, n \geq 1$, iterating the above observation for $n, 2n, \dots, 2^{\ell-1}n$ gives that

$$ \mathbb{E}[V_{2\ell_n}] \geq \mathbb{E}[V_n] - K''n^{-\delta} \sum_{j=0}^{\ell-1} 2^{-\delta j} \geq \mathbb{E}[V_n] - \frac{K''}{1-2^{-\delta}} n^{-\delta}. \quad (7) $$

Taking $\ell \to \infty$, we conclude that $v_\infty \geq \mathbb{E}[V_n] - O(n^{-\delta})$. A similar reasoning exchanging Player 1 with Player 2 shows that $v_\infty \leq \mathbb{E}[V_n] + O(n^{-\delta})$ and concludes the proof of the lemma. $\square$

Finally, we are ready to prove Theorem 1.

*Proof of Theorem 1.* Fix an arbitrary $\varepsilon > 0$. By Lemma 6, there is a constant $K > 0$ such that $|v_\infty - \mathbb{E}[V_n]| \leq Kn^{-\delta}$ for all $n \geq 1$, independently of the initial state. Combining this with the triangle inequality and Lemma 3 shows that, for every $t \geq 0$,

$$ 
\begin{aligned}
\mathbb{P}(|V_n - v_\infty| \geq t + Kn^{-\delta}) &\leq \mathbb{P}(|V_n - \mathbb{E}[V_n]| \geq t + Kn^{-\delta} - |\mathbb{E}[V_n] - v_\infty|) \\
&\leq \mathbb{P}(|V_n - \mathbb{E}[V_n]| \geq t) \leq 2 \exp\left(\frac{-t^2n^2}{2h(n)}\right),
\end{aligned}
$$

which is the desired result. $\square$

# 5 Directed games on trees: proof of Theorem 2

The first lemma in this section bootstraps upon the conclusion of Lemma 3 (which still holds in this setting), thus deriving superexponential concentration for the value of the $n$-stage game. Below, log stands for the natural logarithm.
**Lemma 7.** Fix $\delta \in (0, 1/2)$ and $t \ge n^{-\delta}$. For every integer $n \ge 1$ and even integer $k \in [2, n]$ such that

$$k \log d + 2 \log 2 \le t^2(n-k), \quad (8)$$

we have

$$\mathbb{P}(nV_n - (n-k)\mathbb{E}[V_{n-k}] \ge (n-k)t + k) \le \exp\left(-\frac{d^{k/2}}{6}\right),$$

$$\mathbb{P}(nV_n - (n-k)\mathbb{E}[V_{n-k}] \le -(n-k)t - k) \le \exp\left(-\frac{d^{k/2}}{6}\right).$$

*Proof.* First of all, since $T$ is a transitive graph, for all $n \ge 1$, $(V_n(z))_{z \in Z}$ have the same distribution. For every even integer $k \in [n]$, denote

$$S_k := \{z \in Z_k : V_{n-k}(z) - \mathbb{E}[V_{n-k}] \ge t\}.$$

In other words, $S_k$ is the set of vertices that could be reached from $z_0$ after $k$ stages, for which the value of the $(n-k)$-stage game starting at $z$ is greater than or equal to $\mathbb{E}[V_{n-k}] + t$.

Define the event $\mathcal{E}_k := \{|S_k| \ge d^{k/2}\}$. We provide an upper bound for $\mathbb{P}(\mathcal{E}_k)$. Since the random variables $(V_{n-k}(z))_{z \in Z_k}$ are i.i.d., we have that $|S_k|$ follows a binomial distribution $\text{Bin}(d^k, q)$ where $q := \mathbb{P}(V_{n-k} \ge \mathbb{E}[V_{n-k}] + t)$. Consequently, by Lemma 3 (where $h(n) = n$ is the transient speed of the family of partitions $(\Pi_z)_{z \in Z}$ where, for all $z \in Z$ and $k \ge 2$, $Z_k(z)$ contains all descendants of $z$ at distance $k$), $|S_k|$ is stochastically dominated by a binomial random variable $\text{Bin}(d^k, \tilde{q})$ where $\tilde{q} = \exp(-t^2(n-k)/2)$. In particular,

$$\mathbb{P}(\mathcal{E}_k) \le \mathbb{P}\left(\text{Bin}(d^k, \tilde{q}) \ge d^{k/2}\right).$$

The random variable $\text{Bin}(d^k, \tilde{q})$ has mean $\mu := d^k \tilde{q}$. We define

$$\xi := \frac{d^{k/2}}{\mu} - 1 = \exp\left(\frac{t^2(n-k) - k \log(d)}{2}\right) - 1 \ge 1,$$

where the last inequality comes from (8). Since $d^{k/2} = (1 + \xi)\mu$, we have that

$$\mathbb{P}(\text{Bin}(d^k, \tilde{q}) \ge d^{k/2}) = \mathbb{P}(\text{Bin}(d^k, \tilde{q}) \ge (1 + \xi)\mu).$$

Therefore, since $\xi \ge 1$ (so $3\xi \ge 2 + \xi$), by Chernoff's bound,

$$\mathbb{P}\left(\text{Bin}(d^k, \tilde{q}) \ge d^{k/2}\right) \le \exp\left(-\frac{\xi^2\mu}{2+\xi}\right) \le \exp\left(-\frac{\xi\mu}{3}\right) = \exp\left(-\frac{d^{k/2}}{3}\left(1-d^{k/2}\tilde{q}\right)\right).$$

Since $\xi = 1/(d^{k/2}\tilde{q}) - 1 \ge 1$, we have that $1 - d^{k/2}\tilde{q} \ge 1/2$, which finally yields

$$\mathbb{P}(\mathcal{E}_k) \le \exp\left(-\frac{d^{k/2}}{6}\right). \quad (9)$$

At the same time, on the event $|S_k| < d^{k/2}$ (that is, $\overline{\mathcal{E}}_k$), Player 2 can ensure that the token avoids ending up in $S_k$ after $k$ stages. Indeed, at each of the $k/2 \in \mathbb{N}$ turns corresponding to decisions of Player 2, by the pigeonhole principle, Player 2 can always move the token to a vertex having at most a $(1/d)$-fraction of all remaining elements in $S_k$ among its descendants. Since Player 2 has $k/2$ turns and $d^{-k/2}|S_k| < 1$, Player 2 can safely avoid the set $S_k$ at stage $k$.

Let us condition on the event $\overline{\mathcal{E}}_k$. Then, Player 2 can guarantee that the sum of the payoffs over the last $n-k$ stages is strictly smaller than $(n-k)(\mathbb{E}[V_{n-k}] + t)$. Moreover, the sum of the
first $k$ payoffs is at most $k$. Consequently, Player 2 can guarantee that, after $n$ stages, the global mean payoff is strictly smaller than $k/n + (n-k)(\mathbb{E}[V_{n-k}] + t)/n$, in other words,

$$nV_n < (n-k)\mathbb{E}[V_{n-k}] + (n-k)t + k. \qquad (10)$$

In particular, using (9) implies that

$$\mathbb{P}(nV_n - (n-k)\mathbb{E}[V_{n-k}] \ge (n-k)t + k) \le \mathbb{P}(|S_k| \ge d^{k/2}) = \mathbb{P}(\mathcal{E}_k) \le \exp\left(-\frac{d^{k/2}}{6}\right).$$

A similar reasoning for Player 1 (using the sets $\tilde{S}_k := \{z \in Z_k : V_{n-k}(z) - \mathbb{E}[V_{n-k}] \le -t\}$ instead of $S_k$ and replacing (10) with $nV_n > (n-k)\mathbb{E}[V_{n-k}] - (n-k)t$) yields

$$\mathbb{P}(nV_n - (n-k)\mathbb{E}[V_{n-k}] \le -(n-k)t) \le \exp\left(-\frac{d^{k/2}}{6}\right),$$

which implies the second statement. Note that the additional $-k$ in it is introduced for reasons of symmetry only. □

Next, we show that the expected value of the $n$-stage game converges rapidly as $n$ grows to infinity.

**Lemma 8.** There exists $v_\infty \in \mathbb{R}$ such that, for every $\delta \in (0, 1/2)$, we have $|\mathbb{E}[V_n] - v_\infty| = O(n^{-\delta})$ as $n \to \infty$.

*Proof.* Fix $\delta' \in (0, 1/2)$ and $t \ge n^{-\delta'}$. For each $n \ge 1$, we set $k = k(n) := 2\lfloor n^{1-2\delta'}/4 \log d \rfloor$. Then, $k \log d + 2 \log 2 \le t^2(n-k)$ for all large $n$. For every even integer $m \in [n/2, 2n]$ and large $n$, we have

$$\begin{aligned} \mathbb{P}\left(\min_{z \in Z_m} nV_n(z) \le (n-k)(\mathbb{E}[V_{n-k}] - t) - k\right) &\le \sum_{z \in Z_m} \mathbb{P}(nV_n(z) \le (n-k)(\mathbb{E}[V_{n-k}] - t) - k) \\ &\le d^m \exp\left(-\frac{d^{k/2}}{6}\right) \\ &\le \exp\left(2n \log d - \frac{d^{\lfloor n^{1-2\delta'}/4 \log d \rfloor}}{6}\right), \end{aligned}$$

where the first inequality comes from a union bound and the second inequality comes from Lemma 7. Fix $\delta \in (0, \delta')$ and define, for all $n \ge 1$,

$$\varepsilon_n := n^{-\delta} \quad \text{and} \quad \psi(n) := \exp\left(2n \log d - d^{\lfloor n^{1-2\delta'}/4 \log d \rfloor/6}\right).$$

For large $n$ and every even integer $m \in [n/2, 2n]$, we have

$$\begin{aligned} \mathbb{E}\left[\min_{z \in Z_m} V_n(z)\right] &\ge \left(\frac{n-k}{n}(\mathbb{E}[V_{n-k}] - \varepsilon_n) - \frac{k}{n}\right) \mathbb{P}\left(\min_{z \in Z_m} nV_n(z) > (n-k)(\mathbb{E}[V_{n-k}] - \varepsilon_n) - k\right) \\ &\ge \left(\frac{n-k}{n}(\mathbb{E}[V_{n-k}] - \varepsilon_n) - \frac{k}{n}\right)(1 - \psi(n)) \\ &\ge \left(\mathbb{E}[V_{n-k}] - \frac{k}{n}(1 + \mathbb{E}[V_{n-k}]) - \varepsilon_n\right)(1 - \psi(n)) \\ &\ge \left(\mathbb{E}[V_n] - \frac{3k}{n} - \varepsilon_n\right)(1 - \psi(n)) \ge \mathbb{E}[V_n] - (\psi(n) + 2\varepsilon_n), \end{aligned} \qquad (11)$$
where in the fourth inequality we used that $\mathbb{E}[V_n] \le \mathbb{E}[V_{n-k}] + k/n$ by Lemma 4 and $1 + \mathbb{E}[V_{n-k}] \le 2$, and the last inequality is valid for large $n$ because $k/n = o(\varepsilon_n)$.

Consider integers $n \ge 1$ and even $m \in [n/2, 2n]$. In the $(n+m)$-stage game, Player 1 can play according to an optimal strategy for the $m$-stage game starting at $z_0$, and then play according to an optimal strategy for the $n$-stage game starting from the state $z$ reached after $m$ stages. This guarantees that $(m+n)V_{m+n} \ge mV_m + \min_{z \in Z_m} nV_n(z)$. Taking expectations on both sides and using (11) yields

$$ (m+n)\mathbb{E}[V_{m+n}] \ge m\mathbb{E}[V_m] + n\mathbb{E}\left[\min_{z \in Z_m} V_n(z)\right] \ge m\mathbb{E}[V_m] + n\mathbb{E}[V_n] - n(\psi(n) + 2\varepsilon_n). $$

We find a similar inequality for odd $m \in [n/2, 2n]$. In this case, $m+1$ is even and also in $[n/2, 2n]$. Then, the previous inequality applied to $m+1$ and $n$ yields

$$ (m+n+1)\mathbb{E}[V_{m+n+1}] \ge (m+1)\mathbb{E}[V_{m+1}] + n\mathbb{E}[V_n] - n(\psi(n) + 2\varepsilon_n). \quad (12) $$

However,

$$ (m+n)\mathbb{E}[V_{m+n}] \ge (m+n+1)\mathbb{E}[V_{m+n+1}] - 1 \quad \text{and} \quad (m+1)\mathbb{E}[V_{m+1}] \ge m\mathbb{E}[V_m], $$

which combined with (12) gives

$$ (m+n)\mathbb{E}[V_{m+n}] \ge m\mathbb{E}[V_m] + n\mathbb{E}[V_n] - n(\psi(n) + 2\varepsilon_n) - 1. $$

To sum things up, for large $n$ and $m \in [n/2, 2n]$,

$$ (m+n)\mathbb{E}[V_{m+n}] \ge m\mathbb{E}[V_m] + n\mathbb{E}[V_n] - n(\psi(n) + 2\varepsilon_n) - 1. \quad (13) $$

Recall that there is a constant $K' > 0$ such that, for all $n \ge 1$, $n(\psi(n) + 2\varepsilon_n) + 1 \le K'n^{1-\delta}$. We define $\phi(n) := K'n^{1-\delta}$ and deduce from (13) that

$$ (m+n)\mathbb{E}[V_{m+n}] \ge m\mathbb{E}[V_m] + n\mathbb{E}[V_n] - \phi(n+m). $$

Moreover, $\phi$ is increasing and verifies $\sum_{n \ge 1} \phi(n)/n^2 < \infty$. Consequently, Lemma 2 applied to the function $f: n \in \mathbb{N} \mapsto -n\mathbb{E}[V_n]$ implies that $\mathbb{E}[V_n]$ converges to a limit $v_\infty \in \mathbb{R} \cup \{\infty\}$ as $n \to \infty$. Note that $v_\infty \in [0, 1]$ since $V_n \in [0, 1]$ for all $n \ge 1$.

Finally, using (13) with $m=n$ and a telescopic summation shows that the inequality (7) still. In particular, we conclude that $v_\infty \ge \mathbb{E}[V_n] - O(n^{-\delta})$. A similar reasoning replacing Player 1 with Player 2 shows that $v_\infty \le \mathbb{E}[V_n] + O(n^{-\delta})$ and concludes the proof of the lemma. $\square$

We are now ready to prove Theorem 2.

*Proof of Theorem 2.* Fix $t \ge n^{-\delta}$ and let $K'$ be a constant such that $|\mathbb{E}[V_n] - v_\infty| \le K'n^{-\delta}$ for all large $n$. Using that, for all $n$ and $k \le n$, we have $|nV_n - (n-k)V_{n-k}| \le k$, and fixing $k = 2^{\lceil \frac{t^2n}{4\log d} \rceil}$ (which satisfies (8)), we get

$$ \begin{aligned} & \mathbb{P}(|V_n - v_\infty| \ge t + 2t^2 + K'n^{-\delta}) \\ \le & \mathbb{P}\left(\left|V_n - \frac{n-k}{n}\mathbb{E}[V_{n-k}]\right| \ge t + 2t^2 + K'n^{-\delta} - \left|\frac{n-k}{n}\mathbb{E}[V_{n-k}] - \mathbb{E}[V_n]\right| - |\mathbb{E}[V_n] - v_\infty|\right) \\ \le & \mathbb{P}\left(\left|V_n - \frac{n-k}{n}\mathbb{E}[V_{n-k}]\right| \ge t + t^2\right) \\ \le & \mathbb{P}(|nV_n - (n-k)\mathbb{E}[V_{n-k}|] \ge (n-k)t + k) \\ \le & \exp\left(-\frac{d^{[k/2]}}{6}\right) \le \exp\left(-\frac{d^{2n/(4\log d)}}{6}\right) = \exp\left(-\frac{1}{6}\exp\left(\frac{t^2n}{4}\right)\right), \end{aligned} $$
where the first inequality comes from the triangle inequality, the second inequality comes from the definition of $K'$ and the fact that $|nV_n - (n-k)V_{n-k}| \le k \le nt^2$, and the third inequality once again uses the fact that $k \le nt^2$.

Finally, choosing $K \ge K'$ sufficiently large ensures that, first, the upper bound shown above holds for all $n \ge 1$ (and not only for large $n$), and second, the upper bound holds for all $t \ge 0$, which finishes the proof. □

# 6 Oriented directed games: proof of Proposition 1

We present a simple and self-contained proof of Proposition 1.

*Proof.* First, by density of the rational vectors in $\mathbb{R}^d$ and rescaling, we may assume that $u \in \mathbb{Z}^d$ is such that the greatest common divisor of its coordinates is 1. Then, for every integer $i \ge 1$ and initial state $z_0 = z$, defining $Z_{2i}(z) := \{w \in Z : w \cdot u = z \cdot u + i\}$, $Z_{2i+1}(z) := \{w \in Z : w \cdot u = z \cdot u - i\}$, and $Z_1(z) := \{w \in Z : \{z\} : w \cdot u = z \cdot u\}$ shows that the game is directed. Indeed, $(Z_i(z))_{i \ge 0}$ form a partition of $Z$ for all $z \in Z$, and each of them could be visited at most once by the token.

Now, fix $\delta \in (0, 1/2)$ and $z_0 = z \in Z$. To see that the game is $\delta$-transient, set $r = \max_{uv \in E(\Gamma)} \|v-u\|_2$. After $n$ steps of the process, the position $z_n$ of the token satisfies $\|z_n - z\|_2 \le nr$, and by the Cauchy-Schwarz inequality,

$$|(z_n - z) \cdot u| \le \|z_n - z\|_2 \cdot \|u\|_2 \le \lceil nr \cdot \|u\|_2 \rceil =: M = M(n).$$

In particular, $Z^{(n)}(z)$ is contained in the ball with radius $M$ around $z$, which itself is contained in $Z_{[2M+1]}(z)$, so the transient speed of the process satisfies $h(n) \le 2M(n)+1$ for all $n \ge 1$. Finally, take $\delta \in (0, 1/2)$ and set $\varepsilon_n := n^{-\delta}$. Then,

$$ \begin{aligned} \psi(n, \varepsilon_n) &= \exp\left(-\frac{\varepsilon_n^2 n^2}{2h(n)}\right) \max_{z \in Z} |Z^{(2n)}(z)| \\ &\le \exp\left(-\frac{\varepsilon_n^2 n}{6r \cdot \|u\|_2}\right) (2nr \cdot \|u\|_2 + 1)^d \\ &= \exp\left(-\frac{n^{1-2\delta}}{6r \cdot \|u\|_2}\right) (2nr \cdot \|u\|_2 + 1)^d = O(n^{-\delta}). \end{aligned} $$

Hence, for all $\delta \in (0, 1/2)$, $\varepsilon_n + \psi(n, \varepsilon_n) = O(n^{-\delta})$, and therefore, the game is $\delta$-transient. □

# Acknowledgments

This work was supported by the French Agence Nationale de la Recherche (ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002 (GrHyDy), and by Fondecyt grant 1220174. This collaboration was mainly conducted during a 1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling (CMM) at University of Chile in 2023, under the IRL program of CNRS.

# References

[1] N. Alon, K. Rudov, and L. Yariv. Dominance solvability in random games. *arXiv preprint arXiv:2105.10743*, 2021. 1

[2] B. Amiet, A. Collevecchio, M. Scarsini, and Z. Zhong. Pure Nash equilibria and best-response dynamics in random games. *Mathematics of Operations Research*, 46(4):1552–1572, 2021. 1
[3] A. Auffinger, M. Damron, and J. Hanson. *50 years of first-passage percolation*, volume 68. American Mathematical Society, 2017. 1

[4] D. Bhasin, S. Karmakar, M. Podder, and S. Roy. On a class of PCA with size-3 neighborhood and their applications in percolation games. *Electronic Journal of Probability*, 28:1–60, 2023. 1

[5] N. Govert de Bruijn and P. Erdős. Some linear and some quadratic recursion formulas II. *Indagationes Mathematicae (Proceedings)*, 55:152–163, 1952. 2

[6] D.-Z. Du and P. M. Pardalos. *Minimax and applications*, volume 4. Springer Science & Business Media, 1995. 2

[7] J. Flesch, A. Predtetchinski, and V. Suomala. Random perfect information games. *Mathematics of Operations Research*, 48(2):708–727, 2023. 1

[8] G. Garnier and B. Ziliotto. Percolation games. *Mathematics of Operations Research*, 48(4):2156–2166, 2023. 1, 2

[9] T. Garrec. Communicating zero-sum product stochastic games. *Journal of Mathematical Analysis and Applications*, 477(1):60–84, 2019. 1

[10] Torsten Heinrich, Yoojin Jang, Luca Mungo, Marco Pangallo, Alex Scott, Bassel Tarbush, and Samuel Wiese. Best-response dynamics, playing sequences, and convergence to equilibrium in random games. *International Journal of Game Theory*, 52(3):703–735, 2023. 1

[11] A. E. Holroyd, I. Marcovici, and J. B. Martin. Percolation games, probabilistic cellular automata, and the hard-core model. *Probability Theory and Related Fields*, 174:1187–1217, 2019. 1

[12] S. Janson, T. Łuczak, and A. Ruciński. *Random Graphs*. John Wiley & Sons, Inc., 2000. 1

[13] R. Laraki and J. Renault. Acyclic gambling games. *Mathematics of Operations Research*, 45(4):1237–1257, 2020. 1

[14] R. Laraki and S. Sorin. Advances in zero-sum dynamic games. In *Handbook of game theory with economic applications*, volume 4, pages 27–93. Elsevier, 2015. 1

[15] E. Solan and B. Ziliotto. Stochastic games with signals. *Advances in Dynamic and Evolutionary Games: Theory, Applications, and Numerical Methods*, pages 77–94, 2016. 1

[16] J. von Neumann. Zur Theorie der Gesellschaftsspiele. *Mathematische Annalen*, 100(1):295–320, 1928. 2

[17] B. Ziliotto. Zero-sum repeated games: counterexamples to the existence of the asymptotic value and the conjecture $\maxmin = \lim v(n)$. *The Annals of Probability*, 44(2):1107–1133, 2016. 1

[18] B. Ziliotto. Mertens conjectures in absorbing games with incomplete information. *arXiv preprint arXiv:2106.09405*, to appear in *The Annals of Applied Probability*, 2021. 1