Rida Laraki
email: rida.laraki@lamsade.dauphine.fr.

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

Jérôme Renault Acyclic Gambling

Acyclic Gambling Games

est destinée au dépôt

Introduction

The model of zero-sum stochastic games was introduced by Shapley [START_REF] Shapley | Stochastic Dames[END_REF] in 1953. A state variable ω ∈ Ω follows a controlled Markov chain with transitions Q(ω|i, j, ω) controlled by the actions of two competing players (i ∈ I for player 1 and j ∈ J for player 2). Shapley assumed the action and state spaces (I, J and Ω) to be finite and proved the existence of the value v λ of the λ-discounted game using a dynamic programming principle, and characterized v λ as the unique fixed point of what has been called the Shapley operator [START_REF] Rosenberg | An Operator Approach to Zero-Sum Repeated Games[END_REF][START_REF] Sorin | A First Course on Zero-Sum Repeated Games[END_REF].

Bewley and Kohlberg [START_REF] Bewley | The Asymptotic Theory of Stochastic Games[END_REF], using algebraic tools, proved the existence of the asymptotic value v = lim λ→0 v λ . Actually, when action and state spaces are finite, the equations that define v λ may be described by finitely many polynomial inequalities, implying that v λ is semi-algebraic and so is converging. The extension of this result to infinite stochastic games is a central question in mathematical game theory [START_REF] Laraki | Advances in Zero-Sum Dynamic Games. Chapter 2 in Handbook of Game Theory IV[END_REF][START_REF] Mertens | Repeated Games[END_REF][START_REF]Stochastic Games and Applications[END_REF][START_REF] Sorin | A First Course on Zero-Sum Repeated Games[END_REF].

Recently, several important conjectures [START_REF] Mertens | Repeated Games[END_REF][START_REF] Mertens | Repeated Games[END_REF] were proved to be false. Vigeral [START_REF] Vigeral | A Zero-Sum Stochastic Game with Compact Action Sets and no Asymptotic Value[END_REF] and Ziliotto [START_REF] Ziliotto | Zero-Sum Repeated Games: Counterexamples to the Existence of the Asymptotic Value and the Conjecture maxmin = limv(n)[END_REF] provided examples where the family {v λ } diverges as λ approaches zero. In Vigeral, the state space Ω is finite and the action sets I and J are semi-algebraic. In Ziliotto, the set of actions is finite but the state space Ω is compact, and can be seen as the space of common beliefs on a finite state variable, controlled but not observed by the players.

On the other hand, there are many classes of stochastic games with general state space and action sets where {v λ } converges (for a recent survey, see [START_REF] Laraki | Advances in Zero-Sum Dynamic Games. Chapter 2 in Handbook of Game Theory IV[END_REF]). Many have in common some irreversibility in the transitions. In recursive games [START_REF] Everett | Recursive Games. Contributions to the Theory of Games[END_REF][START_REF] Sorin | Existence of the Limit Value of Two Person Zeo-Sum Discounted Repeated Games via Comparison Theorems[END_REF] the current payoff is zero until the game is absorbed. In absorbing games [START_REF] Kohlberg | Repeated Games with Absorbing States[END_REF][START_REF] Mertens | Absorbing Games with Compact Action Spaces[END_REF][START_REF] Rosenberg | An Operator Approach to Zero-Sum Repeated Games[END_REF] there is only one non-absorbing state. In repeated games with incomplete information [START_REF] Aumann | Repeated Games with Incomplete Information[END_REF][START_REF] Mertens | The Value of Two-Person Zero-Sum Repeated Games with Lack of Information on Both Sides[END_REF][START_REF] Rosenberg | An Operator Approach to Zero-Sum Repeated Games[END_REF], once a player reveals some information, he cannot withdraw it. Similarly in splitting games [START_REF] Laraki | Variational Inequalities, Systems of Functional Equations and Incomplete Information Repeated Games[END_REF][START_REF] Laraki | The Splitting Game and Applications[END_REF][START_REF] Sorin | A First Course on Zero-Sum Repeated Games[END_REF] the state follows a martingale which eventually converges. Interestingly, in all those classes of "irreversible" stochastic games, not only we have convergence but also an explicit characterization of the asymptotic value. This leads many to anticipate that irreversibility has to do with convergence.

Our paper provides a weak and a strong definition of irreversibility (we call acyclicity) and prove that they constitute the frontier between convergence and divergence of {v λ }: strong acyclicity guarantee convergence while the closely related weak acyclicity do not. To do so, we restrict ourself to a new class which embeds any product stochastic game [START_REF] Flesch | Stochastic Games on a Product State Space[END_REF] and naturally extends gambling houses.

A classical gambling house problem [START_REF] Dubins | Inequalities for Stochastic Processes[END_REF][START_REF] Maitra | Discrete Gambling and Stochastic Games[END_REF] has three ingredients : a metric state space S, a Borel-measurable utility function u : S → IR, and a gambling house Φ, where Φ is a set value function that assigns to each s ∈ S a set Φ(s) of ∆(S) (set of Borel probability distributions over S). At each stage t, given the state s t , the decision maker gets the reward u(s t ), chooses p t ∈ Φ(s t ), and the state moves to s t+1 according to the probability distribution p t .

The gambling house is leavable if for every s ∈ S, δ s (the dirac mass at s) belongs to Φ(s). It is well known that any MDP can be mapped to a gambling house and any positive MDP to a leavable gambling house [START_REF] Dubins | Invariant Gambling Problems and Markov Decision Processes[END_REF][START_REF] Maitra | Discrete Gambling and Stochastic Games[END_REF][START_REF] Schal | On Stochastic Dynamic Programming: A Bridge Between Markov Decision Processes and Gambling[END_REF]. In this paper, we consider only leavable gambling houses.

In a gambling game, each player controls his gambling house: Γ : X → ∆(X) for Player 1 and Λ : Y → ∆(Y ) for Player 2, and the utility function is now u : X × Y → IR with the convention that player 1 wants to maximize u whereas player 2 wants to minimize u. At each stage t, both players knowing the state ω t = (x t , y t ), simultaneously Player 1 chooses p t in Γ(x t ) and Player 2 chooses q t ∈ Λ(y t ), the stage payoff is u(x t , y t ) and a new state (x t+1 , y t+1 ) is selected according to the probability distribution p t ⊗ q t . As any MDP can be mapped into a gambling house, a product stochastic game [START_REF] Flesch | Stochastic Games on a Product State Space[END_REF] can be mapped into a gambling game.

For each λ ∈ (0, 1], one can define the λ-discounted game where the stream of payoffs is evaluated according to t=1 λ(1 -λ) t-1 u(x t , y t ). Usually λ is called the discount rate, 1 -λ = 1 1+r is called the discount factor and r is the interest rate. Under classical regularity assumptions, the λ-discounted game has a value v λ and the family {v λ } is equi-continuous.

Our first main result shows that if at least one of the gambling houses Γ or Λ is strongly acyclic, {v λ } uniformly converges to a function v as λ goes to 0. Moreover, we provide several characterizations of the asymptotic value v that extend the well known Mertens-Zamir system of functional equations [START_REF] Mertens | The Value of Two-Person Zero-Sum Repeated Games with Lack of Information on Both Sides[END_REF]. Our second result proves that under a slightly weaker notion of acyclicity, {v λ } may diverge (even if both houses Γ and Λ are weakly acyclic and both state spaces X and Y are finite). Our example is inspired by an example in Ziliotto [START_REF] Ziliotto | Zero-Sum Repeated Games: Counterexamples to the Existence of the Asymptotic Value and the Conjecture maxmin = limv(n)[END_REF] for stochastic games where both players control the same state variable. It is the first in the class of product stochastic games, and appears simpler than the existing counterexamples of divergence with finite state space. Finally, under an idempotent assumption combined with a bounded variation hypothesis on the transitions, we prove existence of the uniform value, extending a recent result by Oliu-Barton [START_REF] Barton | The Splitting Game: Uniform Value and Optimal Strategies[END_REF] on splitting games.

Gambling Games

Notations

Given a compact metric space S, we denote by B(S), resp. by C(S), the set of bounded measurable, resp. continuous, functions from S to the reals, and by ∆(S) the set of Borel probabilities over S. For s in S, we denote by δ s ∈ ∆(S) the Dirac measure on s, and whenever possible we assimilate s and δ s . For v in B(S), we denote by ṽ its affine extension to ∆(S): ṽ(p) = IE p (v) for all p in ∆(S), where IE p (v) is the expectation of v with respect to p. ∆(S) is endowed with the weak-* topology, a compatible distance being the Kantorovich-Rubinstein (or Wasserstein of order 1) metric:

d KR (p, p ′ ) = sup v∈E 1 |ṽ(p) -ṽ(p ′ )|
, where E 1 is the set of 1-Lipschitz functions on S. When there is no confusion, ṽ(p) will also be denoted by v(p).

Model

A gambling game is a zero-sum stochastic game where each player controls his own state variable. We will always assume in this paper that the state spaces are non empty metric and compact, and denote by X and Y the respective set of states1 controlled by Player 1 and by Player 2. The transitions of Player 1 are given by a continuous2 multifunction Γ : X ⇉ ∆(X) with non empty convex3 compact values: if the state of Player 1 is at x, he can select his new state according to any probability in Γ(x). Similarly, a continuous multifunction Λ : Y ⇉ ∆(Y ) with non empty convex compact values, gives the transitions of Player 2. The players independently control their own state, and only interact through payoffs: the running payoff of Player 1 is given by a continuous mapping u : X ×Y -→ IR, and the payoff to Player 2 is given by -u.

Gambling games extend the model of gambling houses [START_REF] Dubins | Inequalities for Stochastic Processes[END_REF], which correspond to the single player case when Y is a singleton and Player 2 plays no role. One can show, by an adequate increase of the state space in order to encompass actions, that any MDP can be mapped into a gambling house [START_REF] Dubins | Invariant Gambling Problems and Markov Decision Processes[END_REF][START_REF] Maitra | Discrete Gambling and Stochastic Games[END_REF][START_REF] Schal | On Stochastic Dynamic Programming: A Bridge Between Markov Decision Processes and Gambling[END_REF].

A standard gambling house is the red-and-black casino where X = [0, 1] is a fortune space. Suppose that at each fortune x ≥ 0, the gambler can stake any amount s in her possession. The gambler loses the stake with probability 1 -w where w ∈ (0, 1) is fixed and given, and wins back the stake and an additional equal amount with probability w. The corresponding transition multiifunction reads:

Φ w (x) = {wδ min{x+s,1} + (1 -w)δ x-s : 0 ≤ s ≤ x}.
Another class of gambling house are splitting problems where X = ∆(K) is a simplex (K is a finite set) and Γ(x) is the set of Borel probabilities on X centered at x. The idea of splitting was introduced by Aumann and Maschler [START_REF] Aumann | Repeated Games with Incomplete Information[END_REF] in the context of repeated games with incomplete information on one side. This is now very popular in economics (persuasion and information design literature [START_REF] Kamenica | Bayesian Persuasion[END_REF]).

The above examples of gambling houses naturally extend to gambling games. One can consider a casino game where each player i controls a red-and-black house with parameter w i , and the running payoff depends on the current pair of fortunes. Another example is a splitting game [START_REF] Laraki | Variational Inequalities, Systems of Functional Equations and Incomplete Information Repeated Games[END_REF][START_REF] Laraki | The Splitting Game and Applications[END_REF][START_REF] Sorin | A First Course on Zero-Sum Repeated Games[END_REF] where X = ∆(K) and Y = ∆(L) are simplexes, Γ(x) is the set of Borel probability measures on X that are centered at x and Λ(y) is the set of probability measures of Borel probability measures on Y that are centered at y.

Discounted Evaluations

Given a discount factor λ ∈ (0, 1] and an initial state (x 1 , y 1 ) in X × Y , the game G λ (x 1 , y 1 ) is played as follows: at any stage t ≥ 1, the payoff to Player 1 is u(x t , y t ) and both players knowing (x t , y t ), simultaneously Player 1 chooses p t+1 in Γ(x t ) and Player 2 chooses q t+1 in Λ(y t ). Then, x t+1 and y t+1 are independently selected according to p t and q t , the new states x t+1 and y t+1 are publicly announced, and the play goes to stage t + 1. Under our assumptions of compact state spaces, continuous transitions with convex compact values and continuous running payoff, it is easy to describe the value of such dynamic game.

Definition 2.1. v λ is the unique element of C(X × Y ) s.t. ∀(x, y) ∈ X × Y, v λ (x, y) = max p∈Γ(x) min q∈Λ(y) (λu(x, y) + (1 -λ)ṽ λ (p, q)) , = min q∈Λ(y) max p∈Γ(x) (λu(x, y) + (1 -λ)ṽ λ (p, q)) .
This is the standard characterization of the value of a discounted game by means of the Shapley operator. Existence and uniqueness of v λ follow from standard fixed-point arguments (see for instance [START_REF] Mertens | Repeated Games[END_REF][START_REF] Rosenberg | An Operator Approach to Zero-Sum Repeated Games[END_REF]). We refer to v λ (x, y) as the value of the game G λ (x, y).

The goal of the paper is to study the convergence of (v λ ) λ when λ goes to 0, i.e. when players become more and more patient.

Remark 2.2. Cesaro Evaluations. It is also standard to define the value of the n-stage games by: v 1 = u, and for n ≥ 1 and (x, y) ∈ X × Y :

v n+1 (x, y) = 1 n + 1 max p∈Γ(x) min q∈Λ (y)
(u(x, y) + nṽ n (p, q)) ,

= 1 n + 1 min q∈Λ(y) max p∈Γ(x)
(u(x, y) + nṽ n (p, q)) .

It is known that the uniform convergence of (v n ) n when n goes to infinity, is equivalent to the uniform convergence of (v λ ) λ when λ goes to 0, and in case of convergence both limits are the same (Theorem 2.2 in [START_REF] Ziliotto | A Tauberian Theorem for Nonexpansive Operators and Applications to Zero-Sum Stochastic Games[END_REF] applies here)

Non expansive transitions

Without further assumptions, convergence of (v λ ) may fail even in the simple case where Γ and Λ are single-valued ("0 player case", players have no choice), so we will assume throughout the paper that the gambling game is non expansive, i.e. have non expansive transitions:

Definition 2.3. The game has non expansive transitions if:

∀x ∈ X, ∀x ′ ∈ X, ∀p ∈ Γ(x), ∃p ′ ∈ Γ(x ′ ), s.t. d KR (p, p ′ ) ≤ d(x, x ′ ),
and similarly : ∀y ∈ Y, ∀y ′ ∈ Y, ∀q ∈ Λ(y), ∃q ′ ∈ Λ(y ′ ), s.t. d KR (q, q ′ ) ≤ d(y, y ′ ).

The gambling game has non expansive transitions if the transitions, viewed as mappings from X to 2 ∆(X) , and from Y to 2 ∆(Y ) , are 1-Lipschitz for the Hausdorff distance on compact subsets of ∆(X) and ∆(Y ). Note that the transitions are always non expansive when X and Y are finite 4 . Moreover splitting games are non expansive [START_REF] Laraki | Variational Inequalities, Systems of Functional Equations and Incomplete Information Repeated Games[END_REF], and red-and-black casino houses with parameter w are non-expansive if and only if w ≤ 1 2 [START_REF] Laraki | The Preservation of Continuity and Lipschitz Continuity by Optimal Rewards Operators[END_REF]. Let us mention also Markov chain repeated games with incomplete information [START_REF] Gensbittel | The value of Markov chain games with lack of information on both sides[END_REF], where each player observes a private and exogenous Markov chain. These repeated games lead to gambling houses with transitions of the form: X is a simplex ∆(K), and Γ(x) = {pM, p ∈ ∆(X) centered at x} with M a fixed stochastic matrix. Here again, transitions are non expansive.

Let us mention immediately an important consequence of the non expansive assumption. The proof is in the Appendix.

Proposition 2.4. Assume the gambling game is non-expansive. Then the family {v λ } λ∈(0,1] is equicontinuous.

This proposition extends to two players a similar result in [START_REF] Laraki | The Preservation of Continuity and Lipschitz Continuity by Optimal Rewards Operators[END_REF] on gambling houses where it is proved that non-expansivity is necessary and sufficient to guarantee equi-continuity of the values. As a consequence, pointwise and uniform convergence of {v λ } are equivalent, and since X × Y is compact, to prove this convergence it is enough to prove uniqueness of a limit point5 .

Remark 2.5. It is not difficult to see that without non-expansivity, {v λ } may not be equicontinuous and the convergence may not be uniform. For instance in red-and-black casino with a single player, if the parameter w > 1 2 and u(x) = x, v λ is continuous for every λ but v = lim λ →0 v λ is not : v(x) = 0 for x = 0 and v(x) = 1 for x > 0.

Excessive, depressive and balanced functions

Definition 2.6. Let v be in B(X × Y ). 1) v is balanced if ∀(x, y) ∈ X × Y , v(x, y) = max p∈Γ(x) min q∈Γ(y) ṽ(p, q) = min q∈Γ(y) max p∈Γ(x) ṽ(p, q). 2) v is excessive (with respect to X) if: ∀(x, y) ∈ X×Y , v(x, y) = max p∈Γ(x) ṽ(p, y). 3) v is depressive (with respect to Y ) if: ∀(x, y) ∈ X×Y , v(x, y) = min q∈Γ(y) ṽ(x, q).
Observe that any uniform limit v of (v λ ) λ∈(0,1] is necessarily continuous and balanced (by passing to the limit in definition 2.1). In a splitting game, excessive means concave with respect to the first variable, and depressive means convex with respect to the second variable.

Example 2.7. Consider a gambling game where players 1 and 2 move on the same finite grid of a circle containing 6 nodes in equidistant positions. Any player can move one step to the left, one step to the right, or not move (and choose randomly between these 3 options, so that transitions have convex values). It is here possible for a player to go from any state to any other state in at most 3 stages (the game may be called cyclic), so any excessive and depressive function is necessarily constant. Suppose that Player 1's payoff is 1 if he is at most one step away from Player 2, and Player 1's payoff is 0 otherwise. If the players start a distance at most 1, Player 1 can guarantee this property will hold forever by not moving or moving one step to the direction of Player 2 and so, in this case we have v λ = 1 for every λ. On the other hand, if the players start at a distance at least 2, Player 2 can insure that this property will hold forever, by not moving or moving one step in the opposite direction of Player 1. For these initial states, v λ = 0 for every λ. Here, v = lim v λ is continuous and balanced, but not excessive nor depressive.

Acyclicity

We now come to the main definitions of the paper. Definition 2.8.

1) The gambling game is leavable if: ∀x ∈ X, δ x ∈ Γ(x) and ∀y ∈ Y, δ y ∈ Λ(y).

2) The gambling house Γ of player 1 is weakly acyclic if there exists ϕ in B(X) lower semi-continuous such that:

∀x ∈ X, Argmax p∈Γ(x) φ(p) = {δ x }.
Similarly, the gambling house Λ of player 2 is weakly acyclic if there exists ψ in B(Y ) upper semi-continuous such that:

∀y ∈ Y, Argmin q∈Λ(y) ψ(q) = {δ y }.
The gambling game is weakly acyclic if both gambling houses are weakly acyclic.

The gambling game is leavable if each player can remain in any given state. This is a standard assumption [START_REF] Dubins | Inequalities for Stochastic Processes[END_REF]. This is the case in red-and-black casinos and splitting games. In persuasion games and in repeated games with incomplete information, not moving means revealing no information. If the game is leavable, any excessive and depressive function is necessarily balanced. The converse is not necessarily true as example 2.7 shows.

Weak acyclicity is, to our knowledge, a new condition in the gambling house literature. If the house Γ is weakly acyclic, the "potential" ϕ decreases in expectation along non stationary trajectories, hence the irreversibility of the process (in the space of probabilities over X).

Observe that any weakly acyclic gambling game is necessarily leavable. When w ≤ 1 2 , a red-and-black casino is weakly acyclic (take ϕ to be strictly increasing and strictly concave). Also, a splitting game is weakly acyclic (take ϕ to be any strictly concave function on X).

We will now define strong acyclicity, our central condition. For this, we need to consider transitions for several stages. We first extend linearly the transitions to ∆(X) and ∆(Y ) by defining Γ : ∆(X) ⇉ ∆(X) and Λ : ∆(Y ) ⇉ ∆(Y ). More precisely, the graph of Γ is defined as the closure of the convex hull of the graph of Γ (viewed as the subset {(δ x , p), x ∈ X, p ∈ Γ(x)} of ∆(X)×∆(X)), and similarly the graph of Λ is defined as the closed convex hull of the graph of Λ. Because Dirac measures are extreme points of ∆(X) and ∆(Y ), we have Γ(δ x ) = Γ(x) and Λ(δ y ) = Λ(y) for each x in X and y in Y . Be careful that in general, for p in ∆(X) and

q in ∆(Y ): ṽλ (p, q) = max p ′ ∈ Γ(p) min q ′ ∈ Λ(q) (λu(p, q) + (1 -λ)ṽ λ (p ′ , q ′ )) .
We now define inductively a sequence of transitions ( Γn ) n from ∆(X) to ∆(X), by Γ0 (p) = {p} for every state p in ∆(X), and6 for each n ≥ 0, Γn+1 = Γn • Γ . Γn (δ x ) represents the set of probabilities over states that Player 1 can reach in n stages from the initial state x in X. Similarly we define Λn for each n. Definition 2.9.

1) The reachable set of Player 1 from state x in X is the closure of n≥0 Γn (δ x ) in ∆(X), and denoted Γ ∞ (x). Similarly, the reachable set of Player 2 from state y in Y is the subset Λ ∞ (y) of ∆(Y ) defined as the closure of n≥0

Λn (δ y ).

2) The gambling house Γ of player 1 is strongly acyclic (or simply, acyclic) if there exists ϕ in B(X) lower semi-continuous such that:

∀x ∈ X, Argmax p∈Γ ∞ (x) φ(p) = {δ x }.
Similarly, the gambling house Λ of player 2 is strongly acyclic (or simply, acyclic) if there exists ψ in in B(Y ) upper semi-continuous such that:

∀y ∈ Y, Argmin q∈Λ ∞ (y) ψ(q) = {δ y }.
The gambling game is strongly acyclic (or simply, acyclic) if both gambling houses are strongly acyclic.

Clearly, strong acyclicity implies weak acyclicity. Note that in splitting games, we have Γ • Γ = Γ, so Γ ∞ = Γ and weak and strong acyclicity coincide.

Main Results

In all the paper (and in particular the results below), we consider standard gambling games. Definition 3.1. A gambling game is standard if both state spaces X and Y are compact metric, the running payoff u is continuous, and the transitions Γ and Λ have non empty convex compact values and are leavable and non expansive.

We will also use the following properties. Definition 3.2. Given v in B(X × Y ), we say that :

v satisfies P 1 if: ∀(x, y) ∈ X × Y, ∃p ∈ Γ ∞ (x), v(x, y) = ṽ(p, y) ≤ u(p, y), v satisfies P 2 if : ∀(x, y) ∈ X × Y, ∃q ∈ Λ ∞ (y), v(x, y) = ṽ(x, q) ≥ u(x, q).
Our main result is the following.

Theorem 3.3. Consider a standard gambling game.

1. If at least one of the players has a strongly acyclic gambling house, (v λ ) uniformly converges to the unique function v in C(X × Y ) satisfying:

a) v is excessive , i.e. ∀(x, y) ∈ X × Y , v(x, y) = max p∈Γ(x) ṽ(p, y), b) v is depressive, i.e. ∀(x, y) ∈ X × Y , v(x, y) = min q∈Γ(y) ṽ(x, q), c) v satisfies P 1, i.e. ∀(x, y) ∈ X × Y, ∃p ∈ Γ ∞ (x), v(x, y) = ṽ(p, y) ≤ u(p, y), d) v satisfy P 2, i.e. ∀(x, y) ∈ X × Y, ∃q ∈ Λ ∞ (y), v(x, y) = ṽ(x, q) ≥ u(x, q).
Moreover: v is the largest excessive-depressive continuous function satisfying P 1, and is the smallest excessive-depressive continuous function satisfying P 2.

2. If both gambling houses are weakly acyclic, convergence of (v λ ) may fail.

The conditions of the positive result 1) may be interpreted as follows:

• a) and b) : It is always safe not to move. For each player, not moving ensures not to degrade the limit value.

• c) and d) : Each player can reach, if his opponent does not move, the zone when the current payoff is at least as good than the limit value, without degrading the limit value.

These interpretations will lead later to the construction of simple uniformly optimal strategies in some gambling games, see section 7.3.

The positive result of theorem 3.3 relies on the following three propositions. Recall that thanks to proposition 2.4, to get convergence of the values it is enough to show uniqueness of a limit point of (v λ ) λ . Proposition 3.4. Assume one of the player has a weakly acyclic gambling house. If v in C(X × Y ) is balanced, then v is excessive and depressive. Proposition 3.5. Let v be a limit point of (v λ ) for the uniform convergence. Then v is balanced, and satisfies P 1 and P 2. Proposition 3.6. Assume one of the player has a strongly acyclic gambling house. Then, any balanced continuous function satisfying P 1 is smaller that any balanced continuous function satisfying P 2. Consequently, there is at most one balanced continuous function satisfying P 1 and P 2.

If none of the player has a strongly acyclic gambling house, there may be infinitely many balanced continuous functions satisfying P1 and P2. This will be the case in our counter-example of section 6, where both gambling houses are weakly acyclic.

Examples 4.1 A simple acyclic gambling house

Let us first illustrate our characterization on a simple example. Consider the following Markov decision process with 3 states: X = {a, b, c} from [START_REF] Sorin | A First Course on Zero-Sum Repeated Games[END_REF]. States b and c are absorbing with respective payoffs 1 and 0. Start at a, choose α ∈ I = [0, 1/2], and move to b with proba α and to c with proba α 2 .

"! # a 0 "! # b 1* "! # c 0* © ' α 1 -α -α 2 α 2
Here formally Y is a singleton (there is only one player, so we can omit the variable y),

Γ(b) = {δ b }, Γ(c) = {δ c }, and Γ(a) = conv{(1 -α -α 2 )δ a + αδ b + α 2 δ c , α ∈ I}. The payoffs are u(a) = u(c) = 0, u(b) = 1.
Γ has compact convex values, the transitions are 1-Lipschitz, and the game is leavable. The gambling game is strongly acyclic: just consider ϕ such that ϕ(a) = 1, and ϕ(b) = ϕ(c) = 0.

Player 1 can go from state a to state b in infinitely many stages with arbitrarily high probability, by repeating a choice of α > 0 small (so that α 2 is much smaller than α), and the limit value v clearly satisfies:

v(a) = v(b) = 1, v(c) = 0.

A weakly acyclic gambling house

Let us modify the gambling house of the previous section 4.1. We still have a unique player and a state space X = {a, b, c}. The only difference is that state b is no longer absorbing : in state b the player also has to choose some α ∈ I = [0, 1/2], and then moves to a with probability α, to c with probability α 2 and remains in b with probability 1 -α -α 2 .

"! # a "! # b "! # c © ' α 1 -α -α 2 α 2 α 1 -α -α 2 E α 2
States a and b are now symmetric. This gambling house is weakly acyclic, with ϕ(a) = ϕ(b) = 1, ϕ(c) = 0, but it is not strongly acyclic since a ∈ Γ ∞ (b) and b ∈ Γ ∞ (a). We will later use this gambling house to construct our counterexample of theorem 3.3, 2).

An example with countable state spaces

We present here a (strongly) acyclic gambling game with countable state spaces, and illustrate7 the proof of proposition 3.4, that under weak acyclicity any continuous balanced function is also excessive and depressive. Consider the state space:

X = {1 - 1 n , n ∈ IN * } ∪ {1} = {x 1 , ..., x n , ...., x ∞ },
where

x n = 1 -1 n if n is finite, and x ∞ = 1. We use d(x, x ′ ) = |x -x ′ |
, so that X is countable and compact. The transition is given by:

Γ(x n ) = {αδ xn + (1 -α)δ x n+1 , α ∈ [0, 1]}, and Γ(x ∞ ) = {δ x∞ }.
The intuition is clear: Player 1 can stay at his location, or move 1 to the right. The gambling house (Y, Λ) of Player 2 is a copy of the gambling house of Player 1. Transitions are non expansive (since

| 1 n+1 -1 n ′ +1 | ≤ | 1 n -1 n ′ |)
, and the game is strongly acyclic. The payoff u is any continuous function X × Y -→ IR, so that theorem 3.3 applies.

Consider v : X × Y -→ IR, and for simplicity we use w(n, m) = v(x n , x m ). Here v excessive means that w(n, m) is weakly decreasing in n, and v depressive means that w(n, m) is weakly increasing in m. The meaning of v balanced is the following: for each n and m, w(n, m) is the value of the matrix game ("local game" at (n, m)):

w(n + 1, m) w(n + 1, m + 1)
w(n, m) w(n, m + 1) .

Clearly, if v is excessive and depressive it is balanced, but proposition 3.4 tells that if v is continuous, then the converse also holds: balancedness implies excessiveness and depressiveness. The idea of the proof of proposition 3.4 can be seen here as follows.

Suppose v is balanced, but not excessive. Then one can find n and m such that w(n + 1, m) > w(n, m). Because w(n, m) is the value of the local game at (n, m), we necessarily have w(n+1, m+1) ≤ w(n, m), and w(n+1, m) > w(n+1, m+1). Consider now the "local game" at (n+1, m). w(n+1, m) is the value of the matrix:

w(n + 2, m) w(n + 2, m + 1) w(n + 1, m) w(n + 1, m + 1)
.

Since w(n + 1, m) > w(n + 1, m + 1), we obtain w(n + 2, m + 1) ≥ w(n + 1, m).

We have obtained:

w(n + 2, m + 1) ≥ w(n + 1, m) > w(n, m) ≥ w(n + 1, m + 1), so w(n + 2, m + 1) -w(n + 1, m + 1) > w(n + 1, m) -w(n, m).
Iterating the argument, we obtain that for each p,

w(n + p + 1, m + p) ≥ w(n + 1, m) -w(n, m) > 0.
And this is a contradiction with w being continuous at infinity. To conclude with this example, consider the simple case where the running payoff is given by u(x, y) = |x -y|. Player 1 wants to be far from Player 2, and Player 2 wants to be close to Player 1. If initially n < m, it is optimal for each player not to move, so w(n, m) = |x n -x m |. Suppose on the contrary that initially n ≥ m, so that Player 1 is more to the right than Player 2. Then Player 2 has a simple optimal strategy which is to move to the right if the current positions satisfy x > y, and to stay at y if x = y. No matter how large is the initial difference n -m, Player 2 will succeed in being close to player, so that w(n, m) = 0 if n ≥ m.

5 Proof of Theorem 3.3, part 1.

We prove here propositions 3.4, 3.5 and 3.6.

Proof of proposition 3.4

By symmetry, suppose that Γ is weakly acyclic and Λ Leavable. Let us prove that any balanced continuous function v is excessive-depressive. First let us first prove that v is excessive.

Fix any (x 0 , y 0 ) in X × Y , and p 1 ∈ Γ(x 0 ). A direct consequence of balancedness is the existence of q 1 in Λ(y 0 ) such that v(p 1 , q 1 ) ≤ v(x 0 , y 0 ). Now, p 1 is in ∆(X) and q 1 is in ∆(Y ). One has to be careful that there may not exist p 2 ∈ Γ(p 1 ) such that for all q 2 ∈ Λ(q 1 ), v(p 2 , q 2 ) ≥ v(p 1 , q 1 ). This is because, ṽ being affine in each variable, v(p 1 , q 1 ) can be interpreted as the value of the auxiliary game where first x and y are chosen according to p 1 ⊗ q 1 and observed by the players, then players respectively choose p ∈ Γ(x) and q ∈ Λ(y) and finally Player 1's payoff is v(p, q). And to play well in this game Player 1 has to know the realization of q 1 before choosing p. However since y 0 is a Dirac measure, balancedness implies that there exists p 2 ∈ Γ(p 1 ) such that v(p 2 , q 1 ) ≥ v(p 1 , y 0 ). We have obtained the following lemma: Lemma 5.1. Given (x 0 , y 0 ) in X × Y , and p 1 ∈ Γ(x 0 ), there exists q 1 in Λ(y 0 ) and p 2 ∈ Γ(p 1 ) such that: v(p 1 , q 1 ) ≤ v(x 0 , y 0 ) and v(p 2 , q 1 ) ≥ v(p 1 , y 0 ). We now prove the proposition. Define, for x in X, h(x) = Max{v(p, y) -v(x, y), y ∈ Y, p ∈ Γ(x)}. h is continuous. We put Z = Argmax x∈X h(x), and consider x 0 ∈ Argmin x∈Z ϕ(x), where ϕ comes from the definition of Γ weakly acyclic.

x 0 ∈ Z, so v is excessive if and only if h 0 = def h(x 0 ) ≤ 0. By definition of h(x 0 ), there exists p 1 ∈ Γ(x 0 ) and y 0 in Y such that v(p 1 , y 0 ) -v(x 0 , y 0 ) = h 0 .

By lemma 5.1, there exists q 1 in Λ(y 0 ) and p 2 ∈ Γ(p 1 ) such that v(p 1 , q 1 ) ≤ v(x 0 , y 0 ) and v(p 2 , q 1 ) ≥ v(p 1 , y 0 ). Consequently,

v(p 2 , q 1 ) -v(p 1 , q 1 ) ≥ v(p 1 , y 0 ) -v(x 0 , y 0 ) = h 0 .
One can now find y 1 in Y such that v(p 2 , y 1 )-v(p 1 , y 1 ) ≥ h 0 , and since p 2 ∈ Γ(p 1 ) it implies that Supp(p 1 ) ⊂ Z. But p 1 ∈ Γ(x 0 ), so by definition of x 0 and weak acyclicity, we obtain that p 1 = δ x 0 . So h 0 = 0, and v is excessive.

Let us now prove that when v is balanced and excessive then it is depressive. For every (x, y), and every p ∈ Γ(x), we have v(x, y) ≥ v(p, y). Thus, for every (x, y), p ∈ Γ(x) and every q ∈ Λ(y), v(x, q) ≥ v(p, q) and consequently, min q∈Λ(y) v(x, q) ≥ min q∈Λ(y) v(p, q). Taking the maximum in p ∈ Γ(x) and using that v is balanced implies that min q∈Λ(y) v(x, q) ≥ v(x, y). Since Λ is leavable, we have equality and so v is depressive with respect to Y .

Proof of proposition 3.5

Let (λ n ) n be a vanishing sequence of discount factors such that v λn -v → n→∞ 0. Fix (x, y) in X ×Y , by symmetry it is enough to show that there exists p ∈ Γ ∞ (x) such that v(x, y) ≤ v(p, y) ≤ u(p, y). If v(x, y) ≤ u(x, y), it is enough to consider p = δ x , so we assume v(x, y) > u(x, y). For n large enough, v λn (x, y) > u(x, y) + λ n .

Fix n. We define inductively a sequence (p n t ) t=0,...,Tn in ∆(X), with T n ≥ 1, by: 1) p n 0 = δ x , 2) for each t ≥ 0 such that v λn (p n t , y) > u(p n t , y) + λ n , we define p n t+1 in Γ(p n t ) by:

p n t+1 ∈ Argmax p∈ Γ(p n t ) (λ n u(p n t , y) + (1 -λ n )v λn (p, y)) . We have max p∈ Γ(p n t ) (λ n u(p n t , y) + (1 -λ n )v λn (p, y)) ≥ v λn (p n t , y
), so:

λ n u(p n t , y) + (1 -λ n )v λn (p n t+1 , y) ≥ v λn (p n t , y). (1)
Since u(p n t , y) < v λn (p n t , y) -λ n , we obtain:

v λn (p n t+1 , y) ≥ v λn (p n t , y) + λ 2 n 1 -λ n > v λn (p n t , y). (2)
Since λ 2 n 1-λn > 0 and v λn is bounded, there exists a first integer t = T n where v λn (p n Tn , y) ≤ u(p n Tn , y) + λ n , and we stop here the definition of the sequence (p n t ) t=0,...,Tn . Inequalities (1) and (2) above give:

v λn (x, y) ≤ v λn (p n Tn-1 , y) ≤ λ n u(p n Tn-1 , y) + (1 -λ n )v λn (p n Tn , y). (3)
Define now p n = p n Tn for each n. p n ∈ ΓTn (x) ⊂ Γ ∞ (x) for each n, and we consider a limit point p * ∈ Γ ∞ (x) of (p n ) n . Because v λn is an equicontinuous family converging to v, we obtain the convergence (along a subsequence) of v λn (p n Tn , y) to v(p * , y). Passing to the limit in the inequality defining T n then gives:

v(p * , y) ≤ u(p * , y).
Finally, passing to the limit in (3) shows: v(x, y) ≤ v(p * , y).

Proof of proposition 3.6

We start with a lemma. Lemma 5.2. Assume v in C(X × Y ) is excessive. Then for all (x 0 , y 0 ) in X × Y and all p ∈ Γ ∞ (x 0 ), we have: v(p, y 0 ) ≤ v(x 0 , y 0 ).

Proof: p = lim n p n , with p n ∈ Γn (x 0 ) for each n. It is enough to prove that v(p n , y 0 ) ≤ v(x 0 , y 0 ) for each n, and we do the proof by induction on n. The case n = 1 is clear by definition of v excessive. Since p n+1 ∈ Γ(p n ), it is enough to prove that for p ′ in ∆(X) and p ′′ ∈ Γ(p ′ ), we have v(p ′′ , y 0 ) ≤ v(p ′ , y 0 ). By definition of Γ, (p ′ , p ′′ ) is in the closure of conv(GraphΓ). y 0 is fixed, and the function h : p -→ v(p, y 0 ) is affine continous on ∆(X). The set

D = def {(p ′ , p ′′ ) ∈ ∆(X) × ∆(X), h(p ′′ ) ≤ h(p ′ )}.
is convex and compact, and we want to show that Graph( Γ) = conv(GraphΓ) ⊂ D. It it enough to prove that Graph(Γ) ⊂ D, and this is implied by the fact that v is excessive. This concludes the proof of lemma 5.2.

We now prove the proposition. Assume one of the gambling houses is strongly acyclic, and let v 1 and v 2 satisfying the conditions of proposition 3.6 (are continuous, balanced, v 1 satisfies P 1 and v 2 satisfies P 2). We will show that v 1 ≤ v 2 .

By symmetry, suppose that Γ is strongly acyclic. From Proposition 3.4, v 1 and v 2 are excessive (in X) and depressive (in Y ). v 1 -v 2 being continuous on X × Y , define the compact set:

Z = Argmax (x,y)∈X×Y v 1 (x, y) -v 2 (x, y).
Consider now ϕ u.s.c. given by the strong acyclicity condition of Γ. The set Z being compact, there exists (x 0 , y 0 ) minimizing ϕ(x) for (x, y) in Z.

By v 2 satisfying P 2, there exists q in Λ ∞ (y 0 ) such that v 2 (x 0 , y 0 ) = v 2 (x 0 , q) ≥ u(x 0 , q). Thus, there is y ′ 0 ∈ Supp(q) such that v 2 (x 0 , y ′ 0 ) ≥ u(x 0 , y ′ 0 ). Because v 1 is depressive, by lemma 5.2 we have v 1 (x 0 , q) ≥ v 1 (x 0 , y 0 ) and we obtain v 1 (x 0 , q) -v 2 (x 0 , q) ≥ v 1 (x 0 , y 0 ) -v 2 (x 0 , y 0 ). Since (x 0 , y 0 ) is in Z, {x 0 } × Supp(q) ⊂ Z. Thus, (x 0 , y ′ 0 ) ∈ Z. Obviously, (x 0 , y ′ 0 ) also minimizes ϕ(x) for (x, y) in Z (the minimum value remains unchanged: ϕ(x 0 )).

By v 1 satisfying P 1, there exists p in Γ ∞ (x 0 ) such that:

v 1 (x 0 , y ′ 0 ) = v 1 (p, y ′ 0 ) ≤ u(p, y ′ 0 ). Because v 2 is excessive, by lemma 5.2 we have v 2 (p, y ′ 0 ) ≤ v 2 (x 0 , y ′ 0 ) and we obtain v 1 (p, y ′ 0 ) -v 2 (p, y ′ 0 ) ≥ v 1 (x 0 , y ′ 0 ) -v 2 (x 0 , y ′ 0 ). Since (x 0 , y ′ 0 ) is in Z, Supp(p) × {y ′ 0 } ⊂ Z.
By definition of (x 0 , y ′ 0 ), this implies: ϕ(p) ≥ ϕ(x 0 ). The definition of ϕ now gives that p is the Dirac measure on x 0 . We obtain that v 1 (x 0 , y ′

0 ) = v 1 (p, y ′ 0 ) ≤ u(x 0 , y ′ 0 ). So Max (x,y)∈X×Y v 1 (x, y) -v 2 (x, y) = v 1 (x 0 , y ′ 0 ) -v 2 (x 0 , y ′ 0 ) ≤ u(x 0 , y ′ 0 ) -u(x 0 , y ′ 0 ) = 0, and thus v 1 ≤ v 2 .

A weakly acyclic game without limit value

We conclude here the proof of theorem 3.3 by providing a counterexample to the convergence of (v λ ) in a weakly acyclic non expansive gambling house.

The counter-example

The states and transitions for Player 1 are as in example 4.2:

"! # a "! # b "! # c © ' α a 1 -α a -α 2 a α 2 a α b 1 -α b -α 2 b E α 2 b
The set of states of Player 1 is X = {a, b, c}. The difference with example 4.2 is that the set of possible choices for α a and α b may be smaller than [0, 1/2].

Here α a and α b now belong to some fixed compact set I ⊂ [0, 1/2] such8 that 0 is in the closure of I\{0}. Then 0 ∈ I, the transitions are leavable and non expansive. States a and b are symmetric, this gambling house is weakly acyclic, with ϕ(a

) = ϕ(b) = 1, ϕ(c) = 0, but not strongly acyclic since a ∈ Γ ∞ (b) and b ∈ Γ ∞ (a).
The gambling house of Player 2 is a copy of the gambling house of Player 1, with state space Y = {a ′ , b ′ , c ′ } and a compact set of choices J ⊂ [0, 1/2] such that 0 is in the closure of J\{0}. The unique difference between the gambling houses of the players is that I and J may be different. Payoffs are simple:

u(x, y) = 0 if x = y, u(x, y) = 1 if x = y.
The u function can be written as follows

a ′ b ′ c ′ a 0 1 1 b 1 0 1 c 1 1 0
, with a clear interpretation : Player 1 and Player 2 both move on a space with 3 points, Player 2 wants to be at the same location as Player 1, and Player 1 wants the opposite.

Here the gambling game is weakly acyclic but not strongly acyclic, and the following lemma shows that the uniqueness property of proposition 3.6 fails. Lemma 6.1. Let v : X × Y -→ IR. Then A) and B) are equivalent:

A) v is excessive, depressive, and satisfies P 1 and P 2, B) There exists x ∈ [0, 1] such that v can be written:

a ′ b ′ c ′ a x x 1 b x x 1 c 0 0 0 Proof: Assume v satisfies A).
Since u takes values in [0, 1], so does also v. Because c and c ′ are absorbing, we have v(c, c ′ ) = u(c, c ′ ) = 0.

Consider now v(c, a ′ ). v being depressive, for any fixed β * > 0 in J we have: Consider now v(a, a ′ ). v being excessive, for any α > 0 in I we have:

v(c, a ′ ) ≤ β * v(c, b ′ ) + β * 2 v(c, c ′ ) + (1 -β * -β * 2 )v(c, a ′ ).
v(a, a ′ ) ≥ αv(b, a ′ ) + α 2 v(c, a ′ ) + (1 -α -α 2 )v(a, a ′ ).
Hence v(a, a ′ ) ≥ 1 1+α v(b, a ′ ), and by assumption on I we obtain v(a, a ′ ) ≥ v(b, a ′ ). By symmetry of the transitions between a and b, v(a, a

′ ) = v(b, a ′ ). Similarly, v(a, b ′ ) = v(b, b ′ ).
It only remains to prove that v(a, a ′ ) = v(a, b ′ ). v being depressive, for any

β > 0 in J, v(a, a ′ ) ≤ βv(a, b ′ ) + β 2 v(a, c ′ ) + (1 -β -β 2 )v(a, a ′ ).
By assumption on J, we get v(a, a ′ ) ≤ v(a, b ′ ). By symmetry of the transitions between b and b ′ , v(a, b ′ ) = v(a, a ′ ), and v satisfies B).

One can easily check that B) implies A), and the proof of lemma 6.1 is complete.

The second part of theorem 3.3 is a direct consequence of the following result. Theorem 6.2.

1) If I = J = [0, 1/4], the limit value exists and is:

a ′ b ′ c ′ a 1/2 1/2 1 b 1/2 1/2 1 c 0 0 0
2) If J = [0, 1/4] and I = {0, 1/4}, the limit value exists and is:

a ′ b ′ c ′ a 0 0 1 b 0 0 1 c 0 0 0 3) If J = [0, 1/4] and I = { 1 4 n , n ∈ IN * } ∪ {0}, then v λ diverges.
6.2 Proof of theorem 6.2

We start with considerations valid for the 3 cases of the theorem. We fix J = [0, 1/4] in all the proof, and only assume for the moment that I is a compact subset of [0, 1/4] containing 0 and 1/4. Consider λ ∈ (0, 1). It is clear that v λ (c, c ′ ) = 0, and v λ (a, c ′ ) = v λ (b, c ′ ) = 1. By symmetry of the payoffs and transitions, we have

v λ (a, a ′ ) = v λ (b, b ′ ), v λ (b, a ′ ) = v λ (a, b ′ ) and v λ (c, c ′ ) = v λ (c, b ′
), so we can write v λ as:

a ′ b ′ c ′ a x λ y λ 1 b y λ x λ 1 c z λ z λ 0
with x λ , y λ and z λ in (0, 1).

z λ is indeed easy to compute. If the game is at (c, a ′ ), Player 1 can not move, and Player 2 wants to reach c ′ as fast as possible, so he will choose β = 1/4 and we have (see definition 2.8): z λ = λ1 + (1 -λ)( 116 0 + 15 16 z λ ), so that:

z λ = 16λ 1 + 15λ ≤ 16λ. ( 4
)
Proposition 6.3. Assume J = [0, 1/4], min I = 0 and max I = 1/4. Then for λ small enough,

z λ < x λ < y λ , (5)
λ x λ = (1 -λ) max α∈I α(y λ -x λ ) + α 2 (z λ -x λ ) , (6)
λ y λ = λ + (1 -λ) min β∈J β(x λ -y λ ) + β 2 (1 -y λ ) . (7)
(6) express the fact that at (a, a ′ ) or (b, b ′ ), it is optimal for Player 2 to play the pure strategy β = 0 (stay at the same location and wait until Player 1 has moved), and Player 1 can play a pure strategy α there. Similarly, (7) express the fact that at (a, b ′ ) or (b, a ′ ), it is optimal for Player 1 not to move. In spite of these simple intuitions, the proof of the proposition is rather technical, and relegated to the appendix.

Taking for granted proposition 6.3, we now proceed to the proof of theorem 6.2. It is simple to study the simple maximization problem of Player 2 given by [START_REF] Dubins | Invariant Gambling Problems and Markov Decision Processes[END_REF], which is simply minimizing a concave polynomial on the interval

J = [0, 1/4]. If y λ -x λ ≤ 1 2 (1 -y λ ), the minimum in (7) is achieved for β = y λ -x λ 2(1-y λ )
, and otherwise it is achieved for β = 1 4 . Hence for λ small enough:

If y λ -x λ ≤ 1 2 (1 -y λ ), 4λ(1 -y λ ) 2 = (1 -λ)(y λ -x λ ) 2 . (8)
If

y λ -x λ ≥ 1 2 (1 -y λ ), (1 -y λ )(1 + 15λ) = 4(1 -λ)(y λ -x λ ). (9)
Notice that the 2 inequalities of ( 9) imply 1 + 15λ ≥ 2(1 -λ), which is is not possible for λ small. Consequently, for small discount factors the right hand side of (8) holds, and we have proved, for λ small enough, the main equality of the proof:

4λ(1 -y λ ) 2 = (1 -λ)(y λ -x λ ) 2 . ( 10
)
This clearly implies:

y λ -x λ -→ λ→0 0.
For each λ > 0, denote by α λ ∈ I a maximizer in the expression [START_REF] Dubins | Inequalities for Stochastic Processes[END_REF], so that

λx λ = (1 -λ)α λ (y λ -x λ ) + (1 -λ)α 2 λ (z λ -x λ ). (11)
And since x λ > 0, α λ > 0.

The following lemma implies part 2) of theorem 6.2.

Lemma 6.4. If 0 is an isolated point in I, then y λ and x λ converge to 0.

Proof: In this case there exists α * > 0 such that α λ ≥ α * for all λ. Passing to the limit in [START_REF] Gensbittel | The value of Markov chain games with lack of information on both sides[END_REF] gives the result.

We will now prove parts 1) and 3) of the theorem. The fact that I ⊂ J gives an advantage to Player 2, which can be quantified as follows. Lemma 6.5. Assume that y λn and

x λn converge to v in [0, 1]. Then v ≤ 1/2, and y λn -x λn ∼ 2 √ λ n (1 -v). Proof: (1 -λ)(y λ -x λ ) = 2 √ λ √ 1 -λ(1 -y λ ), so x λ (λ + α 2 λ ) = λx λ α 2 λ + (1 -λ)α 2 λ z λ + 2α λ √ λ √ 1 -λ(1 -y λ ) ≥ 2α λ √ λx λ , since λ + α 2 λ -2α λ √ λ ≥ 0.
Dividing par α λ √ λ and passing to the limit gives 2(1 -v) ≥ 2v, so v ≤ 1/2, and the lemma is proved.

Consider again the concave optimization problem of Player 1 given by equation [START_REF] Dubins | Inequalities for Stochastic Processes[END_REF], and denote by α * (λ) = y λ -x λ 2(x λ -z λ ) > 0 the argmax of the unconstrained problem if Player 1 could choose any α ≥ 0. If y λ and x λ converge to v > 0, then α * (λ) ∼ √ λ 1-v v , and Player 1 would like to play in the λ-discounted game at (a, a ′ ) some α close to √ λ 1-v v . Lemma 6.6. Let λ n be a vanishing sequence of discount factors such that √ λ n ∈ I for each n. Then y λn and x λn converge to 1/2.

Proof: By considering a converging subsequence we can assume that y λn and x λn converge to some v in [0, 1]. By the previous lemma, v ≤ 1/2, and we have to show that v ≥ 1/2. We have for each λ in the subsequence, since Player 1 can choose to play α = √ λ:

λx λ ≥ (1 -λ) √ λ(y λ -x λ ) + (1 -λ)λ(z λ -x λ ), so x λ (2 -λ) ≥ (1 -λ)z λ + (1 -λ) y λ -x λ √ λ .
By passing to the limit, we get 2v ≥ 2(1 -v), and v ≥ 1/2. Lemma 6.7. Let λ n be a vanishing sequence of discount factors such that for each n, the open interval

( 1 2 √ λ n , 2 √ λ n ) does not intersect I.
Then lim sup n y λn ≤ 4/9.

Proof: Suppose that (up to a subsequence) x λn and y λn converges to some v ≥ 4/9. It is enough to show that v = 4/9. We know that v ≤ 1/2 by lemma 6.5, and since

α * (λ) ∼ √ λ 1-v v we have 1 2 √ λ ≤ α * (λ) ≥ 2 √ λ for λ small in the sequence. By assumption ( 1 2 √ λ, 2 √
λ) contains no point in I and the objective function of Player 1 is increasing from 0 to α * (λ) and decreasing after α * (λ). There are 2 possible cases:

If

α λ ≤ 1 2 √
λ we have:

λx λ ≤ 1 2 (1 -λ) √ λ(y λ -x λ ) + 1 4 (1 -λ)λ(z λ -x λ ).
Dividing by λ and passing to the limit gives:

v ≤ 1 -v -1 4 v, i.e. v ≤ 4 9 . Otherwise, α λ > 2
√ λ and we have:

λx λ ≤ 2(1 -λ) √ λ(y λ -x λ ) + 4(1 -λ)λ(z λ -x λ ).
Again, dividing by λ and passing to the limit gives:

v ≤ 4(1 -v) -4v, i.e. v ≤ 4 9 .
Finally, lemma 6.6 proves part 1) of theorem 6.2, whereas lemmas 6.6 and 6.7 together imply part 3), concluding the proof of theorem 6.2. Remarks 6.8.

• In case 3) of theorem 6.2, it is possible to show, using lemma (6.7), that lim inf x λ = lim inf y λ = 4/9, and lim sup x λ = lim sup y λ = 1/2.

• It is not difficult to adapt lemma (6.7) to show the divergence of (v λ ) as soon as J = [0, 1/4] and I satisfies: a) there exists a sequence (λ n ) converging to 0 such that √ λ n ∈ I for each n, and b) there exist η > 0 and a sequence (λ n ) converging to 0 such that for each n, I does not intersect the interval [

√ λ n (1 -η), √ λ n (1 + η)]. • It is important for the counterexample that I = { 1 2 2n , n ∈ IN * } ∪ {0}
is not semi-algebraic. Indeed, it has been showed that if we assume X and Y finite, and the transitions Γ, Λ and the payoff u to be definable in some o-minimal structure, then (v λ ) λ converges [START_REF] Bolte | Definable Zero-Sum Stochastic Games[END_REF].

Equivalent characterizations

Definition 7.4. Given g in B(X × Y ), Exc Γ (g) is the smallest excessive (w.r.t. X) function not lower than g, and Dep Λ (g) is the largest depressive (w.r.t. Y ) function not greater than g. Exc Γ is usually called the réduite operator and Dep Λ (g) = -Exc Γ (-g). In splitting games, Exc Γ = Cav X is the concavification operator on X and Dep Λ (g) = V ex Y is the convexification operator on Y . We introduce the following definition by analogy with the Mertens-Zamir characterization.

MZ1 : ∀(x, y) ∈ X × Y, v(x, y) = Exc Γ min(u, v)(x, y), and MZ2 : ∀(x, y) ∈ X × Y, v(x, y) = Dep Λ max(u, v)(x, y).
We now introduce other properties, by analogy with the one established for splitting games and repeated games with incomplete information, see for instance [START_REF] Laraki | Variational Inequalities, Systems of Functional Equations and Incomplete Information Repeated Games[END_REF][START_REF] Laraki | The Splitting Game and Applications[END_REF][START_REF] Rosenberg | An Operator Approach to Zero-Sum Repeated Games[END_REF].

Definition 7.6. Let v be in B(X × Y ). 1) For each (x, y) in X × Y , x is extreme for v(•, y) if arg max p∈Γ ∞ (x) v(p, y) = {δ x }. y is extreme for v(x, •) if arg min q∈Λ ∞ (y) v(x, q) = {δ y }.
2) v satisfies the E-characterization if:

E1 : f or all (x, y) ∈ X × Y, if x is extreme for v (•, y) then v(x, y) ≤ u(x, y), and E2 : f or all (x, y) ∈ X × Y, if y is extreme for v (x , •) then v(x, y) ≥ u(x, y). Proposition 7.7. Consider a standard gambling game and let v in C(X × Y ) be excessive and depressive. Then: v satisfies MZ1 =⇒ v satisfies P 1 =⇒ v satisfies E1, and v satisfies MZ2 =⇒ v satisfies P 2 =⇒ v satisfies E2.

Proof. Let v be a continuous excessive function that satisfies MZ1. Fix y and define for each x, f (x) = min(v(x, y), u(x, y)). Then, for every x, v(x, y) = Exc Γ (f )(x). We consider the gambling house for Player 1 where the state of Player 2 is fixed to y and the payoff is given by f . From corollary 7.3, there is

p ∈ Γ ∞ (x) such that v(x, y) = v(p, y) ≤ f (p). Since f (p) ≤ u(p, y), v satisfies P 1.
Now, let v be an excessive continuous function that satisfies P 1. Take any x and y and suppose that x is extreme for v(•, y). By P 1, there is p * ∈ Γ ∞ (x) such that v(x, y) = v(p * , y) ≤ u(p * , y). Because v is excessive and continuous, by lemma 5.2 we have p * ∈ arg max p∈Γ ∞ v(p, y). Because x is extreme for v(•, y), p * = δ x and so, v(x, y) ≤ u(x, y). Consequently, E1 is satisfied.

By symmetry, MZ2 =⇒ P 2 =⇒ E2.

Remark 7.8. It is easy to find examples where E1 is satisfied but MZ1 is not. For instance, assume that Y is a singleton, and that Γ(x) = ∆(X) for each x in X. Consider the constant, hence excessive, functions u = 0 and v = 1. v has no extreme points hence satisfies E1, but Exc Γ min(u, v) = u and v does not satisfy MZ1.

Proposition 7.9. Consider a standard gambling game and let v be an excessivedepressive function in C(X × Y ). Then: (Γ strongly acyclic) and (v satisfies E1) =⇒ (v satisfies MZ1), and;

(Λ strongly acyclic) and (v satisfies E2) =⇒ (v satisfies MZ2).

Consequently, if the gambling game is strongly acyclic, characterizations MZ, P and E are equivalents.

Proof. Let v be excessive-depressive that satisfies E1. Fix y ∈ Y . We want to show that v(x, y) = g(x, y) where g = Exc Γ (f ) and f = min(u, v). g is continuous by corollary 7.3. Since v is excessive and v ≥ f , we have v ≥ g. Let Z = arg max x∈X v(x, y) -g(x, y) and let x 0 = arg min x∈Z ϕ(x), where ϕ comes form the definition of acyclicity. It is enough to prove that v(x 0 , y) ≤ g(x 0 , y).

Suppose not. We have g(x 0 , y) ≥ f (x 0 , y), so (1) g(x 0 , y) ≥ u(x 0 , y). Now, let p 0 ∈ Γ ∞ (x 0 ) such that v(x 0 , y) = v(p 0 , y). Because g is excessive and continuous, g(p 0 , y) ≤ g(x 0 , y) (lemma 5.2). Consequently, v(p 0 , y) -g(p 0 , y) ≥ v(x 0 , y)-g(x 0 , y). Consequently, p 0 is supported on Z. Thus, ϕ(x 0 , y) ≤ ϕ(p 0 , y), and by strong acyclicity p 0 = δ x 0 . Thus x 0 is an extreme point of v(•, y). By E 1 , we have (2) v(x 0 , y) ≤ u(x 0 , y). By ( 1) and (2), v(x 0 , y) -g(x 0 , y) ≤ 0. A contradiction. In that case, clearly Γ = Γ ∞ and Λ = Λ ∞ . Any state that could be reached in several stages can be reached immediately in a single stage. This holds true for instance in splitting games. Notice also that for any Γ, the multifunction Γ ∞ is idempotent. If Γ • Γ = Γ , then Γ(x) = Γn (δ x ) = Γ ∞ (x) for all n and x so if the gambling game is idempotent the notions of weak and strong acyclicity coincide.

Uniform optimal strategies in idempotent games

An immediate corollary of theorem 3.3 is the following.

Corollary 7.11. Consider a standard idempotent gambling game where a player has an acyclic gambling house. Then {v λ } converges uniformly to the unique function v in C(X × Y ) which is excessive, depressive and satisfies:

Q1 : ∀(x, y) ∈ X × Y, ∃p ∈ Γ(x), v(x, y) = v(p, y) ≤ u(p, y), Q2 : ∀(x, y) ∈ X × Y, ∃q ∈ Λ(y), v(x, y) = v(x, q) ≥ u(x, q).

Uniform value and optimal strategies

In repeated and stochastic games, a stronger notion of limit value is given by the uniform value. As usual, a strategy of Player 1, resp. Player 2, is a measurable rule giving at every stage t, as a function of past and current states, an element in Γ(x t ), resp. of Λ(y t ), where x t and y t are the states of stage t. A pair (x 1 , y 1 ) of initial states and a pair of strategies (σ, τ ) naturally define a probability on the set of plays (X × Y ) ∞ (with the product σ-algebra, X and Y being endowed with their Borel σ-algebra), which expectation is written IE (x 1 ,y 1 ),σ,τ .

Definition 7.12. w ∈ B(X × Y ) is the uniform value of the gambling game and both players have optimal uniform strategies if: There exists a strategy σ of Player 1 that uniformly guarantees w: for any ε > 0, there is N such that for any any n ≥ N and initial states (x 1 , y 1 ), for any strategy τ of Player 2, IE (x 1 ,y 1 ),σ,τ 1 n n t=1 u(x t , y t ) ≥ w(x 1 , y 1 ) -ε. And similarly, there exists a strategy τ of Player 2 that uniformly guarantees w: for any ε > 0, there is N such that for any n ≥ N and initial states (x 1 , y 1 ), for any strategy σ of Player 1, IE (x 1 ,y 1 ),σ,τ 1 n n t=1 u(x t , y t ) ≤ w(x 1 , y 1 ) + ε. It is known [START_REF] Sorin | A First Course on Zero-Sum Repeated Games[END_REF] that the above conditions imply similar inequalities for discounted payoffs: for Player 1, the same strategy σ is such that for any ε > 0, there is λ 0 > 0 satisfying: for any λ ≤ λ 0 , (x 1 , y 1 ) and τ , IE (x 1 ,y 1 ),σ,τ (λ ∞ t=1 (1 -λ) t-1 u(x t , y t )) ≥ w(x 1 , y 1 ) -ε. And if the uniform value exists, it has to be v = lim λ v λ = lim n v n .

Adapted strategies

Our main theorem 3.3 suggests particularly interesting strategies for the players. Consider again conditions P 1 and P 2, and fix a pair of states (x, y). If u(x, y) ≥ v(x, y), the running payoff of Player 1 is at least as good as the payoff he should expect in the long run, so we may consider that Player 1 is "quite happy" with the current situation and in order to satisfy P 1 it is enough for him not to move, i.e. to choose p = δ x . If on the contrary u(x, y) < v(x, y), Player 2 is happy with the current situation and can choose q = δ y to satisfy P 2, whereas Player 1 should do something, and a possibility is to move towards a p satisfying P 1. This looks interesting for Player 1 because if Player 2 does not react, eventually the distribution on states will approach (p, y) and (in expectation) Player 1 will be happy again with the current situation since u(p, y) ≥ v(p, y). Definition 7.13. Let w in B(X × Y ).

A strategy of Player 1 is adapted to w if whenever the current state is (x, y), it plays p ∈ Γ(x) such that w(x, y) ≤ w(p, y) ≤ u(p, y).

A strategy of Player 2 is adapted to w if whenever the current state is (x, y), it plays q ∈ Γ(y) such that w(x, y) ≥ w(x, q) ≥ u(x, q). If w satisfies Q1, resp. Q2, Player 1, resp. Player 2, has a strategy adapted to w (using a measurable selection theorem [START_REF] Aliprantis | Infinite Dimensional Analysis: a Hitchhiker's Guide[END_REF]). If moreover w is excessive, we have

• Is there a strongly acyclic gambling game where the uniform value fails to exist?

• Recently splitting games have been extended to continuous time and linked to differential games with incomplete information [START_REF] Gensbittel | A Probabilistic Representation for the Value of Zero-Sum Differential Games with Incomplete Information on Both Sides[END_REF]. How our model and results extend to continuous time? The one player game has been investigated [START_REF] Buckdahn | On Representation Formulas for Long Run Averaging Optimal Control Problem[END_REF][START_REF] Li X | Limit Value for Optimal Control with General Means[END_REF].

Appendix

9.1 Proof of proposition 2.4

u being uniformly continuous over the compact set X × Y , we consider a concave modulus of continuity ω :

IR + -→ IR + : |u(x, y) -u(x ′ , y ′ )| ≤ ω(d(x, x ′ ) + d(y, y ′ )), ∀x, x ′ ∈ X, ∀y, y ′ ∈ Y.
ω is non decreasing, concave and lim 0 ω = 0. Denote by C the set of functions

v in C(X × Y ) satisfying: |v(x, y) -v(x ′ , y ′ )| ≤ ω(d(x, x ′ ) + d(y, y ′ )), ∀x, x ′ ∈ X, ∀y, y ′ ∈ Y.
We start with a lemma.

Lemma 9.1. For v in C, p, p ′ in ∆(X), q, q ′ in ∆(Y ), |ṽ(p, q) -ṽ(p ′ , q ′ )| ≤ ω(d KR (p, p ′ ) + d KR (q, q ′ )).
Proof of lemma 9.1: By the Kantorovich duality theorem, there exists µ in ∆(X × X) with first marginal p and second marginal p ′ satisfying: d KR (p, p ′ ) = X×X d(x, x ′ )dµ(x, x ′ ). Similarly there exists ν in ∆(Y × Y ) with first marginal q and second marginal q ′ satisfying: d KR (q, q ′ ) = Y ×Y d(y, y ′ )dν(y, y ′ ). We have for all x, x ′ , y, y ′ : v(x, y) ≥ v(x ′ , y ′ ) -ω(d(x, x ′ ) + d(y, y ′ )).

We integrate the above inequality with respect to the probability µ ⊗ ν, and obtain using the concavity of ω: ṽ(p, q) ≥ ṽ(p ′ , q ′ ) -X 2 ×Y 2 ω(d(x, x ′ ) + d(y, y ′ )) dµ(x, x ′ )dν(y, y ′ ), ≥ ṽ(p ′ , q ′ ) -ω X 2 ×Y 2 d(x, x ′ ) + d(y, y ′ ) dµ(x, x ′ )dν(y, y ′ ) = ṽ(p ′ , q ′ ) -ω (d KR (p, p ′ ) + d KR (q, q ′ )) .

We now return to the proof of proposition 2.4. Fix λ in (0, 1]. Given v in C, define Φ(v) : X × Y -→ IR by: Φ(v)(x, y) = sup p∈Γ(x) inf q∈Λ(y) λ u(x, y) + (1 -λ) ṽ(p, q). Consider the zero-sum game with strategy spaces Γ(x) and Λ(y) and payoff function (p, q) → λ u(x, y) + (1 -λ) ṽ(p, q). The strategy spaces are convex compact and the payoff function is is continuous and affine in each variable, hence by Sion's theorem we have: Φ(v)(x, y) = max p∈Γ(x) min q∈Λ(y) λ u(x, y)+(1-λ) ṽ(p, q) = min q∈Λ(y) max p∈Γ(x) λ u(x, y)+(1-λ) ṽ(p, q). Consider (x, y) and (x ′ , y ′ ) in X × Y , and let p in Γ(x) be an optimal strategy of Player 1 in the zero-sum game corresponding to (x, y). The gambling game has non expansive transitions, so there exists p ′ ∈ Γ(x ′ ) such that d KR (p, p ′ ) ≤ d(x, x ′ ). Consider any q ′ in Λ(y ′ ), there exists q in Γ(y) with d KR (q, q ′ ) ≤ d(y, y ′ ). Now, using lemma 9.1 we write: λu(x ′ , y ′ ) + (1 -λ)ṽ(p ′ , q ′ ) ≥ λ(u(x, y)-ω(d(x, x ′ )+d(y, y ′ ))+(1-λ)(ṽ(p, q)-ω(d KR (p, p ′ ) + d KR (q, q ′ ))), ≥ Φ(v)(x, y) -ω(d(x, x ′ ) + d(y, y ′ )). We obtain Φ(v)(x ′ , y ′ ) ≥ Φ(v)(x, y) -ω(d(x, x ′ ) + d(y, y ′ )), and Φ(v) belongs to C.

The rest of the proof is very standard. C is a complete metric space for vw = sup (x,y)∈X×Y |v(x, y)-w(x, y)|, and we have Φ(v)-Φ(w) ≤ (1-λ) v-w , so Φ is (1 -λ)-contracting. Hence Φ has a unique fixed point which is v λ . Each v λ is in C, and we obtain that the family (v λ ) λ∈(0,1] is equicontinuous, ending the proof of proposition 2.4.

Proof of proposition 6.3

We proceed in 4 steps.

1. The game at (b, a ′ ): It is intuitively clear that y λ ≥ x λ since Player 1 is better off when the players have different locations. We now formalize this idea. Consider the game at (b, a ′ ). The current payoff is 1, and Player 1 has the option not to move, so we obtain by definition 2.8:

y λ ≥ λ + (1 -λ) min β∈J (βx λ + (1 -β -β 2 )y λ + β 2 1).
This implies

λy λ ≥ λ + (1 -λ) min β∈J (β(x λ -y λ ) + β 2 (1 -y λ )),
and since y λ ≤ 1, we obtain: x λ ≤ y λ . Now, min β∈J (β(x λ -y λ ) + β 2 (1 -y λ )) ≥ min β∈J β(x λ -y λ ) + min β∈J β 2 (1 -y λ ) = 1/4(x λ -y λ ), hence:

(1 -λ)(y λ -x λ ) ≥ 4λ(1 -y λ ). [START_REF] Kohlberg | Repeated Games with Absorbing States[END_REF] In the same spirit, in the game at (a, a ′ ), Player 2 has the option not to move, so we have:

x λ ≤ (1 -λ) max α∈I (αy λ + (1 -α -α 2 )x λ + α 2 z λ ).
Hence, λx λ ≤ (1 -λ) max α∈I (α(y λ -x λ ) + α 2 (z λ -x λ )). ( 13)

2. The game at (a, a ′ ): Consider now the game at (a, a ′ ). By definition 2.8, x λ is the value of the game (possibly played with mixed strategies), where Player 1 chooses α in I, Player 2 chooses β in J and the payoff to Player 1 is:

(1 -λ)g λ (α, β), where g λ (α, β) =

x λ ((1-α-α 2 )(1-β-β 2 )+αβ)+y λ (β(1-α-α 2 )+α(1-β-β 2 ))+β 2 (1-α 2 )1+α 2 (1-β 2 )z λ .

We want to prove that in this game, it is a dominant strategy for Player 2 not to move, that is to choose β = 0. We need to show that for all α and β, g λ (α, 0) ≤ g λ (α, β). As a function of β, g λ (α, β) can be written as a constant plus:

β(1 -2α -α 2 )(y λ -x λ ) + β 2 (-(1 -α -α 2 )x λ -αy λ + 1 -α 2 -α 2 z λ ).
So we want to show that for all α in I, β in J:

(1 -2α -α 2 -αβ)(y λ -x λ ) + β((1 -α 2 )(1 -x λ ) -α 2 z λ ) ≥ 0
Since the expression is decreasing in α, it is enough to prove it with α = 1/4:

(7 -4β)(y λ -x λ ) + β(15(1 -x λ ) -z λ ) ≥ 0. This is true for β = 0, and will be true for all β in J if and only if it is true for β = 1/4, so we are left with proving:

24(y λ -x λ ) + 15(1 -x λ ) -z λ ≥ 0.

Consider λ ≤ 1/32, and recall that z λ ≤ 16λ. If x λ ≤ 1/2, then clearly (14) holds. Assume on the contrary that x λ ≥ 1/2, then z λ ≤ x λ , and (13) gives: λx λ ≤ (1 -λ) 1 4 (y λ -x λ ) + 0, so (y λ -x λ ) ≥ 2λ and ( 14) holds as well. We have shown that in the λ-discounted game at (a, a ′ ) with λ ≤ 1/32, Player 2 has a pure dominant strategy which is β = 0. Considering a pure best reply of Player 1 against this strategy implies that the game at (a, a ′ ) has a value in pure strategies satisfying x λ = (1 -λ) max α∈I (αy λ + (1 -α -α 2 )x λ + α 2 z λ ), i.e. equation ( 6) is proved.

Small discount factors:

For the sake of contradiction, assume that z λn ≥ x λn for a vanishing sequence λ n of discount factors. Then by equation ( 6), we have for each n:

λ n x λn = (1 -λ n )( 1 4
(y λn -x λn ) + 1 16 (z λn -x λn )).

  This is the unique function w : X → IR satisfying the conditions a), b), c), d) of Theorem 3.3: P 1 and P 2 implies u ≤ w ≤ 1, and because b and c are absorbing states, w(b) = 1 and w(c) = 0. Finally, w excessive gives w(a) = 1. Notice that δ b ∈ Γ ∞ (a) but for each n, δ b / ∈ Γn (a).

  and we obtain v(c, a ′ ) ≤ 1 1+β * v(c, b ′ ). But symmetrically we also have v(c, b ′ ) ≤ 1 1+β * v(c, a ′ ), and we get v(c, a ′ ) = v(c, b ′ ) = 0. Consider now v(a, c ′ ). By P 2, we obtain that v(a, c ′ ) ≥ u(a, c ′ ) = 1, and v(a, c ′ ) = 1. Similarly, v(b, c ′ ) = 1.

Definition 7 . 5 .

 75 A function v in B(X × Y ) satisfies the MZ-characterization if:

7. 3 . 1

 31 Idemptotent gambling games Definition 7.10. The gambling game is idempotent if Γ • Γ = Γ and Λ • Λ = Λ.

Both metrics are denoted by d, and we will use the metric d((x, y), (x ′ , y ′ )) = d(x, x ′ ) + d(y, y ′ ) on X × Y .

i.e. ∀ε > 0, ∃α > 0, ∀x, x ′ ∈ X with d(x, x ′ ) ≤ α, ∀p ∈ Γ(x), ∃p ′ ∈ Γ(x ′ ) s.t. d KR (p, p ′ ) ≤ ε.Since Γ has compact values, it implies that the graph of Γ is compact.

If originally the gambling game has non convex values, then allowing as usual players to randomize, would lead to transitions with convex values.

If X is finite and d(x, x ′ ) = 2 for x = x ′ , then d KR (p, p ′ ) = p -p ′ 1 for p, p ′ in ∆(X).

By convergence or limit point of {v λ }, we always mean when λ approaches 0.

The composition being defined byG • H(p) = {p" ∈ ∆(X), ∃p ′ ∈ H(p) s.t. p" ∈ G(p ′ )}.

We have first studied and understood this example before proving proposition 3.4. Example 2.7 shows that weakening the assumption of weakly acyclic gambling game to leavable gambling game is not possible in this proposition.

Except in part 2 of theorem 6.2 where we will consider the case I = {0, 1/4}.

Laraki's work was supported by (Idex [Grant Agreement No. ANR-11-IDEX-0003-02/Labex ECODEC No. ANR11-LABEX-0047] and ANR-14-CE24-0007-01 CoCoRICo-CoDec).

Corollaries and Extensions

Gambling houses (or Markov Decision Processes)

We assume here that there is a unique player, i.e. that Y is a singleton. Then non expansiveness is enough to guarantee the uniform convergence of (v λ ) λ (as well as the uniform value, see [START_REF]Uniform Value in Dynamic Programming[END_REF]) and the limit v can be characterized as follows [START_REF] Venel | A Distance for Probability Spaces, and Long-Term Values in Markov Decision Processes and Repeated Games[END_REF]: for all x in X, v(x) = inf{w(x), w : ∆(X) → IR affine C 0 s.t.

(1) ∀x ′ ∈ X, w(x ′ ) ≥ sup p∈Γ(x ′ ) w(p), and (2) ∀r ∈ R, w(r) ≥ u(r)},

where R = {p ∈ ∆(X), (p, p) ∈ Graph Γ} is interpreted as the set of invariant measures for the gambling house (which is not necessarily leavable here). If we moreover assume that the gambling house is leavable, then R = ∆(X) and we recover the fundamental theorem of gambling [START_REF] Dubins | Inequalities for Stochastic Processes[END_REF][START_REF] Maitra | Discrete Gambling and Stochastic Games[END_REF], namely, (v λ ) uniformly converges to:

It is also easy to see that v(x) = sup p∈Γ ∞ (x) u(p) for each x.

Our approach will lead to other characterizations. We don't assume any acyclicity condition in the following result.

Theorem 7.1. Consider a one player (leavable and non-expansive) gambling house. Then (v λ ) uniformly converges to the unique function v in C(X) satisfying: v is excessive, P 1 : ∀x ∈ X, ∃p ∈ Γ ∞ (x), v(x) = ṽ(p) ≤ ũ(p), and P 2 : v ≥ u.

Proof: From proposition 3.5 any accumulation point of (v λ ) is excessive and satisfies P 1 and P 2. Thus, we just need to show uniqueness, which is a direct consequence of the following lemma.

Using the gambling fundamental theorem, we obtain new viewpoints on the characterization of the limit value in leavable gambling houses.

Corollary 7.3. Consider a one player (leavable and non-expansive) gambling house. Then the asymptotic value exists and is:

(1) the smallest excessive function v in B(X) satisfying P 2;

(2) the largest excessive function v in B(X) satisfying P 1;

(3) the unique excessive function v in B(X) satisfying P 1 and P 2. Moreover, v is continuous. w(x, y) = w(p, y) ≤ u(p, y). Mertens Zamir [START_REF] Mertens | The Value of Two-Person Zero-Sum Repeated Games with Lack of Information on Both Sides[END_REF] in repeated games with incomplete information and Oliu-Barton [START_REF] Barton | The Splitting Game: Uniform Value and Optimal Strategies[END_REF] in splitting games used similar strategies derived from the MZ-characterization instead of the Q-characterization.

Vanishing L 1 -variation

In repeated games with incomplete information or in splitting games, an important property is that any martingale on a simplex has bounded variations. This suggests the following. Definition 7.14. A gambling house Γ has vanishing L 1 -variation if for every ε > 0, there is N such that for all n ≥ N and any sequence

The proof of the next result is inspired by Oliu-Barton [START_REF] Barton | The Splitting Game: Uniform Value and Optimal Strategies[END_REF] in the framework of splitting games. He shows that Player 1 (resp. Player 2) can uniformly guarantee any excessive-depressive function satisfying MZ1 (resp. MZ2). Our proof is much shorter because it uses the new Q-characterization. Proposition 7.15. In a standard gambling game where Γ has vanishing L 1variation, if w in B(X×Y ) is excessive-depressive and satisfies Q1, then a strategy of Player 1 adapted to w uniformly guarantees w.

Proof: Fix ε > 0. Because Lipschitz functions are dense in the set of continuous functions, there exists K > 0 and a K-Lispchtiz function u ε that is uniformly εclose to u. Consider w in B(X × Y ) be an excessive-depressive function satisfying Q1, let σ be a strategy of Player 1 adapted to w and let τ be any strategy of Player 2. We fix the initial states and write IE = IE (x 1 ,y 1 ),σ,τ .

Then, the average payoff of the n-stage game is:

Because the gambling game is of vanishing variation, there is N such that when n ≥ N one has K n n t=1 d KR (p t+1 , p t ) ≤ ε. Because of Q1, IE(u(x t+1 , y t )) ≥ IE(w(x t+1 , y t )) = IE(w(x t , y t )). Since w is depressive, IE(w(x t , y t ) ≥ IE(w(x t , y t-1 )), so that IE(w(x t+1 , y t )) ≥ IE(w(x t , y t-1 )), and this property holds for every t. Consequently, IE(u(x t+1 , y t )) ≥ IE(w(x 2 , y 1 )) = w(x 1 , y 1 ). We obtain finally Proof: If such a function exists, it can be guaranteed by both players. So it must be the uniform value of the game, which is unique whenever it exists.

Combining proposition 3.5, proposition 7.15 and corollary 7.16, we obtain the existence of the uniform value in a class of gambling games: Theorem 7.17. In a standard and idempotent gambling game where Γ and Λ have vanishing L 1 -variation, the uniform value v exists, and strategies adapted to v are uniformly optimal. Moreover, v is the unique excessive-depressive function in B(X × Y ) satisfying Q1 and Q2.

Proof: From proposition 3.5, any accumulation point of v λ satisfies P 1 and P 2, i.e. Q1 and Q2, so is unique and is the uniform value, as shown above.

Observe that acyclicity is not assumed in theorem 7.17. But vanishing L 1variation is a form of acyclicity (it rules out for example non-constant periodic orbits). A more formal link between acyclicity and vanishing variation is given in section 9.3 of the Appendix.

Open problems and future directions

We introduce the class of gambling games. It is a sub-class of stochastic games which includes MDP problems, splitting games and product stochastic games. We define a strong notion of acyclicity under which we prove existence of the asymptotic value v and we establish several characterizations of v which are linked to the Mertens-Zamir system of functional equations (re-formulated in our more general set-up). We also prove that our condition is tight: a slight weakening of acyclicity implies non-existence of the asymptotic value. Our example is the first in the class of product stochastic games and is probably the simplest known counterexample of convergence for finite state spaces and compact action set (the first counterexample in this class was established by Vigeral [START_REF] Vigeral | A Zero-Sum Stochastic Game with Compact Action Sets and no Asymptotic Value[END_REF]). Many questions merit to be investigated in a future research:

• In standard gambling games, is it possible to characterize the asymptotic value in models where we know it exists (for example when X and Y are finite, transition function is polynomial and Γ and Λ are definable [START_REF] Bolte | Definable Zero-Sum Stochastic Games[END_REF] in an o-minimal structure)? We know that the asymptotic value is excessivedepressive and satisfy P1 and P2, but this does not fully characterize it.

• Is there an asymptotic value if one house is strongly acyclic and the other not necessarily leavable? As seen, even when both houses are weakly acyclic, we may have divergence: strong acyclicity of one of the two houses is necessary.

Since z λn converges to 0, so does x λn and y λn , and moreover y λn -x λn λn converges to 0. This is in contradiction with equation [START_REF] Kohlberg | Repeated Games with Absorbing States[END_REF]. We have shown [START_REF] Buckdahn | On Representation Formulas for Long Run Averaging Optimal Control Problem[END_REF].

4. The game at (b, a ′ ) again: We proceed as for the game at (a, a ′ ) and will show that in the game at (b, a ′ ), it is a dominant strategy for Player 1 not to move. By definition, y λ is the value of the game where Player 1 chooses α in I, Player 2 chooses β in J and the payoff is λ

We want to show that h λ (0, β) ≥ h λ (α, β) for all α and β. That is, for all α and β,

For λ small enough, we have z λ ≤ x λ ≤ y λ , and the above property is satisfied. Hence in the game at (b, a ′ ) it is dominant for Player 1 to choose α = 0. Consequently, Player 2 has a pure optimal strategy and we can write:

proving equation [START_REF] Dubins | Invariant Gambling Problems and Markov Decision Processes[END_REF]. And the proof of proposition 6.3 is complete.