Mario Bravo
email: bravo@math.jussieu.fr

An adjusted payoff-based procedure for normal form games

Keywords: Normal form games, Learning, Adaptive dynamics, Stochastic approximation MSC2010 Subject classification: Primary: 91A26, 91A10 ; Secondary: 62L20, 93E35

come

Introduction

This paper studies an adaptive model for an N -player repeated game. We consider boundedly rational players that adapt using simple behavioral rules based on past experiences.

The decision that a player can make at each stage hinges on the amount of information available. Several approaches have been proposed depending on the information that agents can gather over time. Fictitious play (see Brown [START_REF] Brown | Iterative solution of games by fictitious play, Activity Analysis of Production and Allocation[END_REF], Fudenberg and Levine [START_REF] Fudenberg | The theory of learning in games[END_REF]) is one of the best studied procedures. Players adapt their behavior by performing best responses to the opponent's average past play over time. In this case, each player needs to know her own payoff function and to receive complete information about the other players' moves. A less restrictive framework is when each player is informed of all the possible payoffs that she could have received by using alternative moves. The exponential procedure (Freund and Shapire [START_REF] Freund | Adaptive game playing using multiplicative weights[END_REF]) is, among others, one example of this kind of adaptive processes.

We are interested in a less informative context. Players make no anticipation on the opponents' behavior and we assume that they have no information on the structure of the game. This means that agents have only their own space of actions and past realized payoffs to react to the environment. We suppose that players are given a rule of behavior (a decision rule) which depends on a state variable. The state variable is updated by a possibly time-dependent rule (an updating rule) based on the history of play and current observations. A widely studied model in this framework is the cumulative reinforcement learning procedure where players conserve a vector perception (the state variable), in which each coordinate of the vector represents how a move performs. The updating rule is defined by adding the payoff received to the component of the previous vector perception corresponding to the move actually played, and keeping the other components unaltered for the unused moves. The decision rule is given by the normalization of this perception vector assuming that payoffs are positive. Several results for the convergence (and nonconvergence) of players' mixed actions have been obtained (see Beggs [START_REF] Beggs | On the convergence of reinforcement learning[END_REF], Börgers and Sarin [START_REF] Börgers | Learning through reinforcement and replicator dynamics[END_REF], Laslier et al. [START_REF] Laslier | A behavioral learning process in games[END_REF], and a normalized version by Posch [22] for the 2-player game framework and Erev and Roth [START_REF] Erev | Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria[END_REF] for experimental results). In Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF] the authors study a model in the same spirit mainly in the case of Logit rule decision (which allows nonpositive payoffs) in the N -player case. Players update the perception vector by performing an average between the new payoff received and the former perception. Conditions are given to ensure the convergence to a Nash equilibrium of a perturbed version of the game. A similar model is studied by Leslie and Collins [START_REF] Leslie | Individual Q-learning in normal form games[END_REF], where results concerning 2-player games are obtained. Another approach in this information framework is developed by Hart and Mas-Colell [START_REF]A reinforcement procedure leading to correlated equilibrium[END_REF] where the analysis focuses on the convergence of the empirical frequency of play instead of the long-term behavior of the mixed strategy. Using techniques based on consistent procedures (see Hart and Mas-Colell [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF]), it is shown that, for all games, the set of correlated equilibria is attained.

We consider here a particular updating rule where players keep a perception vector that is updated, on the coordinate corresponding to the strategy played, by computing the average between the previous perception and the payoff received using the number of times that each strategy has been played. The resultant process turns out to be a variation of the one studied by Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF], but in our case, players use more information on the history of play. Using the tools provided by the stochastic approximation theory (see e.g., Benaïm [3], Benveniste et al. [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF], Kushner and Yin [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF]), the asymptotic behavior of the process can be analyzed by studying a related continuous dynamics. We are interested in the case in which players use the Logit decison rule and our aim is to find general conditions to have almost sure, or with positive probability, convergence to an attractor of the associated ODE. This case is particularly interesting because the rest points of the ODE are the Nash equilibria of a related game. This paper is organized as follows. Section 2 describes the very basic aspects of the stochastic approximation theory. Section 3 states precisely our model in the framework of an infinitely repeated N -player normal form game. In Section 4, we restate our algorithm to make it fit in the set-up of the stochastic approximation and we provide a general almost sure convergence result. In Section 5.1 we treat the case of the Logit rule in detail. We start by finding an explicit condition to ensure almost sure convergence derived from Section 4. This condition demands the smoothing parameters associated to the Logit rule to be sufficiently small. It is worth noting that, up to this point, we proved that the same results obtained for the process studied by Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF] hold in our setting. Given this fact, we perform a comparison between these two processes in terms of the path-wise rate of convergence. Later, under a weaker assumption, we study the convergence with positive probability to attractors. We apply this result to a particular traffic game on a simple network (studied as an application in [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF]) showing that a convergence with positive probability property holds under a much weaker assumption than in the general case. Next, we provide some examples where the convergence is lost. Finally, in Section 6, we prove that part of the analysis can be recovered if players face random payoffs. For that purpose, we use some known techniques that, to our knowledge, do not seem very exploited in the framework of learning in games.

Preliminaries

In this section, we revisit some basic aspects of the stochastic approximation theory following the approach in Benaïm [START_REF]Dynamics of stochastic approximation algorithms[END_REF]. The motivation is to study the following discrete process in

R d z n+1 -z n = γ n+1 H(z n ) + V n+1 , (2.1)
where (γ n ) n is a nonnegative step-size sequence, H : R d → R d is a continuous function and (V n ) n is a (deterministic or random) noise. Let us denote by L(z n ) the limit set of the sequence (z n ) n , i.e., the set of points z such that lim l→+∞ z n l = z for some sequence n l → +∞.

The connection between the asymptotic behavior of the discrete process (2.1) and the asymptotic behavior of the continuous dynamics ż = H(z)

is obtained as follows. Given ε > 0, T > 0, a set Z ⊆ R d and two points x, y ∈ Z, we say that there is an (ε, T )-chain in Z between x and y if there exist k solutions of (2.2) {x 1 , . . . , x k } and times {t 1 , . . . , t k } greater than T such that [START_REF] Beggs | On the convergence of reinforcement learning[END_REF] x i ([0, t i ]) ⊆ Z for all i ∈ {1, . . . , k},

(2) x i (t i ) -x i+1 (0) < ε for all i ∈ {1, . . . , k -1}, (3) x 1 (0) -x < ε and x k (t k ) -y < ε. Definition 2.1. A set D ⊆ R d is Internally Chain Transitive (ICT) for the dynamics (2.
2) if it is compact and for all ε > 0, T > 0 and x, y ∈ D there exists an (ε, T )-chain in D between x and y.

This definition is derived from the notion of Internally Chain Recurrent sets introduced by Conley [START_REF] Conley | Isolated invariant sets and the Morse index[END_REF]. Roughly speaking, on an ICT set, we can link any two points by a chain of solutions of the dynamics (2.2) by allowing small perturbations. ICT sets are compact, invariant and attractor-free.

In Benaïm [START_REF]Dynamics of stochastic approximation algorithms[END_REF] the following general theorem is proved.

γ i+1 V i+1 ; k ∈ {n + 1, . . . , m( n j=1 γ j + T )} = 0,
where m(t) is the largest integer l such that t ≥ l j=1 γ j . Then L(z n ) is an ICT set for the dynamics (2.2).

Remark 2.3. In the case where the noise (V n ) n in (2.1) is a martingale difference sequence with respect to some filtration on a probability space, we say that (2.1) is a Robbins-Monro [START_REF] Robbins | A stochastic approximation method[END_REF] algorithm. In this framework if, for instance, sup n E( V n 2 ) < +∞ and (γ n ) n ∈ l 2 (N) then assumption (c) in Theorem 2.2 holds with probability one (see Benaïm [3,Proposition 4.2]). Moreover this result is still valid if the noise can be decomposed into a martingale difference process plus a random variable that converges to zero almost surely.

The model

An N -player normal form game is introduced as follows. Let A = {1, 2, . . . , N } be the set of players. For every i ∈ A let S i be the finite strategy set for player i and let the set

∆ i = {z ∈ R |S i | ; z i ≥ 0, i z i = 1}
denote her mixed strategy set. S = i∈A S i is the set of strategy profiles and ∆ = i∈A ∆ i is the set of mixed strategy profiles. We write as (s, s -i ) ∈ S the strategy profile where player i uses the strategy s ∈ S i and her opponents use the strategy profile s -i ∈ j =i S j and we adopt the same notation when a mixed strategy profile is involved. The payoff function to each player i ∈ A is denoted by G i : S → R as well as its multilinear extension

G i : ∆ → R.
The game is repeated infinitely and we suppose that players are not informed about the structure of the game, i.e., neither the number of players (or their strategies) nor the payoff functions are known. At the stage n ∈ N, each player i selects a strategy s i n ∈ S i using the mixed strategy σ i n ∈ ∆ i . Then, she gets her own payoff g i n = G i (s i n , s -i n ) and this is the only information she receives. For every n ∈ N and for each player i, we assume that the mixed strategy at stage n , σ i n ∈ ∆ i , is determined as a function of a previous perception vector x i n-1 ∈ R |S i | , i.e., σ i n = σ i (x i n-1 ) with σ i : R |S i | → ∆ i . The state space for the perception vector profiles x = (x 1 , . . . , x N ) ∈ i∈A R |S i | is denoted X. We also assume that, for every i ∈ A, the function σ i : R |S i | → ∆ i is continuous, and for all s ∈ S i and

x i ∈ R |S i | , σ is (x i ) > 0. (A)
We refer to the function σ : X → ∆ with σ(x) = (σ 1 (x 1 ), . . . , σ N (x N )) as the decision rule of the players.

At the end of the stage n, each player i uses the value g i n and x i n-1 to obtain the new perception vector x i n , and so on. The manner in which x n is updated is called the updating rule of the players. Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF] study the following updating rule

x is n+1 = 1 -γ n+1 x is n + γ n+1 g i n+1 , if s = s i n+1 , x is n , otherwise, (3.1)
where we assume that γ n = 1 n (see Remark 4.3 for an explanation on this choice). In this paper we consider a variation of (3.1). Players will use more information by taking into account the number of times that their actions have been played. Explicitly, we define the adjusted process (AP) by

x is n+1 =    1 - 1 θ is n x is n + 1 θ is n g i n+1 , if s = s i n+1 , x is n , otherwise, (AP)
where θ is n denotes the number of times that strategy s has been used by player i ∈ A up to time n. Given the particular structure in (AP), we can suppose that x n lies in a compact subset of X for all n ∈ N. We also note that (A) implies that the decision rule can be assumed component-wise bounded away from zero.

For feasibility issues we suppose that θ is 0 > 0 for all i ∈ A and s ∈ S i and then θ is n is not exactly the number of times that the action s ∈ S i has been used by player i (since it contains the initial condition), but we keep this interpretation. This assumption is not relevant in the asymptotic analysis developed further on.

As usual we denote by F n the σ-algebra generated by the history up to time n, F n = σ (s m , g m ) 1≤m≤n , where s m = (s 1 m , . . . , s N m ) and g m = (g 1 m , . . . , g N m ).

Asymptotic analysis

The main difficulty to analyze (AP) using the tools decribed in Section 2, is that we have a stochastic algorithm in discrete time where the step-size is random and, moreover, depends on the coordinates of the vector to update. Thus, in order to study the asymptotic properties of our adaptive process, let us restate the updating scheme (AP) in the following manner

x is n+1 -x is n = 1 θ is n (g i n+1 -x is n )1 {s=s i n+1 } = 1 (n + 1)λ is n (g i n+1 -x is n )1 {s=s i n+1 } ,
where λ is n = θ is n n+1 is interpreted as the empirical frequency of action s for player i up to time n and 1 C stands for the indicator function of the set C. Without loss of generality, assume that 0 < θ is 0 ≤ 1, for every i ∈ A and s ∈ S i , in order to have λ i ∈ ∆ i for al n ∈ N. Standard computations involving averages show that

λ is n+1 -λ is n = 1 n + 1 1 {s=s i n+1 } -λ is n + b n+1 , and
b n+1 = - 1 n + 2 1 {s=s i n+1 } -λ is n = O 1 n . (4.1)
Then we can express (AP) differently by introducing the empirical frequency of play. The new form is the (up to a vanishing term) martingale difference scheme

           x is n+1 -x is n = 1 n + 1 σ is (x i n ) λ is n (G i (s, σ -i (x n )) -x is n ) + U is n+1 , λ is n+1 -λ is n = 1 n + 1 σ is (x i n ) -λ is n + M is n+1 , (APD)
where the noise terms are explicitly

U is n+1 = 1 λ is n (g i n+1 -x is n )1 {s=s i n+1 } - σ is (x i n ) λ is n (G i (s, σ -i (x n )) -x is n ) , = 1 λ is n (g i n+1 -x is n )1 {s=s i n+1 } -E 1 λ is n (g i n+1 -x is n )1 {s=s i n+1 } | F n , M is n+1 = 1 {s=s i n+1 } -σ is (x i n ) + b n+1 , = 1 {s=s i n+1 } -λ is n -E( 1 {s=s i n+1 } -λ is n | F n ) + b n+1 . (4.2)
From now on, we denote by ǫ n = (U n , M n ) the noise term associated to our process.

The scheme (APD) will allow us to deal with the random (and player-dependent) character of the step-size in (AP). Now, in the spirit of Theorem 2.2, the asymptotic behavior of (APD) is related with the continuous dynamics

         ẋis t = σ is (x i t ) λ is t G i (s, σ -i (x t )) -x is t = Ψ is x (x t , λ t ), λis t = σ is (x i t ) -λ is t = Ψ is λ (x t , λ t ), (4.3) with Ψ x : X × ∆ → i∈A R |S i | and Ψ λ : X × ∆ → i∈A ∆ i 0 , and ∆ i 0 standing for the tangent space to ∆ i , i.e., ∆ i 0 = {z ∈ R |S i | ; s∈S i z s = 0}. Let us denote Ψ the function defined by Ψ(x, λ) = (Ψ x (x, λ), Ψ λ (x, λ)).
For the sake of completeness, let us write the process (3.1) as

x is n+1 -x is n = 1 n + 1 σ is (x i n )(G i (s, σ -i (x n )) -x is n ) + Ũ is n+1 , (4.4)
with noise term given by

Ũ is n+1 = (g i n+1 -x is n )1 {s=s i n+1 } -σ is (x i n )(G i (s, σ -i n (x n )) -x is n ), = (g i n+1 -x is n )1 {s=s i n+1 } -E((g i n+1 -x is n )1 {s=s i n+1 } | F n ). (4.5)
Therefore, the corresponding continuous dynamics is given by

ẋis t = σ is (x i t ) G i (s, σ -i (x t )) -x is t = Φ is (x t ), (4.6)
where Φ :

X → i∈A R |S i | .
Remark 4.1. Observe that the following simple fact holds

(x, σ(x)) ∈ X × ∆ is a rest point of (4.3) ⇔ x ∈ X is a rest point of (4.6).
In the sequel we will show that asymptotic properties similar to those of (4.4) can be obtained for our process. This means that explicit conditions can be found to ensure that the process (APD) converges almost surely to a global attractor for the dynamics (4.3).

Recall that we have assumed that, for every n ∈ N and i ∈ A, the mixed action σ i n ∈ ∆ i is component-wise bounded away from zero. The purpose of the next simple lemma is to verify that the same holds, almost surely, for the empirical frequencies of play. Lemma 4.2. For n ≥ 1, let σ n be a probability distribution over a finite set T and let i n+1 be an element of T which is drawn with law σ n and assume (σ n ) n is adapted to the natural filtration generated by the history. For all j ∈ T , set

λ j n = γ n n p=1 1 {ip=j} ,
where (γ n ) n is a decreasing positive real sequence such that n γ n = +∞ and n γ 2 n < +∞. Assume that there exists σ > 0 such that σ j n ≥ σ. Then

lim inf n→+∞ λ j n ≥ σ,
almost surely, for every j ∈ T .

Proof. Fix j ∈ T and let F k be the σ-algebra generated by the history {i 1 , . . . , i k } up to time k.

Then we have that

E(1 {i k =j} | F k-1 ) = σ j k-1 ≥ σ.
On the other hand the random process (φ j n ) n given by

φ j n = n k=1 γ k 1 {i k =j} -E(1 {i k =j} | F k-1 )
is a martingale and sup n∈N (

φ j n ) 2 ≤ C • p≥1 γ 2 p < +∞ for some constant C. Hence (φ j n ) n converges almost surely. Now Kronecker's lemma (see e.g., Shiryaev [25, Lemma IV.3.2]) gives that lim n→+∞ γ n n k=1 1 {i k =j} -E(1 {i k =j} | F k-1 ) = 0. (4.7) So that γ n n k=1 (1 {i k =j} -E(1 {i k =j} | F k-1 )) ≤ λ j n -σ.
Taking lim inf and using (4.7) we conclude.

Remark 4.3. Observe that we have defined an adjusted version of (4.4) with γ n = 1 n . The previous lemma shows that all the analysis in this section can be carried out for more general stepsize sequences (γ n ) n by taking λ is n = θ is n γ n . We adopt γ n = 1 n to keep the convenient interpretation in terms of frequencies of play. Proof. We only have to show that our process satisfies the hypotheses of Theorem 2.2. The assumptions concerning the regularity of the function involved, the step-size sequence and the boundedness of the process (x n , λ n ) n hold immediately.

According to (4.2), (M n ) n is almost surely bounded and can be written as a martingale difference scheme plus a vanishing term. Observe that E(U n+1 | F n ) = 0 and that

U is n+1 ≤ C/λ is n ,
for some constant C. Then Lemma 4.2 implies that U n is almost surely bounded. In view of Remark 2.3, assumption (c) of Theorem 2.2 holds for the noise term ǫ n = (U n , M n ) and the conclusion follows.

Let us define the function F :

X → i R |S i | by F is (x) = G i (s, σ -i (x)). (4.8)
Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF] show that if the function F is contracting for the infinity norm, then the process (4.4) converges almost surely to the unique rest point of the dynamics (4.6). The following result shows that the same holds for the process (APD) by adding a slighlty stronger assumption on the decision rule σ.

Proposition 4.5. Assume that F is contracting for the infinity norm and that, for every i ∈ A, the function σ i is Lipschitz for the infinity norm. Then there exists a unique rest point (x * , σ(x * )) ∈ X × ∆ of (4.3). Furthermore, the set {(x * , σ(x * ))} is a global attractor and the process (APD) converges almost surely to (x * , σ(x * )).

Proof. According to Remark 4.1, (x * , σ(x * )) ∈ X×∆ is a rest point of (4.3) if and only if F (x * ) = x * , hence the existence and uniqueness follow from the fact that F is contracting.

Let 0 ≤ L < 1 and K i be the Lipstchitz constants associated to the functions F and σ i , i ∈ A, respectively. We want to find a suitable strict Lyapunov function, i.e., a function V that decreases along the solution paths and that verifies

V -1 ({0}) = {(x * , λ * )} with λ * = σ(x * ). Let V : X × ∆ → R + be defined by V (x, λ) = max x -x * ∞ , 1 ζ λ -λ * ∞ ,
where ζ > 0 will be defined later on. The function V is the maximum of a finite number of smooth functions, therefore it is absolutely continuous and its derivatives are the evaluation of the derivatives of the function attaining the maximum. We distinguish two cases:

Case 1. V (x t , λ t ) = x t -x * ∞ . Let i ∈ A and s ∈ S i be such that V (x t , λ t ) = |x is t -x is * |. Let us assume that x is t -x is * ≥ 0. Then, for almost all t ∈ R, d dt V (x t , λ t ) = d dt (x is t -x is * ) = σ is (x i t ) λ is t F is (x t ) -F is (x * ) + x is * -x is t ≤ -ξ(1 -L) x t -x * ∞ = -ξ(1 -L)V (x t , λ t ), for some ξ > 0 such that σ is (x) ≥ ξ for every i ∈ A and s ∈ S i . If x is t -x is * < 0, the computations are analogous. Case 2.: V (x t , λ t ) = 1 ζ λ t -x * ∞ . Let i ∈ A and s ∈ S i be such that V (x t , λ t ) = 1 ζ |λ jr t -λ jr * |. We also assume that λ jr t -λ jr * ≥ 0. Then, for almost all t ∈ R, d dt V (x t , λ t ) = 1 ζ σ jr (x j t ) -σ jr (x * ) + λ jr * -λ jr t ≤ - 1 ζ λ t -λ * ∞ + 1 ζ |σ jr (x j t ) -σ jr (x * )| ≤ -V (x t , λ t ) + max i K i ζ x t -x * ∞ = -(1 - max i K i ζ )V (x t , λ t ),
and we take ζ > 0 sufficiently large to have 1 > max i K i /ζ. Again, if the relation λ jr tλ jr * < 0 holds, the computations are the same.

Hence V (x t , λ t ) ≤ -KV (x t , λ t ) for some K > 0. So V decreases exponentially fast along the solution paths of the dynamics and V (x, λ) = 0 if and only if (x, λ) = (x * , λ * ). Therefore the set {(x * , λ * )} is a global attractor which is the unique ICT set for (4.3) (see [START_REF]Dynamics of stochastic approximation algorithms[END_REF]Corollary 5.4]). Proposition 4.4 finishes the proof.

Logit rule

In this section we will focus on the analysis of a particular decision rule: the Logit rule which has a large foundation in the field of discrete choice models as well as in game theory. Explicitly the decision rule σ : X → ∆ is given by

σ is (x i ) = exp (β i x is ) r∈S i exp (β i x ir ) , (5.1)
for every i ∈ A and s ∈ S i , where β i > 0 is called the smoothing parameter for player i. According to Remark 4.1, the following result shows that the rest points of the dynamics (4.3) are the Nash equilibria for an entropy perturbed version of the original game.

Lemma 5.1 (Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF]). Under the Logit decision rule (5.1), if x ∈ X is a rest point of the dynamics (4.6), then σ(x) is a Nash equilibrium of a game where the strategy set for the each player i is ∆ i and her payoff G i : ∆ → R is given by

G i (π) = s∈S i π is G i (s, π -i ) - 1 β i s∈S i π is ln(π is ) -1 .
(5.2)

Almost sure convergence

We want to apply Proposition 4.5 in this particular framework. For that purpose, let us introduce the maximal unilateral deviation payoff that a single player can face,

η = max i∈A,s∈S i r 1 ,r 2 ∈ S-i |G i (s, r 1 ) -G i (s, r 2 )|, (5.3)
where

S-i = {(r 1 , r 2 ) ∈ S -i × S -i ; r k 1 = r k 2
for exactly one k}. Now we can show the following proposition that ensures that, if the parameters are sufficiently small, the unique attractor is attained with probability one. From now on, we denote α = max i∈A j =i β j . Proposition 5.2. If 2ηα < 1, the discrete process (APD) converges almost surely to the unique rest point (x * , σ(x * )) of the dynamics (4.3).

Proof. We know from Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF]Proposition 5] that, if 2ηα < 1, the function F (defined in (4.8)) is contracting for the infinity norm. Observe also that, for every i ∈ A, the function σ i is Lipschitz for the infinity norm, since it is a smooth function defined on a compact set. Therefore, Proposition 4.5 applies.

Rate of Convergence

Up to this point, we were able to reproduce some of the theoretical results of the original model (4.4) regarding its almost sure convergence to global attractors. Now, we want to justify the inclusion of a counter of the previous actions in terms of the rate of convergence when both learning processes (APD) and (4.4) converge almost surely to (x * , λ * ) and x * , respectively, and the step-size γ n = 1 n is considered. This rate of convergence is deeply linked with the largest real part eigenvalue of the Jacobian matrix of the functions Ψ = (Ψ x , Ψ λ ) and Φ at the respective rest points.

Let us denote ρ(B) the maximal real part of the eigenvalues of a matrix B ∈ R k×k , i.e., ρ(B) = max{Re(µ j ); j = 1, . . . , k, where µ j ∈ C is an eigenvalue of the matrix B}.

We say that a matrix B is stable if ρ(B) < 0.

Lemma 5.3. Assume that 2ηα < 1. Let (x * , λ * ) and x * be the unique rest points of the dynamics (4.3) and (4.6), respectively. Then

-1 ≤ ρ(∇Ψ(x * , λ * )) < - 1 2 ≤ - N k∈A |S k | ≤ ρ(∇Φ(x * )) < 0. (5.4)
Proof. Straigthforward computations concerning the function Ψ (see (4.3)) show that

∂Ψ is λ ∂x jr (x * , λ * ) = 0 and ∂Ψ is λ ∂λ jr (x * , λ * ) = -1 {is=jr} ,
for every i, j ∈ A and (s, r) ∈ S i × S j . Therefore, the matrix ∇Ψ(x * , λ * ) looks like

∇Ψ(x * , λ * ) = ∇ x Ψ x (x * , λ * ) 0 L -I , (5.5)
where I stands for the identity matrix and ∇ x Ψ x (x * , λ * ) denotes the Jacobian matrix of Ψ x with respect to x at (x * , λ * ). Notice that the interesting eigenvalues of this matrix are given by its upperleft block because of the zero block and the identity matrix on the right side in (5.5). Observe also that ∂Ψ is x ∂x is (x * , λ * ) = -1, i.e., the matrix ∇ x Ψ x (x * , λ * ) has diagonal terms equal to -1. On the other hand, we know that every eigenvalue of a complex matrix B = (B pq ) lies within at least one of the Gershgorin discs

D p (B) = {z ∈ C, |z -B pp | ≤ R p } where R p = q =p |B pq |.
Given the specific form of the matrix ∇ x Ψ(x * , λ * ) we can estimate the position of its eigenvalues. So, in our case,

R is = j∈A, j =i r∈S j ∂Ψ is x ∂x jr (x * , λ * ) ,
since ∂Ψ is x ∂x jr (x * , λ * ) = 0 if i = j and r = s. This follows from the fact that F is (x) (defined in (4.8)) is independent of the vector x i . Explicitly,

∂Ψ is x ∂x jr (x * , λ * ) = β j σ jr * G i (s, r, σ -(i,j) * ) -G i (s, σ -i * ) ,
where

G i (s, r, σ -(i,j) * ) = a∈S -i a j =r G i (s, a) k =i k =j σ ka k * , for i = j. So that R is = j∈A j =i β j r∈S j σ jr * G i (s, r, σ -(i,j) * ) -G i (s, σ -i * )
≤ ηα.

Then we have that all the eigenvalues of the matrix ∇ x Ψ x (x * , λ * ) are contained in the complex disc

{z ∈ C, |z + 1| ≤ ηα} ⊇ i∈A s∈S i D is (∇ x Ψ x (x * , λ * )), (5.6)
which implies that ρ(∇Ψ(x * , λ * )) < -1/2.

Analogous computations involving the function Φ show that

D is (∇Φ(x * )) ⊆ {z ∈ C, |z + σ is * | ≤ σ is * ηα}, for every i ∈ A and s ∈ S i . Since -σ is * + σ is * ηα < 0, then ρ(∇Φ(x * )) < 0. The fact that -1 ≤ ρ(∇Ψ(x * , λ * )) is evident. Finally, the inequality -N/ k |S k | ≤ ρ(∇Φ(x * ))
follows since the trace of the matrix ∇Φ(x * ) is equal to -N . The following reduced version of Chen [8, Theorem 3.1.1] will be useful.

Theorem 5.5. Consider the discrete process given by (2.1). Assume that the following hold.

(a) For every n ∈ N, γ n > 0, lim n→+∞ γ n = 0, n γ n = +∞ and

lim n→+∞ γ n -γ n+1 γ n+1 γ n = γ ≥ 0. (b) z n → z 0 almost surely.
(c) There exists δ ∈ (0, 1] such that (c.1) for a path such that z n → z 0 , the noise V n can be decomposed in

V n = V ′ n + V ′′ n where n≥1 γ 1-δ n V ′ n+1 < +∞ and V ′′ n = O(γ δ n ),
(c.2) the function H is locally bounded and is differentiable at z 0 such that H(z) = H(zz 0 ) + r(z) where r(z 0 ) = 0 and r(z) = o( zz 0 ) as z → z 0 and (c.2) the matrix H is stable and, furthermore, H + δγI is also stable.

Then, almost surely,

(1/γ n ) δ (z n -z 0 ) → 0, as n → +∞.
The previous result allows us to show that, in some sense, our algorithm is faster. This will show that, under the common hypothesis 2ηα < 1 (which ensures almost sure convergence for both processes), the employment of the adjusted process (APD) will help the players to adapt faster their behavior than the original process (4.4).

Proposition 5.6. Assume that 2ηα < 1 and let (x * , λ * ) ∈ X × ∆ and x * ∈ X be the unique rest points of the dynamics (4.3) and (4.6), respectively. Then the following estimates hold (i) for almost all trajectories of (4.4)

n δ (x n -x * ) → 0, as n → +∞,
for every δ ∈ (0, |ρ(∇Φ(x * ))|),

(ii) for almost all trajectories of (APD)

n δ (x n , λ n ) -(x * , λ * ) → 0, as n → +∞,
for every δ ∈ (0, 1/2).

Proof. Recall that ǫ n = (U n , M n ) and Ũn are the noise terms associated to (APD) and (4.4), respectively (see (4.2) and (4.5)). We observe that, for both processes, hypotheses (a) and (b) in Theorem 5.5 are immediately satisfied since γ n = 1 n , (with γ = 1) and since Proposition 5.2 applies. Let us verify that condition (c) holds.

(i) Fix δ ∈ (0, |ρ(∇Φ(x * ))|). The random process ( Ũn ) n is almost surely bounded and satisfies that

E( Ũn+1 | F n ) = 0. Therefore, Z n = n k=1 (1/k) 1-δ
Ũk+1 is a martingale where sup n Z n 2 < +∞ k=1 (1/k) 2(1-δ) < +∞, thus convergent (since δ < 1/2). To conclude, observe that the function Φ is smooth and that the matrix ∇Φ(x * ) + δI is stable.

(ii) Fix δ ∈ (0, 1/2). We repeat the argument by noticing that ǫ n = ǫn + bn where bn = O(1/n) and E(ǫ n+1 | F n ) = 0. To finish, we use the fact that the matrix ∇Ψ(x * , λ * ) + δI is stable since inequality (5.4) holds.

Remark 5.7. Two important comments are in order.

(a) For the process (APD), if the matrix C n = E(ǫ T n+1 ǫ n+1 | F n ) converges almost surely to a deterministic positive definite matrix C, then √ n((x n , λ n )-(x * , λ * )) converges in distribution to a normal random variable (see e.g., Benveniste et al. [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF] or Kushner and Yin [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF]). For the process (4.4), if the sequence Cn = E( Ũ T n+1 Ũn+1 | F n ) converges almost surely to a deterministic positive definite matrix C, then it can be shown (see Duflo [START_REF] Duflo | Random iterative models[END_REF]) that n |ρ(∇Φ(x * ))| (x nx * ) converges almost surely to a finite random variable. For instance, if we consider the game defined by (5.7), we can show that both sequences (C n ) n and ( Cn ) n converge almost surely to a deterministic positive definite matrix and that |ρ(∇Φ(x * ))| < 1/2. Therefore, in general, nothing more can be said when the step-size γ n = 1 n is considered. Figure 1 consists in the results of a numerical experience in this particular example where 2ηα = 0.8 and |ρ(∇Φ(x * ))| ≈ 0.3.

(b) Observe that a better rate can be achieved for the process (4.4) if the step-size is given by γ n = a n for a > |ρ(∇Ψ(x * ))|. This leads to the rate o(n -δ ) for all δ ∈ (0, 1/2). However it is fairly unrealistic to assume that the players know in advance this information. Nevertheless, we always have that |ρ(∇Φ(x * ))| < |ρ(∇Ψ(x * , λ * ))| and then the scheme (APD) can reach at least the same path-wise rate of convergence under the hypotheses of Proposition 5.6 and independent of the step-size considered.   (0, 0) (1, 0) (0, 1) (0, 1) (0, 0) (1, 0) (1, 0) (0, 1) (0, 0)

||x n -x * || 2 ||(x n , λ n ) -(x * , λ * )|| 2 Figure 1: (x n , λ n ) -(x * , λ * ) 2 versus x n -x * 2 .

Convergence with positive probability

The estimates given by Lemma 5.3 allows us to improve the range of parameters in which general convergence results can be obtained for the process (APD). We start by showing that there exists a unique rest point of (4.3) which is stable if 1 ≤ 2ηα < 2. Let Y ⊆ X × ∆ be the set of rest points of (4.3) and let B(A) be the basin of attraction corresponding to the attractor A. Given the fact that basins of attraction cannot overlap, the set Y is finite since X × ∆ is compact and Ψ is regular. Finally, Y reduces to one point since, in this case, it is impossible to have finitely many stable equilibibria due to the Poincaré-Hopf Theorem (see e.g., Milnor [20,Chapter 6]).

The following definition is crucial to ensure convergence with positive probability of the process (x n , λ n ) n to a given (not necessarily global) attractor.

Definition 5.9. Let (z n ) n be a discrete stochastic process with state space Z. A point z ∈ Z is attainable by

(z n ) n if for each m ∈ N and every open neighborhood U of z, P(∃n ≥ m, z n ∈ U ) > 0.
The following lemma uses strongly the particular form of the updating rule (AP) considered in this work.

Lemma 5.10.

Fix λ = (λ 1 , . . . , λ N ) ∈ ∆. Set x i ∈ R |S i | such that x is = G i (s, λ -i ) for all s ∈ S i
and put x = (x 1 , . . . , x N ) ∈ X. Then, the point (x, λ) ∈ X ×∆ is attainable by the process (x n , λ n ) n .

In particular, any rest point of the dynamics (4.3) is attainable.

Proof. The fact that σ is n ≥ ξ > 0 for every i ∈ A, s ∈ S i and n ∈ N implies that any finite sequence generated by (APD) has positive probability. The updating rule (AP) can be expressed as (including only for this time the initial conditions)

x is n+1 = 1 θ is n + θ is 0 g i υ is (θ is n ) + g i υ is (θ is n -1) + • • • + g i υ is (1) + x is 0 , (5.8)
where υ is (k) = inf{q ≥ 1, θ is q = k}, i.e., the stage when player i has played strategy s ∈ S i for the k-th time. Observe that, without loss of generality, we can suppose that m = 0 in the definition of attainability given the particular form of the updating rule (5.8).

Let ζ s

n be the number of times that the strategy profile s ∈ S has been played up to time n. Hence, for every i ∈ A and s ∈ S i , (5.8) implies that

x is n+1 = r∈S -i G i (s, r) ζ (s,r) n θ is n + θ is 0 + x is 0 θ is n + θ is 0 , = r∈S -i G i (s, r) ζ (s,r) n θ is n + b n , with b n = O (θ is n ) -1 .
Observe that θ is n → +∞ almost surely due to the conditional Borel-Cantelli lemma. Fix ε > 0 and let n be an integer such that k i s = n ki s ∈ N, where, for every i ∈ A and s ∈ S i , ki s denotes a rational number satisfying that |λ iski s | < ε. For a strategy profile s ∈ S, let us define the positive integers n s = i∈A k i s i and n = s∈S n s . Now we take the sequence generated by (APD) defined by l ∈ N blocks of size n where within each block, each s ∈ S is played exactly n s times, regardless the order of play. Fix i ∈ A and r ∈ S -i , so that, by construction

ζ (s,r) ln θ is ln = j =i k j r j k i s k i s u∈S -i j =i k j u j = j =i kj r j j =i |S j | p j =1 kj p j = j =i λ jr j + bε ,
where bε → 0 as ε → 0. Finally, given ε ′ > 0, take l large and ε small to have

(x ln+1 , λ ln+1 ) -(x, λ) < ε ′ .
Recall that L(z n ) is the limit set of the sequence (z n ) n . The following result is the goal of this subsection.

Proposition 5.11. If an attractor A for the dynamics (4.3) satisfies that B(A) ∩ Y = ∅, then P(L(x n , λ n ) ⊆ A) > 0. In particular, under the Logit decision rule decision (5.1), if 1 ≤ 2ηα < 2, then Y reduces to one point (x * , λ * ) and P((

x n , λ n ) → (x * , λ * )) > 0.
Before providing the proof we need to briefly introduce the following concepts. Let φ be the semi-flow induced by the differential equation ( 4.3) and let Y t the continuous time affine process associated to the discrete process (x n , λ n ) n , i.e.,

Y (τ n + u) = (x n , λ n ) + u (x n+1 , λ n+1 ) -(x n , λ n ) τ n+1 -τ n , (5.9)
for all n ∈ N and u ∈ [0, 1 n+1 ), where τ n = n m=1 1 m . Let (F t ) t≥0 be the natural associated filtration. The following technical lemma is needed. We only provide an outline of the proof because we follow exactly the lines in Benaïm [3, Proposition 4.1] along with the explicit computations provided in the proof of Schreiber [START_REF] Schreiber | Urn models, replicator processes, and random genetic drift[END_REF]Theorem 2.6]. Lemma 5.12. For all T > 0 and δ > 0,

P sup u≥t sup 0≤h≤T Y (u + h) -φ h (Y (u)) ≥ δ | F t ≤ C(δ, T ) exp(ct) ,
for some positive constants c and C(δ, T ) when t ≥ 0 is large enough.

Outline of the proof. Roughly speaking, the process (APD) can be written as

(x n+1 , λ n+1 ) -(x n , λ n ) = 1 n + 1 Ψ(x n , λ n ) + ǫn+1 + b n+1 , where (ǫ n ) n is almost surely bounded, E(ǫ n+1 | F n ) = 0 and b n = O(1/n).
Y (u + h) -φ h (Y (u)) ≤ C(T ) 1 m(u) + A(u, T ) ,
for u sufficiently large, where

A(u, T ) = sup 0≤h≤T m(u+h)-1 l=m(u) ǫ l+1 + b l+1 l + 1 .
To conclude, it is enough to follow word by word, in this simpler case, the lines in the proof of Schreiber [START_REF] Schreiber | Urn models, replicator processes, and random genetic drift[END_REF]Theorem 2.6].

Proof of Proposition 5.11. In view of Proposition 5.8 and Lemmas 5.10 and 5.12 the result follows directly from Benaïm [3, Theorem 7.3].

Remark 5.13. Notice that for Lemma 5.10 and for the first part of the statement in Proposition 5.11, we have only assumed the condition (A) on the decision rule σ. Furthermore, from Benaïm [3, Theorem 7.3], we have the following estimate for the probability of convergence to an attractor A. If the set U ⊆ X × ∆ is such that U ⊆ B(A), then there exists numbers T, δ > 0, depending on U so that

P(L(x n , λ n ) ⊆ A) ≥ 1 - C(δ, T ) exp(ct) P(∃ u ≥ t, Y (u) ∈ U ),
for all t > 0, where the constants C(δ, T ) and c are given by Lemma 5.12.

A traffic game

The (almost sure or with positive probability) convergence to attractors results obtained when the Logit decision rule is considered are valid under the strong assumption 2ηα < 2. In fact, this condition becomes very difficult to verify as the number of players increases. Moreover, nonconvergence can occur for some games (see Section 5.3 for details) if the parameter ηα is large. In this part, we will discuss the interesting application developed in Cominetti et al. [9, Section 3] and we will show that a result in the spirit of Proposition 5.11 can be obtained under a much weaker condition.

Consider a network with a topology that consists on a set of parallel routes. Each route r ∈ R in the network is characterized by an increasing sequence of values c r 1 ≤ • • • ≤ c r N where c r u represents the average travel time when r carries a load of u users.

The traffic game is defined as follows. The strategy set is common for all players, i.e., S i = R, for every i ∈ A with R the set of available routes. The payoff to each player i, when the strategy profile r ∈ R N is played (i.e., when the network is loaded by the configuration r), is given by the value -c r i u = G i (r), that is, minus her travel time. This traffic game is shown to be a potential game in the sense that there exists a function Λ :

[0, 1] N ×|R| → R such that ∂Λ ∂λ is (λ) = G i (s, λ -i
), for every λ ∈ ∆. Explicitly, the function Λ is given by

Λ(π) = -E π r∈R U r u=1 c r u , (5.10)
where the expectation is taken with respect to the random variables U r = i∈A X ir with X ir independent Bernouilli variables such that P(X ir = 1) = π ir . It is also shown that the second derivatives of Λ are zero except for

∂ 2 Λ ∂π jr ∂π ir (π) = E π c r U r ij +1 -c r U r ij +2 ∈ [-η, 0], (5.11)
i = j, where U r ij = k =i,j X kr . Recall that we are assuming that player use the Logit decision rule in the learning process (APD). We also suppose that the smoothing parameters are identical for all players, i.e., β i = β for every i ∈ A. Notice that, in this framework, the value η (defined in (5.3)) translates to

η = max{η r u ; r ∈ R, 2 ≤ u ≤ N } = max{c r u -c r u-1 ; r ∈ R, 2 ≤ u ≤ N }. (5.12)
Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF] obtain the following (among others) result. Recall that α = max i∈A j =i β j = (N -1)β.

Proposition 5.14. The following hold (i) if 2ηα < 4, the function F is contracting for the infinity norm and the process (4.4) converges almost surely to the unique rest point of (

) has a unique rest point x * ∈ X which is symmetric in the sense that x * = (x, . . . , x). Furthermore, {x * } is an attractor for (4.6).

Notice that the first part in the proposition above can be recovered for the process (APD) since Proposition 5.2 applies. The second part provides a much weaker condition to have existence and uniqueness of a rest point of (4.6) (or, equivalently, a Nash equilibrium of the perturbed game defined in Lemma 5.1). Observe also that, despite the fact that the second part gives the existence of an attractor, no convergence result is obtained for the discrete process (4.4). The next result show that, under the assumption ηβ < 1, something more can be said for (APD).

Proposition 5.15. If ηβ < 1, (4.3) has a unique rest point (x * , λ * ) ∈ X × ∆ which is symmetric in the sense that x * = (x, . . . , x) and λ * = ( λ, . . . , λ) = σ(x * ). Furthermore, {(x * , λ * )} is an attractor for (4.3) and P((

x n , λ n ) → (x * , λ * )) > 0.
Proof. The existence and uniqueness of the symmetric rest point of (4. Proof. Recall that the matrix J β = ∇ x Ψ x (x * , λ * ) is the upper-left block of the matrix ∇Ψ(x * , λ * ) (see (5.5)). Observe that, from the definition of the function Ψ x , the fact that σ i depends only on

x i and (5.10), the entries of J β are given by

J β is,jr = ∂Ψ is x ∂x jr (x * , λ * ) = ∂ ∂x jr ∂Λ ∂π is (σ(x)) (x * ) -1 {is=jr} = k∈A r ′ ∈R ∂ 2 Λ ∂π kr ′ ∂π is (λ * ) ∂σ kr ′ ∂x jr (x * ) -1 {is=jr} = r ′ ∈R ∂ 2 Λ ∂π jr ′ ∂π is (λ * ) ∂σ jr ′ ∂x jr (x * ) -1 {is=jr} = ∂ 2 Λ ∂π jr ∂π ir (λ * ) ∂σ jr ∂x jr (x * )1 {s=r,i =j} -1 {is=jr} = βλ jr * (1 -λ jr * )E λ * c r U r ij +1 -c r U r ij +2 1 {s=r,i =j} -1 {is=jr} . (5.13)
Since λ * is symmetric (λ ir = λ jr , for all i, j ∈ A), J β is a symmetric matrix. Let us show that J β is negative definite by modifying the trick used in Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF]Proposition 12]. Take h ∈ R N |R| \{0}, then, from (5.13),

h T J β h = r∈R β i =j h ir λ ir * (1 -λ ir * )h jr λ jr * (1 -λ jr * )E λ * c r U r ij +1 -c r U r ij +2 - i (h ir ) 2 .
For every i ∈ A and r ∈ R, put v ir = h ir 1-λ ir * λ ir * , Z ir = v ir X ir and set η r 0 = η r 1 = 0. Therefore,

h T J β h = r∈R β i =j v ir v jr λ ir * λ jr * E λ * c r U r ij +1 -c r U r ij +2 - i λ ir * (v ir ) 2 1 -λ ir * = r∈R E λ * β i =j Z ir Z jr (c r U r -1 -c r U r - i (Z ir ) 2 1 -λ ir * ≤ r∈R E λ * -η r U r β i =j Z ir Z jr - i (Z ir ) 2 = r∈R E λ * -η r U r β i Z ir 2 + (η r U r β -1) i (Z ir ) 2 < 0,
where the last inequality follows by observing that η r U r ≤ η.

Remark 5.17. In fact, part (ii) in Proposition 5.14 holds true if ηβ < 2. The authors provide an explicit (local) Lyapunov function which does not seem suitable in our case.

Nonconvergence

In order to give an idea of the behavior of the stochastic process defined by (APD) when the parameter β (we assume β i = β for all i ∈ A) becomes large, we provide a small class of games which underlines the relevance of the hypotheses considered throughout this document. Consider a 2-player symmetric game, i.e., the strategy set S = S 1 = S 2 is common for and the payoffs verify that G 1 = (G 2 ) T . Let us assume that G 1 has constant-sum by row, this is, r G 1 (s, r) = k ∈ R for every s ∈ S. It is easy to check that for this kind of games there exists a rest point of (4.3) which has the form (x, σ(x)) ∈ X × ∆ such that x i = (1/k, . . . , 1/k) for i ∈ {1, 2}. We also assume that s G 1 (s, s) = k. A game that satisfies the precedent conditions is the good (resp. bad) Rock-Scissors-Paper game

  0 a -b -b 0 a a -b 0   ,
where 0 < b < a (resp. 0 < a < b) or the game (5.7).

The (strong) hypotheses above ensure that at least one rest point of (4.3) does not depend on the parameter β. In the following we will easily show that if the parameter β is sufficiently large then the rest point (x, σ(x)) becomes linearly unstable. Later, we will prove that this implies that P((x n , λ n ) → (x, σ(x))) = 0.

Lemma 5.18. If the parameter β > 0 is sufficiently large, then there exists an eigenvalue µ of the matrix ∇Ψ(x, σ(x)) such that Re(µ) > 0.

Proof. Again, let J β = ∇ x Ψ x (x, σ(x)) be the upper-left block of the Jacobian matrix of the function Ψ, which is the only relevant part, evaluated at (x, σ(x)). The precise expression for the entries of

J β is J β is,jr = ∂Ψ is x ∂x jr (x, σ(x)) =        -1, if i = j and s = r 0, if i = j and s = r β 1 |S| G i (s, r) -k |S| ,
otherwise, i, j ∈ {1, 2}. Thus the matrix J β has the form

-I J β J β -I , with J β ∈ R |S| × R |S| .
Observe that we can decompose J β as J β = βJ -I, where

J = 0 J J 0 .
Let µ 1 , . . . , µ |S| ∈ C be the eigenvalues of J (counting multiplicity). Since we have assumed that s G 1 (s, s) = k, the trace of J is not zero. So that, there exists some eigenvalue µ k , k ∈ {1, . . . |S|}, with nonzero real part. We have that, if v is an eigenvector associated to µ k , then µ k is an eigenvalue of J with corresponding eigenvector u

= (v, v) ∈ R |S| × R |S| since Ju = 0 J J 0 v v = Jv Jv = µ k u.
If Re(µ k ) > 0, the proof is finished. If Re(µ l ) ≤ 0 for all l ∈ {1, . . . |S|} then l Re(µ l ) < 0. Also, the trace of J is zero and therefore there exists µ eigenvalue of J (which is not an eigenvalue of J) such that Re(µ) > 0.

Finally, observe that det (βJ -µI) = 1

β |S| det J - µ β I , (5.14)
and it is straightforward from (5.14) that µ is an eigenvalue of the matrix J β if µ = (1 + µ)/β is an eigenvalue of J. Then µ = βµ -1 whose real part is strictly positive for a sufficiently large β.

Proposition 5.19. There exists β > 0 large enough and at least one rest point (x, σ(x)) ∈ X × ∆ of (4.3) such that, P((x n , λ n ) → (x, σ(x))) = 0.

Proof. We can directly apply Brandière and Duflo [6, Theorem 1]. The hypotheses of the theorem concerning the continuous dynamics and the step-size of the discrete process (APD) are immediately satisfied. The only condition that deserves attention is the one referred to the excitation of the noise on a repulsive direction at (x, σ(x)). Explicitly, it is sufficient to prove that

lim inf n→+∞ E(||ǫ pr n+1 || 2 | F n ) > 0 a.s. on the event Γ x, σ(x) = {(x n , λ n ) → (x, σ(x))}, (5.15)
since the noise term ǫ n = (U n , M n ) is almost surely bounded. Here the upper-script pr stands for the projection onto the repulsive subspace spanned by the eigenvectors associated to the eigenvalues with positive real part.

Fix i ∈ {1, 2}, take β large to have an eigenvalue µ of ∇Ψ(x, σ(x)) such that Re(µ) > 0 and let v a correspondent (eventually generalized) eigenvector. The vector v has the form v = (v 1 , v 2 ). Notice that necessarily v 2 = 0 since, if v 2 = 0, then v 1 is a vector of ones, which is indeed an eigenvector for the upper-left block of ∇Ψ(x, σ(x)) having -1 as the associated eigenvalue. So that

E(||ε pr n+1 || 2 | F n ) ≥ E( ε n+1 , v v 2 | F n ) ≥ E( r (v jr 2 M jr n+1 ) 2 | F n ) ≥ cE((M jr n+1 ) 2 | F n ),
with j = -i and for some r ∈ S and c > 0.

In view of (4.2),

E((M jr n+1 ) 2 | F n ) = E((1 {s j n+1 =r} -σ jr (x j n )) 2 | F n ) + O 1 n = σ jr (x j n )(1 -σ jr (x j n )) + O 1 n .
Finally, take the lim inf n in the previous expression on the event Γ(x, σ(x)) to conclude that (5.15) holds, since σ is is bounded away from zero for every i ∈ {1, 2} and s ∈ S.

Remark 5.20. For the game (5.7), if β > 3/2, then ρ(∇Ψ(x, σ(x))) > 0. Compare with Propositions 5.2 and 5.11.

As observed by Pemantle [START_REF] Pemantle | Nonconvergence to unstable points in urn models and stochastic approximations[END_REF], the nonconvergence results like the previous proposition are not very interesting if the set of unstable points is too large. Particularly, the most useful consequences can be stated when this set is finite. This is the case of our example (5.3) and, moreover, it is easy to check that (x, σ(x)) is the unique rest point of (4.3) for all β > 0. The previous result shows that for a large β, (x, σ(x)) has probability zero to be the limit of the process while for small β it is almost surely the limit. Simulations suggest that there is a cycle that attracts the trajectories and that the empirical frequencies of play still converge to σ(x). Figure 2 shows the behavior of the procedure (specifically the evolution of the mixed action σ 1 n of player 1) when β is large.

However, it does not seem plausible to pursuit a result like Proposition 5.19 on a general class of games. For instance, consider the 2-player zero-sum game defined by the payoff

G = 0 -1 1 0 . (5.16) Let (x * , σ(x * )), with σ 1 (x 1 * ) = σ 2 (x 2 * ) = (1/(1+e β
), e β /(1+e β )) and x 1 * = x 2 * = (-e β /(1+e β ), 1/(1+ e β )), be the unique rest point of (4.3). In this case, every eigenvalue of ∇Ψ(x * , σ(x * )) is equal to -1. Then P((x n , λ n ) → (x * , σ(x * ))) > 0 for all β > 0 due to Proposition 5.11.

Random environment

Our aim in this section is to consider the case where players receive, at each stage, a perturbed version of their payoffs. The general result given by Theorem 2.2 allows to add some perturbation to the process (APD) maintaining unaltered the results presented in this work. For example, we can consider that each player i ∈ A get a payoff g i n = g i n + ε i n at stage n, where (ε i n ) n is a martingale difference process bounded in L 2 or a vanishing random variable (see Remark 2.3). In this section, we are interested in a different kind of perturbation.

For the sequel, the model runs analogously as before. We only add that, at each time n ∈ N, each player i ∈ A receives a random payoff g i n = G i (s n , w n ) where the sequence (w n ) n is a controlled (by the parameter λ ∈ ∆) Markov chain with finite state space W , i.e., there exists a family of transition matrices (P (λ)) λ∈∆ where P(w n+1 = w | F n ) = P (wn,w) (λ n ), Proposition 6.2. The process (APDM) converges almost surely to an ICT set of the continuous dynamics Fix i ∈ {1, . . . , N } and (x, λ) ∈ X × ∆. Let us define the matrices H i (x, λ) and W(x, λ) by

         ẋis t = σ is (x i t ) λ is t G i (s, σ -i (x t ), τ (λ)) -x is t = Ψ is x (x, λ), λis t = σ is (x i t ) -λ is t = Ψ is λ (x, λ).
H i (a,b) (x, λ) = G i (s, w) -x is i , if s i = r i , 0, otherwise, (6.4)
and W (a,b) (x, λ) = τ b (x, λ), (

for every a = (s, w), b = (r, w ′ ) ∈ S × W and τ b (x, λ) given by equation (6.1). Notice that, for every s ∈ S i , a n+1 = (s n+1 , w n+1 ) and b n+1 = (s, s -i n+1 ), w n+1 , the following equality holds H i (a n+1 ,b n+1 ) (x n , λ n ) = G i (s, s -i n+1 , w n+1 )x is n 1 {s=s i n+1 } , and W(x n , λ n ))H i (x n , λ n ) (a n+1 ,b n+1 ) = a=(r,w) τ a (x n , λ n ) G i (r, w) - Proposition 6.4. Under the Logit decision rule (5.1), let η w be the maximal unilateral deviation that a player can face for a fixed w ∈ W (see (5.3)). Set η = max w η w and η = max i,s,w,w ′ |G i (s, w)-G i (s, w ′ )|. If 2ηα + η |W |k < 1, 2 max i β i < 1, (6.9)

x ir i n 1 {s=r i } = σ is (x i n ) w τ w (λ n )G i (s, σ -i (x n ), w) -x is n = σ is (x i n ) G i (s, σ -i (x n ), τ (λ n )) -x is n , so that (I -W(x n , λ n ))H i (x n , λ n ) (a n+1 ,b n+1 ) = U
where k is the • ∞ -Lipschitz constant for the function τ , then the discrete process (APDM) converges almost surely to the global attractor {(x * , λ * )} for the dynamics (6.3).

Proof. It is not difficult to see that under condition (6.9) there exists a unique rest point (x * , λ * ) ∈ X × ∆ of (6.3). Consider the function V defined by V (x, λ) = max{ xx * ∞ , λλ * ∞ }. Now if V (x t , λ t ) = λ tλ * ∞ ≥ x tx * ∞ then V (x t , λ t ) ≤ -KV (x t , λ t ) for some K ≥ 0, using exactly the same computations as in Proposition 4.5,the fact that 2 max i β i < 1 and that σ is (x)σ is (y) ∞ ≤ 2β i xy ∞ for all i ∈ A and s ∈ S i (see e.g., Cominetti et al. [9, Proposition 5]). On the other hand, if V (x t , λ t ) = x tx * ∞ ≥ λλ * ∞ , assume that the maximum is attained on the is coordinate, that x is ≥ x is * and define F is (x, τ ) = G i (s, σ -i (x), τ ). So that

d dt (x is t -x is * ) = σ is (x i t ) λ is t x is * -x is t + F is (x t , τ (λ t )) -F is (x * , τ (λ t ))+ + F is (x * , τ (λ t )) -F is (x * , τ (λ * )) ≤ σ is (x i t ) λ is t -x t -x * ∞ + 2ηα x t -x * ∞ + η τ (λ t ) -τ (λ * ) 1 ≤ -ξ 1 -2ηα -η |W |k V (x t , λ t ),
for some ξ > 0 such that σ is (x) ≥ ξ for every i ∈ A and s ∈ S i . Notice that we have used the fact that, for every w ′ ∈ W , F is (x * , τ (λ t )) -F is (x * , τ (λ * )) = w∈W (τ w (λ t )τ w (λ * ))(F is (x * , w) -F is (x * , w ′ )),

≤ η τ (λ t ) -τ (λ * ) 1 ≤ η |W | τ (λ t ) -τ (λ * ) ∞ ≤ η |W |k λ t -λ * ∞ .
Again, if x is tx is * < 0, the computations are the same. Then, V is a strict Lyapunov function.

The constant case

We restrict our attention to the constant case, i.e., the function P is such that P (λ) ≡ P * and consequently τ (λ) ≡ τ * where τ * is the unique invariant measure of P * . Therefore the condition to ensure convergence in Proposition 6.4 reduces to 2ηα < 1 (by considering the same Lyapunov function as in Proposition 4.5).

Notice that, in this case, ∇ x Ψ x (x * , λ * ) is an average (by τ * ) of the Jacobian matrices ∇ x Ψ(x * , λ * , w), where

Ψ is x (x, λ, w) = σ is (x i ) λ is G i (x, σ -i (x), w) -x is ,

Theorem 2 . 2 .

 22 Consider the discrete process (2.1). Assume that H is a Lipschitz function and that (a) the sequence (γ n ) is deterministic, γ n ≥ 0, n γ n = +∞ and γ n → 0, (b) sup n∈N z n < +∞, and (c) for any T > 0 lim n→+∞ sup k-1 i=n

Proposition 4 . 4 .

 44 The process (APD) converges almost surely to an ICT set for the continuous dynamics (4.3).

Remark 5 . 4 .

 54 Notice that 1/2 = N/ k |S k | if and only if |S k | = 2 for all k ∈ A.

Proposition 5 . 8 .

 58 Assume that 1 ≤ 2ηα < 2. Then, there exists a unique rest point (x * , λ * ) for the dynamics (4.3) which is an attractor.Proof. Let (x * , λ * ) ∈ Y. If 1 ≤ 2ηα < 2,equation (5.6) shows that the matrix ∇Ψ(x * , λ * ) is stable. To prove that {(x * , λ * )} is an attractor, take V (x, λ) = ((x, λ) -(x * , λ * )) T D((x, λ) -(x * , λ * )) as a (local) Lyapunov function where, for instance, D is the positive definite solution of the Lyapunov equation ∇Ψ(x * , λ * ) T D + D∇Ψ(x * , λ * ) = -I.

σ 1 Figure 2 :

 12 Figure 2: The mixed action σ 1 n of Player 1 when β = 4.

(6. 3 )

 3 In the sequel, our analysis will rely on the ideas in the proof of Benaïm [2, Proposition 3.3] (which are indeed a reduction to the finite state space case of the general framework developed in Benveniste et al. [4, Part II]) to show that hypothesis (c) of Theorem 2.2 holds (since assumptions (a) and (b) are immediately satisfied).

Lemma 6 . 3 .. 7 )

 637 There exists a C 1 function Q i (x, λ) such that(I -P (x, λ))Q i (x, λ) = (I -W(x, λ))H i (x, λ). (6Outline of the proof. The required function is given byQ i (x, λ) = E(x, λ)H i (x, λ) where E(x, λ) = +∞ 0 (E t (x, λ) -W(x, λ))dt,with E t (x, λ) being the matrix solution of the linear differential equationd dt E i t (y) = -(I -P (y))E i t (y), E i 0 (y) =I. See Benaïm [2,Lemma 5.1] (and the previous discussion therein) for further details.

  3) follows from Remark 4.1 and Proposition 5.14. Lemma 5.16 below shows that the matrix ∇Ψ(x * , λ * ) is stable. Hence, {(x * , λ * )} is an attractor for (4.3) and Proposition 5.11 applies. Lemma 5.16. If ηβ < 1, then the matrix ∇Ψ(x * , λ * ) is stable.

Acknowledgements

This article was written during the course of my PhD thesis. I would like to thank my advisor Sylvain Sorin for presenting this problem to me and also Michel Benaïm, Roberto Cominetti, and Mathieu Faure for very helpful discussions and comments.

for w ∈ W with λ n determined by the learning process and F n being the σ-algebra generated by the history (s 1 , g 1 , w 1 , . . . , s n , g n , w n ) up to time n. We assume the following.

(A1) For any λ ∈ ∆ the Markov chain with transition matrix P (λ) has a unique invariant probability τ (λ) ∈ ∆ W , where ∆ W denotes the set of probabilities over W . Remark 6.1. The hypothesis above imply that the function τ is also of class C 1 (see Benaïm [START_REF] Benaïm | Vertex-reinforced random walks and a conjecture of Pemantle[END_REF]Lemma 3.2]).

Observe that the unique recurrent class of the associated Markov chain may be periodic. Note also that the process (s n , w n ) n is also a controlled (by the parameter (x, λ) ∈ X × ∆) Markov chain with state space S × W . The independence hypothesis implies that for a given (x, λ) the associated transition matrix is given by

for each (a, b) = (s, w), (r, w ′ ) ∈ (S × W ) 2 . From (A1), the Markov chain with transition matrix P (x, λ) has a unique invariant probability τ (x, λ), where

for a = (s, w) ∈ S × W .

Let us now state precisely the corresponding discrete process in this framework. We conserve the notation and the hypotheses (A) over the decision rule of players σ. For each player i ∈ A, we define the new payoff function G i : S × W → R and its multilinear extension to ∆ × ∆ W as usual.

Therefore the updating rule is this case is given by

As before, we can conveniently recast the process (APM) as

where

and b n = O( 1 n ). Observe that the process (U n ) n is not a martingale difference sequence. The next result shows that the analogous to Proposition 4.5 holds.

Proof of Proposition 6.2. To prove that the third assumption in the statement of Theorem 2.2 is satisfied almost surely, we have to show that the noise term (ǫ

as n → +∞, for every T > 0. Since (M n ) n is an almost surely bounded martingale difference process plus a vanishing term, it is sufficient to show that (6.8) holds for (U n ) n . For a matrix B (of appropriate dimension) and a fixed s ∈ S i , let us set by B[n] the operation that consists on taking the (a n , b n ) entry of B, where a n = (s n , w n ) and b n = (s, s -i n ), w n . Now, according to (6.6) and Lemma 6.3, we have, for every n ≥ 1,

where

l=n u is l+1 (3) ≤ C/n since the functions P , Q i , and the process (λ n ) n are bounded (for a generic positive constant C). We also have that

which implies that (6.8) holds.

Once we have the connection between the discrete process (APDM) and the continuous dynamics (6.3), the task of finding explicit almost sure convergence results becomes more difficult because of the general form of the function P defined in (A2). However, it is possible to state an analog of Proposition 4.5 in the Logit decision rule case by strengthening the conditions over the parameters β i and assuming that the variation of payoffs is small. Recall that α = max i∈A j =i β j .

for every w ∈ W . Then the estimate given by (5.4) can be obtained exactly in the same manner than in Lemma 5.3 for the function Ψ if 2ηα < 1. Hence, as in the deterministic environment case, the matrix ∇Ψ(x, λ) is stable for every rest point (x, λ) of (6.3) if 1 ≤ 2ηα < 2 and Proposition 5.11 can also be recovered in this framework. Let Y be the set of rest points of the dynamics (6.3). Proposition 6.5. If an attractor A for the dynamics (6.3) verifies that B(A) ∩ Y = ∅, then P(L(x n , λ n ) ⊆ A) > 0. In particular, under the Logit decision rule decision (5.1), if 1 ≤ 2ηα < 2, then the set Y reduces to one point (x * , λ * ) and P((x n , λ n ) → (x * , λ * )) > 0.

Proof. We only have to check that the conclusion of Lemma 5.10 (regarding the attainability points of the process (APDM)) is satisfied in this case, since the remaining assumptions to apply [3, Theorem 7.3] hold just as before. For the sake of simplicity, let us suppose that τ * w is rational for all w ∈ W . Let (x, λ) be such that x is = G i (s, λ -i , τ * ) for all i ∈ A and s ∈ S i . Take m ∈ N large such that, for every w ∈ W , mτ * w ∈ N. Then, for a fixed w, repeat the block-argument in the proof of Lemma 5.10 to construct a w-block of play. Then consider the block of play that consists on playing mτ * w -times each w-block, for each w. This sequence generated by (APDM) carries the process (x n , λ n ) n close to (x, λ). Remark 6.6. In fact, without the constantness assumption, we have shown that for every (x, λ) ∈ X × ∆ such that x is = G i (s, σ -i (x), τ (λ)) for all i ∈ A and s ∈ S i , the point (x, λ) is attainable by (APDM). Hence, in particular, any rest point of (6.3) is attainable and the first part in the statement of Proposition 6.5 holds only under condition (A) on the decision rule σ.


Antoine Seguin

Yann Bertho

Philippe Gondret

Jérôme Crassous

Sphere penetration

Keywords: 45, 70, -n -Granular systems 45, 50, -j -Dynamics and kinematics of a particle and system of particles 96, 15, Qr -Impact phenomena

come

Introduction. -A better knowledge of the impact of a solid object into a granular target has many applied interests from both geologist and ballistic point of view [START_REF] Melosh | Impact cratering: a geologic process[END_REF][START_REF]High velocity impact dynamics[END_REF]. Since a few years, numerous studies have been carried out by physicists interested in the ejection process [START_REF] Thoroddsen | [END_REF][4][5][6][7][8], the crater morphology [9][10][11][12] and the penetration dynamics [4,[13][14][15][16][17][START_REF] Tsimring | Proceedings of Powders and Grains[END_REF][START_REF] Goldman | [END_REF][20], searching for scaling laws for the crater size [9][10][11][12] and penetration depth [13][14][15][16][17][START_REF] Tsimring | Proceedings of Powders and Grains[END_REF][START_REF] Goldman | [END_REF][20][21][22][23]. For the ejection process, a spectacular thin granular jet raising very high can be observed after the impact on small grains of rather low packing fraction [START_REF] Thoroddsen | [END_REF][4][5][6][7] whereas an opening granular corona is seen for larger grains of rather high packing fraction [8]: the effect of air is crucial in the former case [5,6] whereas it is negligible in the latter one. For the crater morphology, the scaling laws found for high energy impacts of planetary interest [START_REF] Melosh | Impact cratering: a geologic process[END_REF] stand for low energy impacts of small scale laboratory experiments [9][10][11][12], indicating some universal physical processes involved in the crater formation. For the penetration dynamics, the observed deceleration of the impacting sphere towards its final stop is usually explained by a complex drag force resulting from frictional and collisional processes and involving several terms: a linear depth dependent term [17] arising from solid friction and velocity-dependent terms of linear or quadratic form arising from the ballistic [14,17,[START_REF] Tsimring | Proceedings of Powders and Grains[END_REF] or the fluid mechanics point of view [21]. Such different force terms are not easy to extract from the sphere trajectory usu-ally tracked by video means [13][14][15][16][17], but recently direct force measurements with an accelerometer inside the impacting sphere [START_REF] Goldman | [END_REF] reveal that a force proportional to the velocity squared is indeed experienced by the impacting sphere at least during its first penetration stage at high velocity and shallow depth. The stopping time of the sphere has been studied in different experimental works and displays a striking and rather counter-intuitive behaviour: it is a decreasing function of the impact velocity with an asymptotic plateau for large enough impact velocities [13,17,[START_REF] Goldman | [END_REF]. The characteristic time scaling for the plateau value was proposed to be τ = (d/g) 1/2 [13,17] or τ = (ρ/ρ g ) 1/4 (d/g) 1/2 [START_REF] Goldman | [END_REF] for a velocity larger than the typical characteristic velocity V = (gd) 1/2 [17,[START_REF] Goldman | [END_REF], where ρ g is the density of the grains, d and ρ are the diameter and the density of the sphere. The observed scaling law for the final penetration depth δ that may be written as δ/d ∝ (ρ/ρ g ) β (H/d) α , where H is the total falling distance covered from release to rest, is not yet satisfactorily explained, as well as the values of the two power exponents α and β found to be around 1/2 in experimental or numerical works [10,14,[START_REF] Tsimring | Proceedings of Powders and Grains[END_REF][20][21][22]. Experiments are essentially 3D (except the real 2D experiment of Ciamarra et al. [13]) whereas the numerical simulations are 2D with similar values for the power exponents. The existence of a finite penetration depth δ is always referred to the existence of a non-zero solid friction µ in contrast to the case of simple fluids where the sphere would not stop but reach a limit velocity in the absence of solid friction. The µ dependence of δ was proposed to be δ ∝ µ -1 [10] (the penetration depth would thus be no more finite for zero solid friction) from experimental investigation varying the grain material. But experimentally, it is hard to change the coefficient of solid friction in a large range and without changing other crucial parameters such as the coefficient of restitution and the solid fraction.

In the present paper, we show by numerical simulations that no microscopic solid friction is necessary to explain a finite penetration depth for a sphere impacting on granular matter. Furthermore, we show that the scaling law δ/d ∝ (ρ/ρ g ) β (H/d) α observed experimentally or numerically with non-zero microscopic solid friction still stands in the zero microscopic solid friction limit. We also recover that the stopping time t s is constant at large enough impact velocities and show that it scales as t s ≃ τ = (ρd/ρ g g) 1/2 for impact velocities larger that the typical characteristic velocity V = (ρgd/ρ g ) 1/2 . These scalings clarify the previous scalings discussed above. The numerical results will be shown and discussed after having presented the 2D numerical method used in the present paper.

Numerical method. -We use the method of molecular dynamics to perform two-dimensional simulations in the geometry shown in the inset of fig. 1. The granular target is prepared by the sedimentation of an initial dilute configuration under the action of the gravity acceleration g = 9.8 m s -2 . The grains are modeled as a random packing of spheres of mean diameter d g , mass m g and density ρ g contained in a rectangular box bounded by hard walls. In order to avoid any crystallization of the packing, a slight dispersion in the grain diameter is introduced, with an uni-form distribution in the range 0.8d g to 1.2d g . Before the impact, the packing fraction in the granular medium is φ ≃ 0.83. The projectile is a sphere of diameter d, mass m and density ρ which is dropped onto the granular packing. The projectile is thrown downwards at the velocity required, and its value at impact will be noted v i . This equivalent to the usual experimental situation where the sphere is dropped from the height h and impacts the granular surface with the velocity v i = √ 2gh. Note that the box containing the granular medium is large enough (> 8d) so that the projectile is not affected by the surrounding walls and the layer of grains is high enough to avoid any bottom wall effects during the penetration [22]. The number of grains in the simulations ranges from 10 4 for small boxes to 10 5 for largest ones.

As the goal of this paper is to show that microscopic solid friction is not essential in explaining the finite penetration of a projectile into a granular material, we do not take into account any static nor dynamic friction between the grains. The interaction forces are thus taken as purely normal with no tangential components. The interaction force between two grains, or between one grain and the projectile or the bounded walls, is modeled as a dissipative Hertz law [24] such as

F n = -kξ 3/2 -γ dξ dt , (1)
where k is the non-linear stiffness, γ is a damping coefficient, and ξ and dξ/dt are respectively the interpenetration and the velocity of interpenetration of the grains. For two identical spherical grains of diameter d g , Young modulus E and Poisson coefficient ν, the non-linear stiffness k is given by k = 2E 2d g /3(1 -ν 2 ). The collision time for a non-dissipative contact (γ = 0) between two grains is

τ c ≈ 3.21 m eff k v -1/5 n , (2)
where v n is the relative normal velocity and m eff = m g /2 the effective mass for two identical colliding grains. The collision time is not very different in the case of a nonzero dissipation (γ = 0). The equations of motion for the grains are integrated using a standard second order Verlet algorithm. The choice for the numerical time step ∆t must be such that ∆t ≪ τ c in order to ensure numerical accuracy.

In the following, we present numerical simulations for a granular material composed of glass spheres (density ρ g = 2520 kg m -3 ) with an effective elastic modulus E * = E/(1-ν 2 ) = 69×10 9 Pa and of mean diameter d g = 1 mm (mass m g = 1.3 mg). The non-linear stiffness is thus k = 2 × 10 9 N m 3/2 and the collision time for a typical collision velocity v n = 1 m s -1 is τ c = 2.7 µs. The time step is chosen as ∆t = 0.1 µs ≪ τ c . For a non-zero damping coefficient γ, the coefficient of normal restitution for normal incidence e n = -v f n /v i n , which is the ratio of the relative normal velocity after an impact over the velocity before the impact, is smaller than the ideal limit value 1 for perfect elastic collisions. More precisely, with model eq. ( 1), e n decreases slowly with the collision velocity as (1 [24]. With the damping value γ = 0.065 kg s -1 the restitution coefficient is e n = 0.9 for v i n = 1 m s -1 . It should be stressed that the following results are qualitatively only weakly dependent on the damping factor value.

-e n ) ∝ (v i n ) -1/5
Numerical results and discussion. -Figure 1 displays the time evolution of the position z(t) of the projectile during its penetration through the grains, where z is the distance between the initial horizontal free surface of the granular medium and the bottom of the impacting sphere. The penetration increases with time up to a maximum depth δ at the time t s . Note that a small rise of the sphere, of typically a few percent of the total penetration, is observed at the end of most of the runs. We attribute this effect to the absence of microscopic static friction in the interaction law [eq. ( 1)]. Indeed, the grains ejected during the collision process are redeposited on the granular material and exert an increasing pressure on it, inducing a downwards motion of the granular material. This small effect was not reported in numerical simulations including microscopic solid friction [START_REF] Tsimring | Proceedings of Powders and Grains[END_REF]. In the following, we shall consider this maximum penetration δ as the final penetration depth and the corresponding time t s as the stopping time. Note that dropping the sphere from slightly different x-positions gives very similar z(t) even if the acceleration signals are quite different.

Penetration depth.

Figure 2 shows the evolution of the normalized penetration depth δ/d as a function of the normalized total falling distance H/d, where H = h + δ is the sum of the free-fall height h = v 2 i /2g and the depth. The diameter of the impacting sphere ranges from d = 20d g to 70d g , and its density is here kept constant and equalled to the grain density (ρ = ρ g ).

In the log-log plot of fig. 2, the data are aligned along a straight line of slope α = 0.31 ± 0.02 meaning that the penetration depth δ varies with H following a power law δ/d ∝ (H/d) α . The variation of the penetration depth with the density (i.e. with the mass) of the projectile is shown in fig. 3, where (δ/d)/(H/d) -α is plotted as a function of the density ratio ρ/ρ g between the projectile and the grains. The penetration depth is found to depend on ρ/ρ g with a power law of the form δ/d ∝ (ρ/ρ g ) β , with β = 0.74 ± 0.02. Finally, grouping the fall height and the mass dependencies, one obtains

δ d = A ρ ρ g β H d α , (3)
with A = 0.92 ± 0.02. This power law scaling for the penetration depth is observed in various experimental and numerical studies [10,14,[START_REF] Tsimring | Proceedings of Powders and Grains[END_REF][20][21][22]. The value of the exponent α ≃ 0.31 is close to the commonly reported values between 0.33 and 0.40, and the exponent β ≃ 0.74 characterizing the dependence with the density ratio is not far from the reported values ranging from 0.50 to 0.61. Thus, the impacting sphere stops at a finite depth without any microscopic friction and the scaling laws for the penetration depth are in agreement with those observed experimentally or numerically with friction.

Forces. Let us now examine the forces undergone by the sphere after the impact, to extract the main ingredients leading to its stop. The force exerted by the grains on the sphere depends mainly on the penetration depth z and on the velocity v of the projectile [17][START_REF] Tsimring | Proceedings of Powders and Grains[END_REF][START_REF] Goldman | [END_REF]. For dense packings, experimental results show that this resistance force may be separated into two independent functions of position F z (z) and velocity F v (v) so that the Newton law for the sphere motion can be written as F z is usually attributed to solid friction [4,17] and F v is considered of collisional or inertial origin [17][START_REF] Tsimring | Proceedings of Powders and Grains[END_REF][START_REF] Goldman | [END_REF].

dv dt = g - F z (z) m - F v (v) m . (4)
Figure 4 displays the reduced acceleration of the sphere as a function of its velocity at a given penetration depth (z = 30 mm) and suggests that the drag force F v is proportional to v 2 , in agreement with the expression mv 2 /d 1 proposed recently by Katsuragi and Durian [17], where d 1 is a characteristic dissipative length. Note that the reduced force is non-zero at vanishing velocity as there is still a non-zero depth dependent force term F z (z). This behavior is observed with different sphere diameters in the range 20 mm < d < 100 mm and different density ratio in the range 1 < ρ/ρ g < 10. Figure 5a shows that d 1 does not depend on depth of the projectile z and thus F v does not depend on z as found experimentally [17], which justify the writing of eq. ( 4). Figures 5b and5c show that d 1 is proportional both to the projectile diameter d and to the density ratio ρ/ρ g leading to d 1 ∝ ρd/ρ g . The velocity dependent force term F v (v) thus scales as F v /m ∝ ρ g v 2 /ρd indicating its inertial or collisional origin.

Plotting now in fig. 6a the force term at vanishing velocity v as a function of z shows that the simple dependence F z ∝ z proposed by Katsuragi and Durian [17] is compatible with our data despite the high scattering at low z (z d) where the sphere is not fully immersed in the granular medium. Figures 6b and6c show that F z /m is proportional to 1/d and ρ g /ρ. The depth dependent force term F z thus scales as F z (z)/m ∝ ρ g gz/ρd. This force term linear in z has been previously proposed and seen by various authors [17][START_REF] Tsimring | Proceedings of Powders and Grains[END_REF][START_REF] Goldman | [END_REF] with a solid friction origin, but the extracted coefficient of friction necessary to fit the data was far from the standard values [17]. Here, the F z (z) force term does not come from microscopic solid friction as there is no microscopic solid friction in our numerical simulations. The depth dependent term F z (z) can thus simply viewed as a hydrostatic term as already suggested in [25] for the experimental penetration of flat plates and in [4] for an impacting sphere in very loose sand. The pressure increases linearly with the depth as ρ g gz and so is the force F z on the sphere. This "hydrostatic" force term is not Archimedean as the penetrating sphere is never im- mersed in the granular packing before it stops as can be seen here numerically (see the inset snapshot of fig. 1) and experimentally [START_REF] Goldman | [END_REF]. It follows that the Newton's law for the projectile during its penetration may be written as

dv dt = g -a z ρ g g ρd z -a v ρ g v 2 ρd , (5)
where a z = 1 ± 0.1 and a v = 0.8 ± 0.1 are numerical prefactors.

Stopping time. Let us now focus on the stopping time. The inset of fig. 7 displays the stopping time t s of the projectile as a function of its impact velocity v i . Numerical data are observed to be very scattered depending on the velocity, diameter and density of the projectile. More precisely, t s decreases with the impact velocity v i for any given size and density of the projectile and increases with the projectile diameter d and with its density ratio ρ/ρ g . Two time scales can be extracted from the non-linear differential equation ( 5) by considering independently the two force terms. Considering only the depth dependent force term, the characteristic time τ z for the stopping time is

τ z = ρd ρ g g 1/2 , (6)
which is independent of the impact velocity. Considering now only the non-linear velocity dependent force term in eq. ( 5) leads to the characteristic time

τ v = ρd ρ g v i , (7)
which depends on the impact velocity v i . As both force terms play a non-negligible role in the penetration (the velocity dependent force term decreases from its maximal value at impact to zero at the stop whereas the depth dependent force term increases from zero at impact to its maximal value at the stop), the total stopping time t s (τ z , τ v ) is a combination of the two characteristic time scales τ z and τ v , and can thus be expressed as t s /τ z = f (τ z /τ v ). Note that the time scale ratio is τ z /τ v = v i (ρ g /ρgd) 1/2 , which corresponds also to the velocity ratio v i /V of the impact velocity v i to the characteristic velocity V = (ρgd/ρ g ) 1/2 . By using the characteristic time scale τ z and velocity scale V , i.e. by plotting t s /τ z as a function of v i /V , all the data collapse on the same master curve with two distinct parts (fig. 7): (i) for low enough impact velocities (v i /V 2), the stopping time decreases with increasing impact velocity; (ii) for large enough impact velocities (v i /V

2), a plateau is reached, so that the stopping time does not depend on the impact velocity and tends to the constant value t s /τ z ≃ 1.7. The existence of a single curve in the normalized plot t s /τ z versus v i /V , and the critical values v i /V ≃ 2 and t s /τ z ≃ 1.7 close to 1 indicate that the typical velocity scale V and time scale τ z are relevant physical parameters for the problem, which validate the two independent model forces acting on the penetrating sphere. The stopping time calculated by eq. ( 5) with a stop condition at v = 0 agrees with the simulation data to within 20% (fig. 7). The calculated penetration depth δ/d obtained by solving eq. ( 5) deviates from the data by as much as 50% since small errors in the force terms in the approximated model equation have a more important effect on the integrated position than on the stopping time.

t s / τ z v i / V
Conclusion. -By performing numerical simulations for an impacting sphere in a frictionless granular material, one obtains the same scaling law for the penetration depth as in simulations with solid friction or real experiments. This shows that dissipation by microscopic solid friction can be ignored and dissipation by collisions is sufficient to catch the penetration dynamics in granular matter. Analysing the forces reveals that besides a velocity squared force term from collisional origin, exists a depth dependent force term. This pressure increasing term with the depth is sufficient to stop the sphere, and steric hindrance with dissipation prevents the sphere from settling, by contrast to simple liquids. The scalings found for the two force terms allow for the prediction of the scaling of the stopping time which is indeed observed: a plateau value at high impact velocity and an increasing value at decreasing velocity. This scaling for the stopping time without any microscopic solid friction is also in agreement with what was observed previously. If microscopic solid friction appears needless to explain the scaling laws for both the final penetration depth and the stopping time of the projectile, it would certainly affect their precise value from a quantitative point of view.

Fig. 1 :

 1 Fig. 1: Time evolution of the penetration z of a sphere impacting the granular medium, where z = 0 corresponds to the initial surface of the grain piling. The projectile of diameter d = 30 dg = 30 mm and of density ρ = ρg = 2520 kg m -3 hits the grains at the velocity vi = 1 m s -1 . Inset: snapshot during penetration by impact.

Fig. 2 :

 2 Fig. 2: Normalized penetration depth δ/d of the sphere as a function of the normalized total falling distance H/d for different projectile diameters: d = 20dg (▽), d = 30dg (•), d = 40dg ( ) and d = 70dg (△). The sphere/grains density ratio is ρ/ρg = 1. (--) Power law fit δ/d ∝ (H/d) α , with α ≃ 0.31.

Fig. 3 :

 3 Fig. 3: (δ/d)(H/d) -α as a function of the sphere/grains density ratio ρ/ρg. (--) Power law fit (δ/d)(H/d) -α ∝ (ρ/ρg) β , with β ≃ 0.74.

Fig. 4 :

 4 Fig. 4: Reduced acceleration -dv/dt + g of the impacting sphere (diameter d = 20dg, density ρ = ρg) as a function of its velocity squared v 2 , at a specific depth: (•) z = 30 mm, ( ) z = 40 mm and (△) z = 50 mm. (--) Linear trends of the data by -dv/dt + g = Fz(z)/m + v 2 /d1, with d1 ≃ 36.4 mm.

Fig. 5 :

 5 Fig. 5: (a) Characteristic length d1 as a function of the depth z of the projectile. (--) Constant fit d1 = 36.4 mm. (b) Characteristic length d1 as a function of the diameter d of the projectile (density ρ = ρg) at a depth z = 20 mm. (--) Linear fit d1 = 1.3d. (c) Characteristic length d1/d as a function of the density ratio ρ/ρg at z = 30 mm for a projectile of diameter d = 20dg. (--) Linear fit d1/d = 1.2ρ/ρg.

Fig. 6 :

 6 Fig. 6: (a) Fz/m as a function of the depth z of the projectile (diameter d = 20dg, density ρ = ρg); (b) Fz/m as a function of the inverse of the diameter 1/d of the projectile (density ρ = ρg) at a depth z = 20 mm; (c) Fz/mg as a function of the inverse of the density ratio (ρ/ρg) -1 at z = 30 for a projectile of diameter d = 20dg. (--) Linear fits of numerical data.

Fig. 7 :

 7 Fig. 7: Normalized stopping time ts/τ as a function of the normalized impact velocity vi/V , for: ρ/ρg = 0.5 and ( ) d = 20 mm, ( ) d = 30 mm, (◭) d = 40 mm, (◮) d = 60 mm, (•) d = 80 mm, ( ) d = 100 mm; ρ/ρg = 1 and (▽) d = 20 mm, ( ) d = 30 mm, (⊳) d = 40 mm, (•) d = 70 mm; ρ/ρg = 1.5 and ( ) d = 30 mm; ρ/ρg = 2 and (⊲) d = 20 mm, (△) d = 30 mm; ρ/ρg = 3 and (⋄) d = 20 mm; ρ/ρg = 4 and (+) d = 30 mm; ρ/ρg = 6 and (×) d = 20 mm. (--) Guideline for the eyes. (-) Calculated stopping time from model eq. (5). Inset: stopping time ts as a function of the impact velocity vi for the same set of data.

The authors thank John Hinch and Marc Rabaud for fruitful discussions.