Frédéric Koessler
email: frederic.koessler@psemail.eu.

Marie Laclau

Jérôme Renault
email: jerome.renault@tse-fr.eu.

Tristan Tomala
email: tomala@hec.fr

"Splitting games over finite sets"

Keywords: Splitting games, Mertens-Zamir system, repeated games with incomplete information, Bayesian persuasion, information design. MSC: Stochastic games 91A15, Bayesian games 91A27

This paper studies zero-sum splitting games with finite sets of states. Players dynamically choose a pair of martingales {p t , q t } t , in order to control a terminal payoff u(p ∞ , q ∞ ). A first part introduces the notion of "Mertens-Zamir transform" of a real-valued matrix and use it to approximate the solution of the Mertens-Zamir system for continuous functions on the square [0, 1] 2 . A second part considers the general case of finite splitting games with arbitrary correspondences containing the Dirac mass on the current state: building on Laraki and Renault (2020), we show that the value exists by constructing non Markovian ε-optimal strategies and we characterize it as the unique concave-convex function satisfying two new conditions.

Introduction

This paper deals with the Mertens-Zamir system of functional equations described as follows. For K, L two non-empty finite sets, ∆(K) and ∆(L) denote the simplices of probability distributions over K and L, respectively viewed as subsets of the Euclidean spaces R K and R L . Given a continuous function u : ∆(K) × ∆(L) → R, the Mertens-Zamir system of functional equations is given by: v(p, q) = cav p min{u(p, q), v(p, q)} = vex q max{u(p, q), v(p, q)}, where cav p (resp. vex q ) denotes concavification, i.e., least concave majorant on ∆(K), with respect to the first variable (resp. convexification with respect to the second variable). This system is introduced by Mertens andZamir (1971, 1977) who prove existence and uniqueness of a continuous solution v = MZ(u), called the Mertens-Zamir transform of u. [START_REF] Mertens | The value of two-person zero-sum repeated games with lack of information on both sides[END_REF] study zero-sum repeated games with incomplete information whose payoffs depend on a pair of parameters (k, l), where k is known by Player 1 and l by Player 2. The key difficulty in analyzing these games is to capture how each player optimally controls the martingale of Bayesian beliefs, or posteriors, of the opponent. [START_REF] Mertens | The value of two-person zero-sum repeated games with lack of information on both sides[END_REF] prove that the limit of the value function, as the length of the game tends to infinity, is the unique solution of this system where u is the value of the non revealing game (see also [START_REF] Mertens | A duality theorem on a pair of simultaneous functional equations[END_REF][START_REF] Sorin | On a pair of simultaneous functional equations[END_REF], Sorin, 2002[START_REF] Mertens | Repeated Games[END_REF].

An equivalent characterization [START_REF] Heuer | Asymptotically optimal strategies in repeated games with incomplete information[END_REF]Laraki, 2001b;[START_REF] Rosenberg | An operator approach to zero-sum repeated games[END_REF] uses the notion of splitting. A splitting of p ∈ ∆(K) is a Borel probability distribution s over ∆(K) with mean p, i.e. such that p∈∆(K) p ds(p) = p. The MZ transform v = MZ(u) is the unique continuous map v : ∆(K) × ∆(L) → R which is concave in the first variable, convex in the second variable, and such that for all (p, q) in ∆(K) × ∆(L), the two following conditions hold:1 (C1) if v(p, q) > u(p, q) there exists a splitting s of p such that v(p, q) = v(s, q) = u(s, q), and (C2) if v(p, q) < u(p, q) there exists a splitting r of q such that v(p, q) = v(p, r) = u(p, r). Still, computing v = MZ(u) in general is a very difficult problem.

The study has been continued in Sorin (2002) and Laraki (2001a,b) who introduced in this setup the notion of splitting game, a discrete time zero-sum stochastic game with state variable (p, q) in ∆(K) × ∆(L), which unfolds as follows. An initial state (p 1 , q 1 ) is given. At every stage t ≥ 1, Player 1 chooses a splitting s of p t and Player 2 chooses a splitting r of q t , choices are simutaneous. The next state (p t+1 , q t+1 ) is then drawn from the product probability s ⊗ r, and observed by both players before playing stage t + 1. Given a strategy profile, the state variables (p t , q t ) form a martingale with values in ∆(K) × ∆(L) which converges almost surely to random variables (p ∞ , q ∞ ). There are several ways to evaluate payoffs in the splitting game. A standard one is to consider, for each discount rate λ ∈ (0, 1], the value v λ (p 1 , q 1 ) of the game in which the payoff is the expectation of ∞ t=1 λ(1λ) t-1 u(p t , q t ). Mertens and Zamir's results imply that (v λ ) uniformly converges to MZ(u) as λ goes to 0. Another standard notion is the uniform value, which whenever it exists, is the real number v such that for each ε > 0, each player guarantees v up to ε, in all games with sufficiently large number of stages, payoffs being evaluated by the arithmetic average of stage payoffs. MZ(u) is also the uniform value of the undiscounted splitting game with stage payoffs u(p t , q t ) (Oliu- [START_REF] Oliu-Barton | The Splitting Game: Uniform Value and Optimal Strategies[END_REF].

The recent literature on information design and Bayesian persuasion [START_REF] Kamenica | Bayesian Persuasion[END_REF][START_REF] Bergemann | Information design: A unified perspective[END_REF][START_REF] Koessler | Interactive Information Design[END_REF] has given new interpretation and applications to splitting games: choosing a splitting amounts to choosing an information structure, and information design considers optimization problems or games over information structures. In Koessler, Laclau, Renault, and Tomala (2021a), we consider a zero-sum splitting game between two information designers who provide information to a decision maker, and where u(p, q) represents the expected payoff induced by the action chosen by the decision maker who has belief (p, q). MZ(u) is also the value of the splitting game with terminal payoff (long information design game) where the payoff of the splitting game is simply the expectation of u(p ∞ , q ∞ ). [START_REF] Laraki | Acyclic Gambling Games[END_REF] generalize the model of splitting games to gambling games where a player can choose the distribution of the next state from a set of feasible distributions. They show that, under some assumptions including a notion of strong acyclicity of the trajectories, these games also admit a value which is a generalized MZ transform of u for gambling games. The approach lim λ→0 v λ = MZ(u) is particularly useful to prove the existence of MZ(u) (by considering a uniform limit point of (v λ )). This approach has been followed in [START_REF] Laraki | Acyclic Gambling Games[END_REF] and Koessler et al. (2021a) to prove the existence of the MZ transform for general classes of games (strongly acyclic gambling games, information design games with experiments).

In this paper, we consider splitting games with terminal payoffs2 and finite sets of states/admissible posteriors. In Section 2, we consider a simple finite case and define a notion of MZ transform for a real valued matrix. We show that MZ(U ) is the value of a splitting game with payoffs given by a matrix U and derive several properties. We also show how to compute the Mertens-Zamir transform and in Section 3, we construct an algorithm approximating v = MZ(u) for a continuous u : [0, 1] 2 → R (the unidimensional case for ∆(K) and ∆(L)). In Theorem 1, we discretize u to obtain a matrix U and prove that the piecewise biaffine extension of the matrix V = MZ(U ) is a uniform approximation of MZ(u). We also show that in both setups, the Mertens-Zamir transform may differ from the value of the one-shot splitting game, where there is a single stage and the payoff is the expectation of u(p 1 , q 1 ), as defined in Laraki (2001a). In section 4, we introduce a general model of splitting games over finite sets, where the splittings available at a given p always allow to stay at p but may be arbitrarily constrained otherwise. Contrary to the existing litterature [START_REF] Laraki | Acyclic Gambling Games[END_REF]Koessler et al., 2021a), we make no further assumption such as acyclicity or closedness under iteration. In Theorem 2, we prove the existence of the value via the construction of non Markovian ε-optimal pure strategies and provide a new characterization of the value with conditions replacing (C1) and (C2) above. We conclude with a few open questions.

The M Z transform of a matrix

Given non-negative integers m, n, the set of real-valued matrices with set of rows I = {0, . . . , m} and set of columns J = {0, . . . , n} is R I×J . We use the product order on R I×J : we say that U is weakly greater than U and write U U if u i,j ≥ u i,j for all i and j. We first introduce particular notions of concavity and convexity.

Definition 1. Let U = (u i,j ) be a matrix in R I×J . U is column-concave if: ∀j ∈ J, ∀i ∈ {1, . . . , m -1}, u i,j ≥ 1 2 (u i-1,j + u i+1,j ). U is row-convex if: ∀i ∈ I, ∀j ∈ {1, . . . , n -1}, u i,j ≤ 1 2 (u i,j-1 + u i,j+1
).

To illustrate this definition, consider for each column j the map (i → u i,j ) from I ⊂ R to R. Then U is column-concave if for each j in J, the piecewise linear interpolation of (i → u i,j ) is a concave map from [0, m] to R. Similarly, U is row-convex if for each row i in I, the piecewise linear interpolation of

(j → u i,j ) is a convex map on [0, n].
Definition 2. Let U = (u i,j ) be a matrix in R I×J . The column-concave envelope of U , denoted cav U , is the smallest column-concave matrix which is weakly greater than U . The row-convex envelope of U , denoted vex(U ), is the greatest row-convex matrix which is weakly smaller than U .

We always have cav(U )

U vex(U ). To compute cav(U ), one can proceed independently for each column j: replace for each i in {1, . . . , m -1} the entry u i,j by max{u i,j , 1 2 u i-1,j + 1 2 u i+1,j }, and iterate until it stabilizes. To compute vex(U ), one can proceed independently for each row i: replace for each j in {1, . . . , n -1} the entry u i,j by min{u i,j , 1 2 u i-1,j + 1 2 u i+1,j }, and iterate until it stabilizes. One can show that cav(vex U ) and vex(cav U ) are both column-concave and row-convex.

We now define the Mertens-Zamir transform of a matrix.

Proposition 1. Given a matrix U in R I×J , there exists a unique matrix V in R I×J that is columnconcave, row-convex and such that for all (i, j) ∈ I × J:

if v i,j > u i,j , then 1 < i < n and v i,j = 1 2 (v i-1,j + v i+1,j ), and if v i,j < u i,j , then 1 < j < p and v i,j = 1 2 (v i,j-1 + v i,j+1
). By analogy with the continuous case, we say that V is the Mertens-Zamir transform of U , and write V = MZ(U ).

It is easy to see that if n = 0 then MZ(U ) = cav U , and if m = 0 then MZ(U ) = vex U . And one can check that MZ( This proposition is generalized in Theorem 2. The following proof of Proposition 1 is derived from [START_REF] Laraki | Acyclic Gambling Games[END_REF].

   0 1 0 1 0 1 0 1 0   ) =    0 0 0 1 0 1 0 0 0    and MZ(       6 4 2 1 4 2 4 3 1 4 2 5 0 3 4 7       ) =       6 4 2 1
Proof. 1) Existence can be derived from Propositions 1, 2, 3 in [START_REF] Laraki | Acyclic Gambling Games[END_REF], considering the splitting game where at each i in I, Player 1 can choose any mixed action between staying at i or inducing the distribution 1 2 δ i-1 + 1 2 δ i+1 if 0 < i < n, and similarly at each j in J, Player 2 can choose any mixed action between staying at j or inducing the distribution 1 2 δ j-1 + 1 2 δ j+1 if 0 < j < p (where δ x denotes the Dirac measure on x). For each discount rate λ ∈ (0, 1], we consider the value v λ in R I×J of the discounted splitting game induced by the matrix U . Since the assumptions of acyclicity from [START_REF] Laraki | Acyclic Gambling Games[END_REF] are satisfied, Propositions 1, 2, 3 in [START_REF] Laraki | Acyclic Gambling Games[END_REF] show that a limit point of (v λ ) λ , as λ goes to 0, satisfies the conditions of Proposition 1 for V .

2) Now we prove uniqueness. Assume that two matrices V and W satisfy the conditions of Proposition 1. Define α = max (i,j)∈I×J {v i,jw i,j } and Z = argmax (i,j)∈I×J {v i,jw i,j }. Let (i 0 , j 0 ) be an element of Z minimizing the sum of coordinates i + j.

Suppose that v i 0 ,j 0 > u i 0 ,j 0 . Then, v i 0 ,j 0 = 1 2 (v i 0 -1,j 0 + v i 0 +1,j 0 )
, and since w is column-concave,

w i 0 ,j 0 ≥ 1 2 (w i 0 -1,j 0 + w i 0 +1,j 0 ). We obtain α = v i 0 ,j 0 -w i 0 ,j 0 ≤ 1 2 ((v i 0 -1,j 0 -w i 0 -1,j 0 ) + (v i 0 +1,j 0 - w i 0 +1,j 0 )) ≤ 1 2 ((v i 0 -1,j 0 -w i 0 -1,j 0 ) + α).
Hence, (i 0 -1, j 0 ) ∈ Z, which contradicts the minimality of (i 0 , j 0 ). Thus, v i 0 ,j 0 ≤ u i 0 ,j 0 .

Suppose now that w i 0 ,j 0 < u i 0 ,j 0 . Then,

w i 0 ,j 0 = 1 2 (w i 0 ,j 0 -1 + w i 0 ,j 0 +1 ) and since v is row-convex, v i 0 ,j 0 ≤ 1 2 (v i 0 ,j 0 -1 +v i 0 ,j 0 +1 ). We obtain α = v i 0 ,j 0 -w i 0 ,j 0 ≤ 1 2 ((v i 0 ,j 0 -1 -w i 0 ,j 0 -1 )+(v i 0 ,j 0 +1 -w i 0 ,j 0 +1
)), so (i 0 , j 0 -1) ∈ Z which contradicts the minimality of (i 0 , j 0 ). Therefore, w i 0 ,j 0 ≥ u i 0 ,j 0 . We deduce that α = v i 0 ,j 0w i 0 ,j 0 ≤ u i 0 ,j 0u i 0 ,j 0 = 0. Thus v ≤ w and by symmetry v = w.

Consider now the splitting game Γ(U ) with terminal payoffs, defined as follows. Player 1 controls states in I and Player 2 controls states in J. We start at a given initial position (i 1 , j 1 ) in I × J. In each

period t ≥ 1, if Player 1's state is i t he can either stay at i t or, if 0 < i t < m, choose the distribution 1 2 δ it-1 + 1 2 δ it+1 . If i t = 0
or n, this is an absorbing state and Player 1 stays at i t forever. Similarly, if Player 2's state is j t , he can either stay at j t or (if 0 < j t < n) choose the distribution 1 2 δ jt-1 + 1 2 δ jt+1 . States in I × J are perfectly observed by players and choices are simultaneous at every stage. Given any pair of pure strategies, by the martingale property, the sequence of states (i t , j t ) t almost surely converges to a random variable (i ∞ , j ∞ ) and the payoff for Player 1 is defined as the expectation of u(i ∞ , j ∞ ). As in Koessler et al. (2021a), the value of Γ(U ) is V .

Lemma 1. The game Γ(U ) with initial state (i 1 , j 1 ) has a value given by v i 1 ,j 1 , where V = (v i,j ) = MZ(U ). Players have pure optimal stationary strategies.

Proof. Consider the following strategy σ of Player 1: if the current state is (i, j),

stay at i if u i,j ≥ v i,j and induce the distribution 1 2 δ i-1 + 1 2 δ i+1 if v i,j > u i,j .
Considering any strategy τ of Player 2, we show that E(u i∞,j∞ ) ≥ v i 0 ,j 0 , where the expectation is with respect to the distribution of sequences (i t , j t ) t induced by σ and τ .

By definition of V , we have for all t,

E(v i t+1 ,jt |(i t , j t )) = v it,jt , whether u it,jt ≥ v it,jt or not. Moreover E(v i t+1 ,j t+1 |(i t+1 , j t )) ≥ v i t+1 ,jt since V is row-convex. Hence, E(v i t+1 ,j t+1 ) ≥ E(v i t+1 ,jt ) = E(v it,jt ) ≥ v i 1 ,j 1 .
Now, (i t , j t ) t is a.s. eventually constant equal to (i ∞ , j ∞ ), which implies by definition of σ that almost surely u i∞,j∞ ≥ v i∞,i∞ . We obtain:

E(u i∞,j∞ ) ≥ E(v i∞,j∞ ) = E(lim t (v it,jt )) = lim t E(v it,jt ) ≥ v i 1 ,j 1 .
Therefore, σ is a pure strategy of Player 1 which guarantees v i 0 ,j 0 . By symmetry, we obtain Lemma 1.

Remark 1. It is not difficult to show that MZ(U ) is also the uniform value of the game Γ(U ), which implies that we also have MZ(U ) = lim λ→0 v λ , where v λ is the value of the λ-discounted game. In general the models with stage payoffs or payoffs defined on plays are of different nature, but here the trajectories (i t , j t ) t converge (being martingales) and the state spaces are finite, and all the approaches give the same result.

Remark 2. MZ(U ) is in general different from the value of the one-shot splitting game, where both players choose splittings simultaneously and once and for all. For instance, in the game given by

U =    0 1 0 1 0 1 0 1 0    with
initial states in the center, the value of the one-shot game is 1/2 whereas the MZ value is 0.

What are the properties of this Mertens-Zamir transform? It is first clear that U = MZ(U ) if and only if U is row-concave and column-convex. As a consequence, MZ • MZ = MZ. Since increasing the payoffs can only increase the value of a game, it follows from Lemma 1 that the MZ transform is weakly increasing for the partial order on matrices. Another consequence is that adding a constant to the payoffs changes the value by the same constant, i.e. MZ(U + c1) = MZ(U ) + c1 for c ∈ R, with 1 the matrix with all entries equal to 1. This implies that the MZ transform is non expansive with respect to the norm U ∞ = max i,j |u i,j |, with the standard arguments:

U ≤ U + U -U ∞ , so MZ(U ) ≤ MZ(U ) + U -U ∞ . Lemma 2. For all U , U in R I×J we have: 1) if U ≥ U then MZ(U ) ≥ MZ(U ). 2) MZ(U ) -MZ(U ) ∞ ≤ U -U ∞ . 3) vex(cav U ) MZ(U ) cav(vex U ). 4) MZ(U -MZ(U )) = 0.
Proof. We only need to prove 3) and 4). To prove 3), observe that in Γ(U ), Player 1 can guarantee vex U by not moving at all (always remain at i

1 ). So MZ(U ) vex U . So, cav(MZ(U )) cav vex U . Now, cav(MZ(U )) = MZ(U ) since MZ(U ) is column-concave and we obtain MZ(U ) cav(vex U ).
The other inequality follows by duality.

To prove 4), consider the splitting game Γ(U -V ) where V = MZ(U ) and assume that Player 1 plays the strategy σ defined in the proof of Lemma 1: if the current state is (i, j),

stay at i if u i,j ≥ v i,j
and induce the distribution

1 2 δ i-1 + 1 2 δ i+1 if v i,j > u i,j .
Whatever is played by Player 2, we have

u(i ∞ , j ∞ )-v(i ∞ , j ∞ ) ≥ 0 almost surely, so σ guarantees 0 in Γ(U -V ).
Similarly, consider the following strategy τ of Player 2: if the current state is (i, j), stay at j if u i,j ≤ v i,j and induce the distribution

1 2 δ j-1 + 1 2 δ j+1 if v i,j < u i,j .
Whatever is played by Player 1, we have u(i ∞ , j ∞ )v(i ∞ , i ∞ ) ≤ 0 almost surely, so τ guarantees 0 to Player 2 in Γ(U -V ). We conclude that the value of the game Γ(U -MZ(U )) is 0.

Remark 3. The analogs of the properties of Lemma 2 also hold in the continuous setup for v = MZ(u). This is clear for 1), 2), 3). One can also show 4) in the continuous case, as follows. Assume that Player 1 plays the following strategy σ, whose existence is granted by [START_REF] Heuer | Asymptotically optimal strategies in repeated games with incomplete information[END_REF]: if v(p, q) > u(p, q), play a splitting s of p such that v(p, q) = v(s, q) and v(p , q) ≤ u(p , q) for all p ∈ supp(s); if v(p, q) ≤ u(p, q), remain at p. Whatever the strategy τ played by player 2, we have for each stage t: u(p t+1 , q t ) ≥ v(p t+1 , q t ) almost surely. Passing to the limit, u(p ∞ , q ∞ ) ≥ v(p ∞ , q ∞ ), hence player 1 guarantees 0 in the game with payoff uv. Similarly, Player 2 guarantees 0, and MZ(u -MZ(u)) = 0.

Since MZ • MZ = MZ, one can view the Mertens-Zamir transform as a projection on the set of row-concave and column-convex matrices. However, MZ is non-linear and MZ(MZ(U ) -U )) can be different from 0 (for the same reason that for a continuous function f :

[0, 1] → R we always have cav(f -cav f ) = vex(f -vex f ) = 0 but may have cav(cav f -f ) = 0 and vex(vex f -f ) = 0).
How can we compute the MZ transform of a matrix? This is easy in the 1-player case (corresponding to m = 0 or n = 0). For instance:

MZ(    1 0 1   ) = cav(    1 0 1   ) =    1 1 1    and MZ( 0 1 0 ) = vex( 0 1 0 ) = 0 0 0 .
Proposition 1 suggests the following algorithm for computing the MZ transform.

Algorithm 1. Start with a matrix U in R I×J .

• Concavify the columns (u i0 ) i and (u i,n ) i , and convexify the rows (u 0,j ) j and (u mj ) j .

• Choose two disjoint subsets A + , A -of I × J and solve the following linear system:

v ij = 1 2 v i-1,j + 1 2 v i+1,j for (i, j) ∈ A + , v ij = 1 2 v i,j-1 + 1 2 v i,j+1 for (i, j) ∈ A -, v ij = u ij for (i, j) / ∈ A -∪ A + .
• If the solution of the system does not satisfy (v ij > u ij for all (i, j) ∈ A + and v ij < u ij for all (i, j) ∈ A -), or does not satisfy column-concavity and row-convexity, then try another pair of subsets.

• Otherwise, V = MZ(U ) and the algorithm ends.

Notice that the linear system above corresponds to a diagonally dominant matrix, hence has a unique solution in every case. Since there is a unique MZ transform of U , there is a unique pair A + , A -on which the algorithm will eventually stop. A + will be the set of states where v > u, and A - the set of states where v < u. We now illustrate this algorithm with an example.

Example 1.

W =       6 4 2 1 4 2 4 3 1 4 2 5 0 3 4 7      
The first step is the concavification of the first and fourth columns and the convexification of the first and fourth rows. We obtain the following:

W =       6 4 2 1 4 2 4 3 2 4 2 5 0 2 4 7      
Having in mind the splitting game interpretation, it is easy to see that V = MZ(W ) = MZ(W ) and that V coincides with W on the first and fourth columns and on the first and fourth rows. Hence, V can be written as follows: Consider the previously defined optimal strategies in the game Γ(W ): σ for Player 1 (if the current state is (i, j), stay at i if w i,j ≥ v i,j and induce the distribution 1 2 δ i-1 + 1 2 δ i+1 if v i,j > w i,j ) and τ for Player 2 (if the current state is (i, j), stay at j if w i,j ≤ v i,j and induce the distribution 1 2 δ j-1 + 1 2 δ j+1 if v i,j < w i,j ). Starting from an initial point in the interior of the matrix, the induced martingale has the "four frogs" structure [START_REF] Aumann | Bi-Convexity and Bi-Martingales[END_REF][START_REF] Forges | Note on Nash equilibria in repeated games with incomplete information[END_REF]Forges, , 1990)): on each of the four central cells, the martingale hits the boundary with probability 1/2 and continues to another central cell with probability 1/2. The number of steps in which states continue to move is thus unbounded (yet finite almost surely). An important property of Algorithm 1 is that it converges in finite time to the MZ transform. A major drawback is the complexity of the choice of the subsets A + and A -, even if on many examples it is easy to determine the region where V > U and U > V . The inequality cav vex U ≤ MZ(U ) ≤ vex cav U gives useful information (as in the above Example 1 with the matrix W ), or one can guess the optimal strategies by analyzing the splitting game Γ(U ). For instance, starting from the second row and second column of W (corresponding to the coefficient a of MZ(W )), Player 1 can split once between its 2 vertical neighbors and then never move again. Whatever does Player 2, the expected terminal payoff of Player 1 will be at least

V =       6
1 2 4 + 1 2 3 2 > 2 so a > 2.
One can also adapt to matrices the algorithm proposed by [START_REF] Mertens | A duality theorem on a pair of simultaneous functional equations[END_REF] for the continuous setup.

Algorithm 2. [START_REF] Mertens | A duality theorem on a pair of simultaneous functional equations[END_REF] Define inductively two sequences of matrices {U k } k≥0 , {U k } k≥0 by: U 0 = U 0 = U , and for all k ≥ 0, U k+1 = cav vex max(U, U k ), U k+1 = vex cav min(U, U k ).

Then {U k } k≥1 is monotonically increasing, {U k } k≥1 is monotonically decreasing, and both sequences converge to MZ(U ).

For the proof of the above property, one can follow closely the proofs in [START_REF] Mertens | A duality theorem on a pair of simultaneous functional equations[END_REF] and check that they adapt to our discrete setup.

Approximating the continuous MZ transform

We now consider the continuous unidimensional setup where a continuous function u :

[0, 1] 2 → R is given. The Mertens-Zamir transform of u, denoted v = MZ(u), is the continuous solution v : [0, 1] 2 → R
of the pair of functional equations: v(p, q) = cav p min{u(p, q), v(p, q)} = vex q max{u(p, q), v(p, q)}.

Recall that for p in [0, 1], a splitting s of p is a Borel probability on [0, 1] with mean p, i.e. such that p∈[0,1] p ds(p) = p, we extend u to Borel probabilities s and r on [0, 1] by u(s, r) = E s⊗r (u). The function v is also the unique concave (in the first variable), convex (in the second variable) function satisfying for all (p, q) in [0, 1] 2 : (C1) if v(p, q) > u(p, q), there exists a splitting s of p such that v(p, q) = v(s, q) = u(s, q), and (C2) if v(p, q) < u(p, q), there exists a splitting r of q such that v(p, q) = v(p, r) = u(p, r). As in the discrete case, we have:

∀(p, q), cav p vex q u(p, q) ≤ MZ(u)(p, q) ≤ vex q cav p u(p, q).
The MZ transform is in general difficult to compute. The following example is an illustration where we see that the MZ transform of u differs from the value function of the one-shot splitting game, i.e.

the one-shot game where simultaneously Player 1 chooses a splitting s of p, Player 2 chooses a splitting r of q, and the payoff to Player 1 is u(s, r).

Example 2. From [START_REF] Mertens | Incomplete information games with transcendental value[END_REF], see also Mertens et al. 2015 (Example VI.7.4, page 375). Consider the following payoff function, where p = 1p and q = 1q:

u(p, q) = p q 1 2 1 2 1 0 0 1 2p -2q 2q -2p 2p -2q 2q -2p 2q -2p 2p -2q 2p -2q 2q -2p
The MZ transform of u is given by Figure 1. The blue lines represent the set of values (p, q) for which MZ(u)(p, q) = u(p, q) (the equations of these curves in different areas are given in blue); in the red rectangle, we have MZ(u)(p, q) = 1 4 ; black arrows represent increasing linear functions and black lines represent constants.

For this example, the functions cav p vex q u and vex q cav p u are given in Figures 2 and3. This shows that the inequalities can be strict. We now show that the MZ transform is in general different from the

MZ(u)(p, q) = p q 1 2 1 2 1 0 0 1 1 4 u = MZ(u) p ( 1 - p ) = 1 2 q p = q - 1 8 Figure 1: MZ transform of u. vex q cav p u(p, q) = p q 1 0 0 0 0 1 2 1 2 1 0 0 0 0 1 2 1 2 0 0 0 1 2 1 2 1 2 1 0 0 1 Figure 2: cav p vex q u
value of the one-shot splitting game. In the example, the MZ transform at

( 1 2 , 1 2 ) is MZ(u)( 1 2 , 1 2 ) = 1 4
, whereas the value of the one-shot splitting game is 1 2 . In the one-shot game, an optimal strategy for Player 1 is the following splitting: 0 with probability 1 4 , 1 2 with probability 1 2 and 1 with probability 1 4 . It is easy to check that this guarantees an expected payoff of 1 2 to Player 1 (similarly for Player 2).

cav p vex q u(p, q) = p q 1 0 0 0 0 1 2 1 2 1 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0 0 0 1 2 1 2 1 0 0 1 Figure 3: vex q cav p u
We now would like to approximate the MZ transform of u, using MZ transforms of matrices from the previous section. Given n ≥ 1, consider u :

[0, 1] 2 → R biaffine 3 on each square [ i n , i+1 n ] × [ j n , j+1
n ] for i, j = 0, . . . , n -1. Define the matrix U in R I×I with I = {0, . . . , n}, which coincides with u at each point ( i m , j n ) of the grid, and consider its transform MZ(U ). Finally, define the piecewise biaffine extension of MZ(U ) as the function v on [0, 1] 2 which coincides with MZ(U ) at each point of the grid and which is biaffine on each square [ i n , i+1 n ] × [ j n , j+1 n ] for all i, j = 0, . . . , n -1. One could hope that v = MZ(u), however the following example shows it is not the case.

Example 3. Consider U =    0 1 0 1 0 1 0 1 0   , with n = 2 and MZ(U ) =    0 0 0 1 0 1 0 0 0   . Define u : [0, 1] 2 → R which is biaffine on each of the squares [0, 1/2] 2 , [0, 1/2]×[1/2, 1], [1/2, 1]×[0, 1/2]
and [1/2, 1] 2 and such that u( i n , j n ) = u i,j for all i, j = 0, 1, 2. Let v be the piecewise affine extension of MZ(U ), we have v(1/4, 1/2) = 0 since MZ(U ) has only 0 in the second column. However, we claim that MZ(u)(1/4, 1/2) ≥ 1/2, so that v = MZ(u). To prove this claim, observe that u(1/4, q) = 1/2 = vex q u(1/4, q) for all q (we adopt the convention that p is the vertical variable whereas q is the horizontal variable, as in Example 2). So cav p vex q u(1/4, q) ≥ 1/2 for each q and MZ(u)(1/4, q) ≥ cav p vex q u(1/4, q) ≥ 1/2.

The next theorem shows that, despite Example 3, computing the matrix MZ transform for finite sets gives an approximation of the MZ transform of a continuous function u :

[0, 1] × [0, 1] → R. We use d((p, q), (p , q )) = |p -p | + |q -q | on the square [0, 1] 2 .
Theorem 1. Let u : [0, 1] × [0, 1] → R be a continuous function and v = MZ(u). For each n ≥ 1, write I n = {0, . . . , n}, P n = {i/n, i ∈ I n }, and let U n = (U n i,j ) i,j ∈ R In×In be the matrix which coincides with u at each point

( i n , j n ), with i, j in I n . Let V n = (V n i,j ) i,j = MZ(U n ) be the MZ transform of U n and v n : [0, 1] × [0, 1] → R be the piecewise biaffine extension of V n . Then, (v n ) n uniformly converges to MZ(u). Moreover, if u is C-Lipschitz, then for each n ≥ 1, v -v n ∞ ≤ 4C n .
As a consequence, an approximation of MZ(u) is obtained by considering a fine discretization of [0, 1] and computing the MZ transform of the matrix given by the restriction of u to the grid.

Proof. Since u is uniformly continuous, there exists a modulus of continuity ω : R ω(d((p, q), (p , q )).

+ → R + with lim x→0 ω(x) = 0 such that ∀ p, p , q, q ∈ [0, 1], |u(p, q) -u(p , q )| ≤
Moreover, ω can be chosen nondecreasing and concave. [START_REF] Laraki | Acyclic Gambling Games[END_REF] in Lemma A.1 prove that if v = MZ(u), then v also has ω as a modulus of continuity, i.e., ∀ p, p , q, q ∈ [0, 1], |v(p, q)v(p , q )| ≤ ω (d((p, q), (p , q ))).

In particular, if u is C-Lipschitz, ω(x) = Cx and v is also C-Lipschitz. For n ≥ 1, one can see that the matrices U n and V n also have ω as a modulus of continuity, in the following sense: ∀i, i , j, j ∈ I n ,

|U n i,j -U n i ,j | ≤ ω(d((i/n, j/n), (i /n, j /n))) and |V n i,j -V n i ,j | ≤ ω(d((i/n, j/n), (i /n, j /n))).
This implies that v n also has ω as a modulus of continuity.

Fix n ≥ 1 and write P n = {i/n, i ∈ I n }. Consider the splitting game where: Player 1 controls the state p = i/n in P n and at each state p in P n can either stay at p or (if 0 < p < 1) induce the distribution 1 2 δ p-1/n + 1 2 δ p+1/n ; Player 2 controls the state q in [0, 1] and can use any splitting of q at any stage; The terminal payoff is given by the restriction of u to P n × [0, 1]. We define a strategy σ of Player 1 as follows. For states of stage t, (p t , q t ) ∈ P n × [0, 1], let i t and j t in I n be such that a p t =

v n i t n , j t n = 1 2 v n i t -1 n , j t n + 1 2 v n i t + 1 n , j t n .
Similarly,

v n i t n , j t + 1 n = 1 2 v n i t -1 n , j t + 1 n + 1 2 v n i t + 1 n , j t + 1 n .
Since v n is piecewise biaffine,

v n i t n , q t = 1 2 v n i t -1 n , q t + 1 2 v n i t + 1 n , q t ,
and we get:

E[v n (p t+1 , q t )|p t , q t ] = v n (p t , q t ).
This equality obviously holds in case b), so it holds almost surely for every t.

Next, for any given p in P n , the mapping (q → v n (p, q)) is convex. To see this, note that the row-convexity of V n implies that for 0 < j < n,

v n p, j n ≤ 1 2 v n p, j -1 n + v n p, j + 1 n .
Therefore, (q → v n (p, q)) is continuous and piecewise linear with nondecreasing slope, thus it is convex.

As a consequence,

E[v n (p t+1 , q t+1 )] ≥ E[v n (p t+1 , q t )] = E[v n (p t , q t )] ≥ v n (p 1 , q 1 ).
Taking limit gives:

E[v n (p ∞ , q ∞ )] ≥ v n (p 1 , q 1 ).
Now, since P n is finite, for almost all realized sequences {p t , q t } t there exists t 0 such that p t = p ∞ for all t ≥ t 0 . Hence, for t ≥ t 0 the definition of

σ gives v n p ∞ , jt n ≤ u p ∞ , jt n or v n p ∞ , jt+1 k ≤ u p ∞ , jt+1 n .
Introducing now ω the modulus of continuity of u, we have,

u p ∞ , q t ≥ u p ∞ , j t n -ω 1 n and u p ∞ , q t ≥ u p ∞ , j t + 1 n -ω 1 n . Similarly, v n p ∞ , q t ≤ v n p ∞ , jt n + ω 1 n and v n p ∞ , q t ≤ v n p ∞ , jt+1 n + ω 1 n .
We obtain that for all t ≥ t 0 , v n p ∞ , q t ≤ u p ∞ , q t + 2ω 1 n . Taking limit, we have almost surely:

v n p ∞ , q ∞ ≤ u p ∞ , q ∞ + 2ω 1 n . It follows that E[u(p ∞ , q ∞ )] ≥ v n (p 1 , q 1 ) -2ω 1 n .
Therefore by playing σ, Player 1 guarantees the payoff v n p 1 , q 1 -2ω 1 n in the splitting game where he is constrained to stay on the grid P n . Since the value of the unconstrained game can not be lower for Player 1,

∀ (p 1 , q 1 ) ∈ P n × [0, 1], v p 1 , q 1 ≥ v n p 1 , q 1 -2ω 1 n .
Now consider any (p 1 , q 1 ) in [0, 1] 2 . For p 1 in P n such that d(p 1 , p 1 ) ≤ 1 n , we have:

v(p 1 , q 1 ) ≥ v(p 1 , q 1 ) -ω 1 n ≥ v n (p 1 , q 1 ) -3ω 1 n ≥ v n (p 1 , q 1 ) -4ω 1 n .
Exchanging the roles of Players 1 and 2, we obtain v(p 1 , q 1 ) ≤ v n (p 1 , q 1 ) + 4ω( 1 n ), and finally

v -v n ∞ ≤ 4ω 1 n .
Remark 4. The above approach is not limited to uniform grids. Consider any grid P × Q ⊂ [0, 1] 2 , with P = {p 0 , p 1 , . . . , p M -1 , p M }, Q = {q 0 , q 1 , . . . , q N -1 , q N }, p 0 = q 0 = 0 and p 1 = q 1 = 1. Then, given a continuous u : [0, 1] 2 → R, we first define the restriction U P ×Q of u to the grid. It is then easy to adapt the definition of MZ transform to matrices coming from a non uniform grid and obtain a MZ transform V P ×Q ∈ R P ×Q of U P ×Q . One can finally define v P ×Q as the piecewise biaffine extension of V P ×Q . Minor modifications of the above proof can show that

MZ(u) -v P ×Q ∞ ≤ 4ω m(P, Q) ,
where m(P, Q) = max max{|p i+1p i | : i = 0, . . . , M -1}; max{|q j+1q j | : j = 0, . . . , N -1} .

Remark 5. Theorem 1 is of course not the first one to use discretizations of the square to obtain estimates for the difference between the value of a continuous game and the value of a close-by discrete game. This was already used by [START_REF] Ville | Sur la théorie générale des jeux ou intervient l'habileté de joueur[END_REF] to prove existence of the value in mixed strategies for continuous zero-sum games on the square.

Splitting over finite sets with general constraints

In this section we consider splitting games with general constraints on feasible splittings. We consider finite sets of states which are, without loss of generality, subsets of finite dimensional vector spaces.

These finite sets of states are denoted P ⊂ R K for Player 1 and Q ⊂ R L for Player 2, and we are given correspondences S : P ⇒ ∆(P ), R : Q ⇒ ∆(Q) such that for all p ∈ P , S(p) is a set of probability distributions on P with mean p, which contains the Dirac measure δ p on P , and similarly for all q ∈ Q, R(q) is a set of probability distributions on Q with mean q, containing the Dirac measure δ q . That is, players face constraints on admissible states (the sets P, Q) and on feasible splittings they can choose.

(One can think for instance that, in each state, players have access to exogenous sets of statistical experiments to affect posterior beliefs as in Koessler et al. (2021a).) A payoff function u

: P × Q → R
is also given.

The splitting game with general constraints Γ(P, Q, S, R, u) unfolds as before:

• There is a given initial state (p 1 , q 1 ) ∈ P × Q.

• At each stage t ≥ 1, if the current state is (p t , q t ) ∈ P ×Q, Player 1 chooses a splitting s ∈ S(p t ) and Player 2 chooses a splitting r ∈ R(q t ). The next state (p t+1 , q t+1 ) is drawn from the independent product s ⊗ r, and observed by both players before playing stage t + 1.

• Given a strategy profile, the payoff is the expectation of u(p ∞ , q ∞ ) where (p ∞ , q ∞ ) is the almostsure limit of the martingale (p t , q t ) t .

The main result of this section is that Γ(P, Q, S, R, u) has a value which admits a Mertens-Zamir-like characterization. In the following, any map v : P × Q → R is linearly extended to distributions as usual by setting v(s, r) = E s⊗r (v) for s ∈ ∆(P ) and r ∈ ∆(Q).

Definition 3. Consider a map v :

P × Q → R.
1) v is S-concave if: ∀(p, q) ∈ P × Q, ∀s ∈ S(p), v(p, q) ≥ v(s, q). v is R-convex if: ∀(p, q) ∈ P × Q, ∀r ∈ R(q), v(p, q) ≤ v(p, r).

2) For all (p, q) in P × Q, define:

v -(p, q) = sup v(s , q) : s ∈ ∆(P \{p}), ∃ α ∈ [0, 1) s.t. αδ p + (1α)s ∈ S(p) ∈ R ∪ {-∞}, and this inequality is also true for s = δ p . The inequality v(s, q) ≤ v(p, q)ε(1s(p)) then directly extends to all s in co S(p) = F (δ p ). And for each s = δ p in F (δ p ) there exists s ∈ ∆(P ) such that s = s(p)δ p + (1s(p))s , p / ∈ supp(s ) and v(s , q) ≤ v(p, q)ε. Now, assume by induction that for some n ≥ 2, v(s, q) ≤ v(p, q)ε(1s(p)) holds for each s ∈ F n-1 (δ p ) and consider a given s n in F n (δ p ). There exists s 1 in F (δ p ) such that s n ∈ F n-1 (s 1 ).

If s 1 = δ p then v(s n , q) ≤ v(p, q)ε(1s n (p)) by induction, so we now assume that s 1 = δ p . Then s 1 can be written s 1 = s 1 (p)δ p + (1s 1 (p))s 1 , with p / ∈ supp(s 1 ) and v(s 1 , q) ≤ v(p, q)ε. We can write s n = s 1 (p)s n-1 + (1s 1 (p))s n , with s n-1 ∈ S n-1 (δ p ) and s n ∈ S n-1 (s 1 ). From the induction hypothesis, v(s n-1 , q) ≤ v(p, q)ε + εs n-1 (p). S-concavity of v implies v(s n , q) ≤ v(s 1 , q) ≤ v(p, q)ε.

This gives the following:

v(s n , q) ≤ v(p, q)ε + εs 1 (p)s n-1 (p) ≤ v(p, q)ε(1s n (p)).

By induction, we obtain:

∀s ∈ F ∞ (δ p ), v(s, q) ≤ v(p, q)ε(1s(p)).

Finally, assume that v(p, q) > u (p, q). By (C1"), there exists s in F ∞ (δ p ) such that v(p, q) = v(s, q) ≤ u(s, q). We deduce that s = δ p and v(p, q) = v(s, q) ≤ v(p, q)ε(1s(p)), a contradiction. Hence, v -(p, q) = v(p, q), and we have proved that (C1') holds. By symmetry, (C2') also holds.

Lemma 4. The splitting game Γ(P, Q, S, R, u) with initial state (p 1 , q 1 ) has a value which is equal to v(p 1 , q 1 ), and both players have pure ε-optimal strategies.

Proof. We fix ε > 0 and define a strategy σ = (σ t ) t≥1 for Player 1 by a main phase and transitions phases. At each stage t, the strategy depends on the past history of states h t := (p 1 , q 1 , . . . , p t , q t ). The play is initially in the main phase.

• At any stage t ≥ 1 in the main phase, -if u(p t , q t ) ≥ v(p t , q t ), stay at p t (i.e. play σ t = δ pt ) and remain in the main phase at stage t + 1, and -if u(p t , q t ) < v(p t , q t ), according to (C1') there exist s t ∈ S(p t ), s t ∈ ∆(P \{p t }) and α t ∈ [0, 1) such that s t = α t δ pt + (1α t )s t and v(s t , q t ) ≥ v(p t , q t ) -ε 2 t . The strategy enters a transition phase where s t is played at each stage t and at all stages t > t as long as p t = p t+1 = • • • = p t .

After the first stage t > t where p t = p t , σ returns to the main phase at stage t .

Consider any strategy τ of Player 2, and let {p t , q t } t≥1 be the induced martingale and (p ∞ , q ∞ ) be its almost sure limit. Since P and Q are finite, there almost surely exists a stage t 0 such that for each t ≥ t 0 , (p t , q t ) = (p ∞ , q ∞ ). Additionally, since a transition phase starting at (p t , q t ) ends up almost surely at some state p = p t , it must be the case that u(p ∞ , q ∞ ) ≥ v(p ∞ , q ∞ ) almost surely.

Next, we define sequences of stopping times (l i ) i≥1 , (m i ) i≥1 with values in {1, 2, . . . , ∞} as follows:

  We have to compare a, b, c and d to the corresponding entries in W . Let us compute lower and upper bounds for V :We have cav vex W ≤ V ≤ vex cav W , so a > 2, d > 2,b < 3 and c < 4. The entries corresponding to a and d belong to the region where (V > W), and the entries corresponding to b and c belongs to the region (V < U). From Lemma 1, we obtain a = (4 + c)/2, b = (a + 3)/2, c = (2 + d)/2, d = (b + 4)/2. The system has a unique solution given by a = 51/15, b = 48/15, c = 42/15 and d = 54/15. Finally,

Any bounded measurable map v : ∆(K) × ∆(L) → R is linearly extended to Borel probabilities on ∆(K) and ∆(L) by v(s, r) = Es⊗r(v).

In the games we consider, the terminal payoff E(u(p∞, q∞)) is well defined, and all other notions of long-term value (such as limit value, uniform value,. . . ) coincide.

We say that a mapping u defined on a square[p, p ] × [q, q ] ⊂ [0, 1] 2 is biaffine if for all λ, µ in [0, 1], u(λp + (1λ)p , µq + (1 -µ)q ) = λµu(p, q) + λ(1 -µ)u(p, q ) + (1 -λ)µu(p , q) + (1 -λ)(1 -µ)u(p , q ).

supp(.) denotes the support of a probability

Frederic Koessler acknowledges the support of the ANR through the program Investissements d'Avenir (ANR-17-EURE-001) and under grant ANR StratCom (ANR-19-CE26-0010-01). Libération, 78351 Jouy-en-Josas, France; laclauMarie Laclau gratefully acknowledges the support of the ANR through the program Investissements d'Avenir (ANR-11-IDEX-0003/Labex Ecodec/ANR-11-LABX-0047) and under grant ANR CIGNE (ANR-15-CE38-0007-01). Jérôme Renault gratefully acknowledges funding from ANR-3IA Artificial and Natural Intelligence Toulouse Institute, from the ANR under the Investments for the Future program, grant ANR-17-EURE-0010 and from ANR MaSDOL-19-CE23-0017-01. , 78351 Jouy-en-Josas, France; . Tristan Tomala gratefully acknowledges the support of the HEC foundation and ANR/Investissements d'Avenir under grant ANR-11-IDEX-0003/Labex Ecodec/ANR-11-LABX-0047.

1

v + (p, q) = inf v(p, r ) : r ∈ ∆(Q\{q}), ∃ α ∈ [0, 1) s.t. αδ q + (1α)r ∈ R(q) ∈ R ∪ {+∞}.

An alternative way to define v -(p, q) and v + (p, q) is as follows. For each s in S(p)\{δ p }, define s =p as the conditional probability induced by s given that the state is not p (i.e. s =p (p ) = s(p )/(1s(p)) for all p = p). Then v -(p, q) = sup v(s =p , q), s ∈ S(p)\{δ p } and similarly v + (p, q) = inf v(p, r =q ), r ∈ Q(q)\{δ q } . Notice that if v is S-concave and R-convex, then v -(p, q) ≤ v(p, q) ≤ v + (p, q). If

Example 4. Take P = 0, 1 n , 2 n , . . . , 1 and S(•) such that Player 1 at state p ∈ 1 n , . . . , n-1 n can either stay at p or split between the two closest neighbors p -1 n and p

Theorem 2. The splitting game Γ(P, Q, S, R, u) admits a value, which is the unique function v :

and such that for all (p, q) in P × Q, q), and

Moreover, the value is obtained in pure strategies: players have pure ε-optimal strategies for all ε > 0.

As shown by Example 4, this theorem generalizes both Proposition 1 and Lemma 1 (for the existence of value). Existence results for splitting games with constraints are found in [START_REF] Laraki | Acyclic Gambling Games[END_REF] and Koessler et al. (2021a), where further assumptions on the correspondences S, R are required (continuity, compactness, convexity, sometimes closedness under iteration). Theorem 2 relaxes the assumptions of compactness, convexity and the assumption that feasible splittings are closed under iteration. In the proof, we introduce correspondences F : ∆(P ) ⇒ ∆(P ) and G : ∆(Q) ⇒ ∆(Q) that are the "closures" of S, R defined by taking the closed convex hulls of the feasible splittings, and extended to distributions on P and Q. The first part of the proof (Lemma 3) shows that the MZ function associated with F and G satisfies (C1') and (C2'). The second part (Lemma 4) shows that each player can guarantee the value up to any ε > 0. Since feasible splittings are not closed under iteration, achieving a desired splitting may require several stages. As a result, the ε-optimal strategies we construct are not Markovian.

Notice also that 0-optimal strategies may fail to exist, as shown in the following simple example

where Player 2 plays no role.

Example 5.

In other words, at all states but 1 2 , Player 1 cannot split the state. At 1 2 , Player 1 can split, but the state is likely to remain at 1 2 and is much more likely to be 1 4 or 3 4 than 0 or 1. Suppose that for each q in Q, u(0, q) = u(1/2, q) = u(1, q) = 0 and u(1/4, q) = u(3/4, q) = 1, so that at p = 1/2, Player 1 would like to induce the distribution 1 2 δ 1 4

is infeasible at 1 2 but can be approximately achieved with many stages by choosing a very small ε. Example 6. This example shows that the assumption that δ p ∈ S(p) is necessary for Theorem 2. Let P = {0, 1/2, 1}, with S(0) = δ 0 , S(1) = {δ 1 } and S(1/2) = {1/2δ 0 + 1/2δ 1 }, that is at p = 1/2, Player 1 has to move to 0 and 1 with equal probability, but cannot stay at 1/2. Let Q = {0}, so that Player 2 has no role here, and assume that u(0, 0) = u(1, 0) = 0 and u(1/2, 0) = 1. Then the value function is v = 0 for each initial state. We have

Proof of Theorem 2. The proof is split into two lemmas.

Lemma 3. There exists v : P × Q → R that is S-concave, R-convex and such that (C1') and (C2') are satisfied for all (p, q) in P × Q.

Proof. We define a correspondence F from ∆(P ) to ∆(P ) which represents the mixed extension of S. Formally, let F : ∆(P ) ⇒ ∆(P ) be as follows, Next, define the iterates of F as follows: F 0 (s) = {s}, and for all n ≥ 1, F n+1 (s) = {s ∈ F n (s ) : s ∈ F (s)}. Finally, let F ∞ (s) be the closure of ∪ ∞ n=0 F n (s). Since F (δ p ) only contains splittings of p, the transition defined by F is strongly acyclic: any strictly concave function ϕ : R K → R, such as (p → -k∈K p 2 k ) satisfies : ∀p ∈ P , Argmax s∈F ∞ (δp) ϕ(s) = {δ p }. And we define similarly multivalued transitions for Player 2, G and

Theorem 1 of [START_REF] Laraki | Acyclic Gambling Games[END_REF] applies and there exists a unique function v : P × Q → R that is S-concave, R-convex and such that for every (p, q) in P × Q, (C1") If v(p, q) > u(p, q), there exists s in F ∞ (δ p ) such that v(p, q) = v(s, q) ≤ u(s, q), and

We now prove that this function v satisfies (C1'). Fix (p, q), we have v

-Let l 1 be the first stage t ≥ 1 where u(p t , q t ) < v(p t , q t ), i.e. where Player 1 is in the main phase and enters the first transition phase, and let m 1 ≥ l 1 be the last stage of the first transition phase.

-For i ≥ 2, let l i > m i-1 be the stage entering the i-th transition phase, and m i ≥ l i be the last stage of the i-th transition phase.

Fix i ≥ 1. We have u(p l i , q l i ) < v(p l i , q l i ) and at all stages t = l i , . . . , m i , Player 1 plays s l i = α l i δ p l i + (1α l i )s l i , with s l i ∈ ∆(P \{p l i }), α l i ∈ [0, 1) and v(s l i , q l i ) ≥ v(p l i , q l i ) -ε 2 l i . At stages t = m i + 1, . . . , l i+1 , the play is in the main phase and p l i+1 = p 1+m i . We have the following:

where the first inequality uses the R-convexity of v. As a consequence,

and thus

Player 1 guarantees the payoff v(p 1 , q 1 ) up to any ε > 0. By symmetry, this is also true for Player 2, and v(p 1 , q 1 ) is the value of the game.

As the value is unique, there exists a unique v satisfying the properties of Lemma 3, and the proof of Theorem 2 is complete.

Remark 6. The proof shows that if a function w is S-concave, R-convex and satisfies (C1 ), then for any ε > 0 Player 1 can guarantee wε with a pure strategy.

Concluding Questions

1. How can we compare Algorithm 1 and Algorithm 2? Regarding Algorithm 2, can we a priori bound the number of steps k 0 , defined such that for each entry (i, j) and all k ≥ k 0 , the sign of U i,j -U ki,j remains the same?

2. Theorem 1 is restricted to binary states, i.e., the unidimensional case. Extending the result to greater dimensions is left as an open problem. The main difficulty is that there are several directions of splitting for Player 1 when v > u so it is difficult to define a good strategy for him (similarly for Player 2 when v < u).

3. Consider a general splitting game as in section 4, but remove the assumption that players can always remain in every state. Theorem 2 is no longer valid as Example 6 shows, but does the game still have a value?