Antoine Salomon Large Bandit

Antoine Salomon

Large Bandit Games

Keywords: one-arm bandit, large games, deterministic equilibria, social learning

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

In this paper, we study situations where many agents deal with a dilemma between exploiting a known protable investment and experimenting others with unknown values. One-arm bandit model provides a good way to address this problem: each player faces a machine which he sequentially decides to (or not to) operate. This is equivalent to deciding which arm to operate when facing a machine with a safe arm (representing the exploitation option) and a risky arm (for the exploration option). When the risky arm is pulled, the player gets a payo from which he can learn about the protability of its machine, and when the safe arm is pulled he is rewarded by a payo of known value. Without loss of generality, we assume that the value of the safe arm is normalized to zero. Usually a machine is one of two types, say High and Low, that the player does not know and that is drawn randomly at the beginning of the game. This type may also be referred as the state of the nature. The expected value of the risky action is positive when the type is High, and negative when the type is Low. So the player has to choose if he stops experimentation, and when: not too early to have time to detect the High state and not too late to avoid costly bets. Gittings [START_REF] Gittins | Bandit processes and dynamic allocation indices[END_REF] was the rst to describe the optimal strategy in such a model (one may also look at Ferguson [START_REF] Ferguson | Optimal stopping and applications[END_REF] for a review). Models with a single player and a multi-armed bandit still spawns many publications (e.g. Brezzi and Lai [START_REF] Brezzi | Optimal learning and experimentation in bandit problems[END_REF]), most of it in a non-bayesian setting ( [START_REF] Lai | Asymptotically ecient adaptive allocation rules[END_REF], [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], [START_REF] Audibert | Exploration-exploitation tradeo using variance estimates in multi-armed bandits[END_REF], ...). In a multi-player game, the situation is trickier: a player may be able to watch others' decisions and/or payos, which is another way to get information when the types of the risky arms are correlated. This is the topic we are interested in, in particular when there is a large number of players.

First, let us briey describe some basic problems raised by the study of multi-player bandit games, and by games with many players. A major question is the social eciency of Nash equilibria, that is, the dierence between the expected gain of a player in a situation of strategic interaction and the expected gain of an isolated player (who only observes his own payos). This dierence is always positive, since a player can not suer from getting extra information from his neighbours, but the amount may depend on the level of cooperation between agents. Besides, an alternative way to study social eciency is to look at the dierence between the gain of a cooperative players (who fully cooperates to maximize the sum of their rewards) and the gain of the players in strategic interaction.

In this view, a popular subject is free-riding: some players may have an incentive to take advantage of other agents' experimentation without taking risks themselves (see Bolton and Harris [START_REF] Bolton | Strategic experimentation[END_REF] and Keller, Rady and Cripps [START_REF] Keller | Strategic experimentation with exponential bandits[END_REF]). This brings some intricacies in the description of equilibria, and it aects their social eciency. As we do not want to focus on free-riding we will assume that the decision to switch to a safe action is irreversible. Nevertheless, the fact that there are many players enables them to gather a better amount of information. As the number of players is growing, this may even asymptotically lead to a full learning of the state. Thus, the players would eventually all play the same action, which has proven to be the best. Consequently our subject is linked to herding , which is not restricted to bandit games (see Banarjee [START_REF] Banerjee | A simple model of herd behavior[END_REF] and Aoyagi [START_REF] Aoyagi | Mutual observability and the convergence of actions in a multi-person two-armed bandit model[END_REF]). In this case of asymptotic perfect learning, we can also wonder if it benets to a large proportion of players, and how fast the state is revealed. This issue was studied by C. Chamley and D. Gale [START_REF] Chamley | Information revelation and strategic delay in a model of investment[END_REF] in a model of investment. Among other parameters, they underlined the role of the cost of experimentation: the more expensive experimentation is expected to be, the more players are willing to take risks in order to shorten the learning period.

Our subject is the description of equilibria with a large number of players, and to discuss the possibility of asymptotic perfect learning. To avoid triviality, it is critical that players do not observe each others payos (or, at least, not a good piece of it). If not, by means of the law of large number and provided that the types of the machines are correlated enough, the state of the nature would be learned automatically after the rst stage thanks the massive amount of observed payos. Previous works are mostly based on models with a continuum of agents (see, e.g. Caplin and Leahy [START_REF] Caplin | Business as usual, market crashes, and wisdom after the fact[END_REF], Bergemann and Välimäki [START_REF] Bergemann | Market diusion with two-sided learning[END_REF], and Camargo [START_REF] Camargo | Learning in society[END_REF]). In these settings, an individual player can not reveal anything and only massive actions indicate relevant information. Each player gets a piece of information, which aects his decisions, so that the proportion of players who take a given option is a feature of the state of the nature. For instance, the equilibria considered in [START_REF] Caplin | Business as usual, market crashes, and wisdom after the fact[END_REF] are depicted as follows: at some point a proportion of agents is led to leave the market, and this reveals the state to the others. The interest for these models is justied in so far as a large number of players is expected to be asymptotically equivalent to a continuum setting. As an example, in Rosenberg, Solan and Vielle [START_REF] Rosenberg | Social Learning in OneArmed Bandit Problems[END_REF], the number of players is nite but when it gets large we also observe a revealing fraction of exit. Nevertheless, the equivalence is questionable. In [START_REF] Rosenberg | Social Learning in OneArmed Bandit Problems[END_REF], the model assumes that some payos make players so pessimistic after one stage that exiting becomes their dominant strategy. That is why, when the number of players gets large, a massive departure is observed. Without this assumption, players could be tempted to delay their exit or to leave far more scarcely, so that limit aggregate behaviour displays randomness and is not determined by the state of the nature. In a study that is related to our, P. Murto and J. Välimäki [START_REF] Murto | Learning in a Model of Exit[END_REF] study this randomness and the process of learning. They show that when the number of players is large and under certain circumstances (basically, when the cost of waiting is not too high), information aggregates smoothly by several random wave of exits. In their model, a player is either informed (i.e. he has received the positive signal that tells his that his state is High) or uninformed (i.e. he did not get the positive signal).

Our model is close to [START_REF] Rosenberg | Social Learning in OneArmed Bandit Problems[END_REF]: each of a large number of players operates in discrete time a one-arm bandit machine, they observe each others' actions but not each others' payos, so that the only way players can get information is from their own payos and from watching others' decisions. Except from one technical assumption, the distribution of payos is general, and learning is not monotonic as in [START_REF] Murto | Learning in a Model of Exit[END_REF]. The type of the machines are perfectly correlated: either they are all in the "High" state, either they are all "Low". This means that all the machine shares a common distribution of payo, the expectation of which is positive in the High state and negative in the Low state. Conditionally to the state, payos are drawn independently across players and across stages. Finally and as mentioned before, the decision to stop experimentation is irreversible.

Our claim is the existence of an alternative. For some asymptotic equilibria, players wait until a fraction of them gets too bad news and is forced to leave. Thus the state is revealed to the remaining players. This case is similar to models with a continuum of players, as the limit aggregate behaviour does not show uncertainty. This is also related to herding: except for the rst leaving players, all players will act the same. Their decisions are based on others' behaviours rather than on their private information, but this always leads to the best action anyway. We will call these equilibria Asymptotically Deterministic. We provide conditions for their existence, which are the inequalities that make sure that a non negligible part of the players exits at a given stage and that all other players are optimistic enough to wait for this revealing stage. In particular, these inequalities can be viewed as conditions for existence of equilibria in a similar model with a continuum of players. For all other asymptotic equilibria, the limit aggregate behaviour exhibits randomness. At some stage of the game, some of the most pessimistic players will leave but the number of exits is uncertain, as it is not fully determined by the type of the machines. This situation is due to the fact there are not enough players willing to reveal a good piece of their private information. Indeed, we will show that the average number of exits is bounded, with a bound which is independent of the number of players involved in the game. In particular, if the equilibrium is symmetric, the law of this number is asymptotically equivalent to a Poisson distribution. As a consequence, this limit case cannot be modelled by a continuum of players.

The paper is organized as follows. In the rst section, our model is described and the main results are presented. Then, we give the main leads of their proofs. The third section is devoted to the complete proofs.

1 Model and results

Model

Each of N players sequentially operates a one-arm bandit machine. They have to decide when to stop. The decision to stop is irreversible and yields a payo normalized to zero. At any stage n ≥ 1, each player i:

1. decides to drop out or to stay in, 2. observes own payo X i n , 3. observes who stayed in.

The machines have a common payo distribution, which can be one of two possible types: High or Low. This type is a random variable, denoted Θ, and stands for the state of the nature. Players are not informed of the value of Θ but they share a common prior p 0 , which is the probability of the state being High. We assume that, conditional on Θ, the payos (X i n ) n≥1,i∈{1,...,N } are i.i.d. θ (resp. θ) stands for the expected stage payo of a machine of type High (resp. Low) and is w.l.o.g. identied with this type. To avoid trivial cases, we assume that θ < 0 < θ. Players discount payos at a common rate δ ∈ (0, 1) so that the overall payo of player i is

τ i k=1 δ k-1 X i k
, where τ i is the last stage where player i decides to stay in (possibly +∞). Lastly, we denote by P θ the conditional probability given Θ = θ (θ ∈ {θ, θ}).

Remarks

• Payos are private information, but decisions are publicly observed. Thus, the only way a player can learn the state is thanks to his own payos on the one hand, and to others' players decisions on the other hand. If payos were publicly disclosed, the study of the large game (i.e. N → +∞) would be simple: there would be a full learning of the state after the rst stage.

• Except for one technical assumption which will be detailed below, there are no restrictions on the reward distributions. Thus, the model itself is not very restrictive. For example, it could be that some payos are not a good prot but are good news, i.e. they show that the state is likely to be High.

• The fact that all the machines are either all of type High, or all of type Low is an assumption of perfect positive correlation. It implies for example that good news for one player is good news for the others. This assumption is common to most of the publications in the eld, but some works investigate negative or partial correlation (e.g. [START_REF] Klein | Negatively Correlated Bandits[END_REF] or [START_REF] Rosenberg | On games of strategic experimentation[END_REF]).

• Lastly, the fact that dropping out is irreversible forbids any player to get back to experiment if they stopped it before. This will enable us to have a simple characterization of equilibria. Without this assumption, the study would be trickier notably because of free-riding.

Cuto Strategies

We want to study equilibria when N is large. Let us rst describe the strategies that characterizes equilibria for any N . To this aim, we introduce the notion of private belief and of the status of players.

To make a decision, a player i may take into account his past payos, which partially disclose the state. For that, he can compute his Private Belief, denoted p i n :

p i n = P(Θ = θ|X i n , ..., X i 1 ).
This is the probability that player i assigns to state High according to his own payos, regardless of others players' actions (as if he were alone).

Assuming he knows the others players' strategies, player i also knows how to account for other players' decisions. Let us set the r.v. α j,N n , which gives the status of player j at stage n in the N player game, as follows: α j,N n = if player j still active, α j,N n = m if j left at stage m (m ≤ n). One can sum up the status of all players (except i) in a random vector α -i,N n whose coordinates are the r.v. α j,N n (j = i). We will denote the vector such that all coordinates are . Moreover, a signicant parameter of the N player game is the number of departures before the end of stage n, and we will denote it k

(N ) n , i.e. k (N ) n = #{j ∈ {1, ..., N }|α j,N n = }.
Now, player i can play as follows: at each stage, he computes p i n and decides to stay only if it is above a given cut-o which depends on n and on the status of the other players α -i,N n . We dene cuto strategies as a sequence (π i,N n ( t n )) with values in [0, 1] indexed by the stages n ≥ 1 and by t n , the possible vectors of status at stage n. Player i plays the strategy if he stops at stage inf{n ≥ 1 :

p i n-1 < π i n-1 ( α -i,N n-1 )}.
Beware the notations that can be a bit deceptive, because the decision at stage n rely on private belief p i n-1 .

These strategies were introduced in [START_REF] Rosenberg | Social Learning in OneArmed Bandit Problems[END_REF]. Their study of equilibria is based on the 2-player game but their results are easily generalized for the game with any number of players. Their results also suppose the following assumption, and our results are based on this assumption as well.

Assumption A. The private belief p i 1 has a density w.r.t. the Lebesgue Measure.

This implies that the law of p i n is continuous for any n ≥ 1 (see section 3.1.1). This is a way to rule out mixed strategy and to simplify the description of equilibria: if p i 1 had atoms, some players could have the same belief at the same time and there would not exist equilibrium if they did not mix their strategy. Another consequence of A is that p i n has the same support under P θ and P θ : if not, it would mean that, with positive probability, p i n has a value that is characteristic of the state. So the state could be revealed and this value would be either 0 or 1. Consequently we would have P(p 1 n = 0) > 0 or P(p 1 n = 1) > 0, which contradicts the fact that p i n has a density.

The main result of [START_REF] Rosenberg | Social Learning in OneArmed Bandit Problems[END_REF] is the following.

Theorem 1.1. Under A, there exist symmetric equilibria. Moreover, every equilibrium strategy is a cuto strategy.

That is why a sequence of equilibria indexed by the number of players N will be sometimes referred to by the corresponding sequence of cutos π i,N n ( t n ) . Now we will study the asymptotic equilibria when N → +∞. As we will see, there are mainly two types of asymptotic equilibria.

Asymptotically Deterministic Equilibrium

1.3.1 Introducing example D.Rosenberg, E.Solan and N.Vieille [START_REF] Rosenberg | Social Learning in OneArmed Bandit Problems[END_REF] study limit equilibrium play as N → +∞ in a particular case. In this setting the support of p i 1 is [0, 1] and asymptotic equilibria can be fully and intuitively described. Basically, this full support assumption makes sure that some players will be so pessimistic after the rst stage that they will leave, which enable the other players to learn the state. To understand the description, we need to introduce the cuto p * , dened by the following equation:

p * θ 1 -δ + (1 -p * )θ = 0.
This is the cuto that makes a player indierent between staying and leaving when he is sure to learn the state at the following stage: leaving yields a payo of zero, whereas staying yields one payo of expectation θ in the Low state and payos of expectation θ for all the remaining stages in the High state. Consequently if a player has a belief below p * , he has to leave because even if he could learn the state afterwards, he will still not get a positive expectation. Conversely, if a player has a belief over p * and if he is going to learn the state at the following stage, he has to stay. Now let us describe the equilibria of large games when p i 1 has full support. After the rst payo, a fraction of players have a belief under p * and for them the best strategy is to drop out. This fraction depends on the state of the world, as players get on average more bad news in the Low state than in the High state. When the number of players is large, this reveals the state by the Law of Large Numbers. Thus players who have a belief above p * after the rst payo can aord to stay for one more stage as the number of departures will show them the state. Therefore players tends to play with cuto p * .

In this paper we do not assume that p i 1 has full support anymore. We dene F n,θ as the c.d.f. of p i n under P θ , and we dene π n as the worst possible belief at stage n:

π n = inf{π ∈ [0, 1] : F n,θ (π) > 0}.
Note that π n does not depend on θ, because p i n has the same support under P θ and P θ . First casual intuition suggests that learning is only delayed and the equilibria will still be deterministic: players will remain active until a fraction of them gets too bad news, leaves, and thus reveals the state to the others. Let us dene precisely this kind of asymptotic play.

Denition

A sequence of equilibria will be called Asymptotically Deterministic if, as the number of players gets large, the play is roughly always the same: players all experiment for a given number of stages, then some of them leaves, and then all remaining players play in perfect accordance to the state. Denition 1. A sequence of equilibria indexed by the number of players N for which each game is set is an Asymptotically Deterministic with delay n ≥ 1 if:

• P k (N ) n-1 = 0 -----→ N →+∞ 1 • P θ k (N ) n+1 = N -----→ N →+∞ 1 • P θ ∀l ≥ n, k (N ) n = k (N ) l -----→ N →+∞ 1.
Such a sequence will also be called an Asymptotically Deterministic Equilibrium (ADE). The idea is that the number k (N ) n of departures at stage n reveals the state to the remaining players, who then all leave in the Low state and all stay forever in the High state. Note that n = 1 is a possible value of the delay, but this situation basically means that nobody enters the game, and this does not make a determination of the state possible. Indeed, this would mean that in the Low state, every player drop out at the very beginning of the game, before getting any information. Consequently their decisions do not depend on their private payos, or a fortiori on the state, and the players all leave in the High state as well. In section 1.5, this situation will not be considered as an ADE.

Results

Let us now give necessary conditions and sucient conditions for the existence of an ADE with delay n.

Firstly, a fraction of players leave at stage n and this reveals the state to the others. Consequently, the most pessimistic belief is below p * . If not, any leaving player would have better stay active one more stage as he would learn the state and thus get a positive average payo. Moreover, this guarantees that a non negligible fraction of players, whose belief is below p * , does leave at stage n. So we have a rst condition.

Secondly, nobody leaves before stage n. So we have to ensure that, at any stage m < n, even the most pessimistic player is willing to stay in. Such a player's belief is π m-1 . He expects to get an average payo of π m-1 θ + (1 -π m-1 )θ for n -m stages before some players leave. At stage n he will leave only if his belief is below p * . If he stays he learns the state by looking at the number of departures, so that he remains active forever if the state is High, and leaves if the state is Low. The expected payo of this strategy must be positive for this player (say player i) to be right to remain active at stage m, as claimed in the following inequality:

(1 + δ + ... + δ n-m-1 ) π m-1 θ + (1 -π m-1 )θ +δ n-m π m-1 θ 1 -δ P θ (p i n-1 > p * |p i m-1 = π m-1 ) +(1 -π m-1 )θP θ (p i n-1 > p * |p i m-1 = π m-1 ) > 0. (I m )
We also denote by ( Ĩm ) the corresponding large inequality.

These conditions are summed up in the following theorem.

Theorem 1.2. If π n-1 < p * and if inequalities (I 1 ), (I 2 ),..., (I n-1 ) hold, then there exists an ADE.

Conversely if there exist an ADE, then π n-1 ≤ p * and inequalities ( Ĩ1 ), ( Ĩ2 ),..., ( Ĩn-1 ) hold.

In particular, the delay n is the rst stage such that π n-1 ≤ p * .

***This theorem enables us to know when there exists an ADE: as we will see in some examples (Section 1.5) and in corollary 1.3 below, this depends on the settings of the game (i.e. δ, p 0 , and the reward distributions f θ , f θ ). One can show that inequalities ( Ĩm ) and inequality π n-1 < p * are the necessary and sucient conditions for the existence of an equilibrium in the same game but with a continuum of players. In this view, our theorem is similar to the results of A. Caplin and J. Leahy [START_REF] Caplin | Business as usual, market crashes, and wisdom after the fact[END_REF].

If inequalities ( Ĩm ) and π n-1 ≤ p * hold with at least an equality, the existence of an ADE is uncertain. For example if ( Ĩm ) is an equality, two phenomenons compete when N is getting large: on the one hand the fact that there are more players may reveal the state at stage n with better accuracy; on the other hand, more and more players may have critical bad news at stage m and this could entail some exits before stage n. The balance between this two phenomenons is linked with the equivalent of x → P(p i m-1 ≤ x) in a neighbourhood of π m-1 and is left outside the scope of this paper. Finally, note that this theorem does not claim the uniqueness of asymptotic equilibria: it could be that... Now, let us give the main consequences of Theorem 1.2.

Corollary 1.3. • For any n ≥ 2, there exist settings of the game for which there exists an ADE with delay n.

• There exist settings of the game for which there is no ADE. ***Thus there are more asymptotic equilibria than equilibria in the continuum of player game.

Remember that, even if an ADE exists, it is not necessarily the unique asymptotic equilibrium. We have a uniqueness result though but, contrary to theorem 1.2, its hypothesis does not only rely on conditions on the settings of the game. This result is crucial to establish the alternative between the two types of asymptotic equilibria.

Proposition 1.4. If (Φ N ) is a sequence of equilibria such that P(k (N ) n-1 = 0) -----→ N →+∞ 0 and if π n-1 < p * , then (Φ N ) is an ADE with delay n.
This result takes up the same ideas as before: players wait for stage n, then a fraction of them gets a belief below p * and reveals it by leaving, which enables the others to learn the state.

The following section describes what happens when limit equilibrium play is not deterministic and exhibits randomness.

Other asymptotic equilibria and Poisson aggregate behaviour

Let us rst deal with symmetric equilibria. If a sequence of equilibria is not A.D. and if players delay their departures until stage n, then they limit themselves to only a few exits for the state not to be revealed at once. The distribution of this number of exits is asymptotically a Poissonian, the parameter of which depends on the state. Theorem 1.5. Let (Φ N ) N ≥1 be a sequence of symmetric equilibria. Assume that there exists a delay, i.e. a stage n such that

P(k (N ) n-1 = 0) -----→ N →+∞
1 and lim sup

N →+∞ P(k (N ) n = 0) < 1,
and assume also that π n-1 > p * . Then there exists two bounded sequences (λ θ,N ) N ≥1 and (λ θ,N ) N ≥1 , with (λ θ,N ) N ≥1 bounded away from zero, such that:

∀θ ∈ {θ, θ}, P θ (k (N ) n = k|k (N ) n-1 = 0) ∼ N →+∞ e -λ θ,N (λ θ,N ) k k! .
Note that the result still holds for a subsequence (i.e. for a sequence Φ ϕ(N ) N ≥1 , where ϕ : N → N is a non-decreasing function). Thus the condition of existence of a delay is not really binding, because any sequence of equilibria can be divided into subsequences for which there exists a delay. What strikes most is that the average number of exits at stage n stands bounded no matter how large the number of players N can be. This extents to non symmetric equilibria, as expressed in the following proposition which can be viewed as an alternative result of propostion 1.4.

Proposition 1.6.

If (Φ N ) is a sequence of equilibria such that P(k (N ) n-1 = 0) -----→ N →+∞
1 and if

π n-1 > p * , then the sequence E θ [k (N ) n |k (N ) n-1 = 0] N ≥1
is bounded.

Nevertheless it is not sure that we will always observe a Poisson distribution. For example, it could be that only a given group of players (say player 1 to player n 0 , where n 0 does not depend on N ) may leave at stage n. Every other player may aord to stay one more stage because this would enable them to learn the useful information given by this group.

To complete our study, let us comment the case of a sequence of equilibria (Φ N ) such that P(k

(N ) n-1 = 0) -----→ N →+∞
1 and if π n-1 = p * . This limit case does not entirely t our alternative, and what we observe in this case is a sort of weak ADE. The number of exits E θ [k

(N ) n |k (N )
n-1 = 0] tends to +∞ and this enables the players to discern the state, but the number of exits can be less than order N and the revelation is not as clear as in an ADE. One can show that:

• ∀i ≥ 1, P θ (α i,N n+1 = ) -----→ N →+∞ 0 • ∀i ≥ 1, ∀l ≥ n, P θ (α i,N n = α i,N l ) -----→ N →+∞ 1.
This is much weaker than in our denition of ADE.

As a conclusion, the scenario described in our introducing example (section 1.3.1) is not general. If we do not assume that players can be arbitrarily pessimistic after the rst stage, the scenario is either delayed and still deterministic, either completely dierent: in particular the process of learning exhibits randomness.

Examples

As an illustration of previous results, we would like to know when there exists ADE and to see how the parameters of the game aect this existence. We call the delay (and denote it n) the stage when rst players exit. In the case of ADE, n is the smallest integer such that π n-1 < p * . The setting is the following : the distribution of the X i n + 1 is exponential, with parameters λ θ if the state is High, and λ θ if the state is Low. To avoid trivial case, we must have

λ θ > 1 > λ θ , as E θ [X i n ] = 1 λ θ -1.
On Figures 1, 2 and 3, x-axis is the prior p 0 and y-axis is the discount rate δ. The color shading from left to right shows the increase of the delay n, except for darkest zones which are the values of p 0 and δ for which there can not be ADE. With a delay of n = 1, we have p 0 < p * and no player can aord to enter the game. This situation (an ADE with delay n = 1) is not considered as an ADE here (left of the gures).

The other possible values of n are bordered by curves π k = p * , k = 0, 1, 2, .... For given values of λ θ and λ θ , an increase of λ θ (which is equivalent to a decrease of θ) there are less possible ADE (see Fig. 1 and Fig. 2). Even if the delay is shorter (for given values of p 0 and δ), it that seems players can not wait for the revelation. Indeed, their average payos before the revelation is not high enough.

On the contrary, a decrease λ θ is an incentive for players to wait to learn the state. Thus, in the particular case of Fig. 3, there always exists ADE.

Similarly, an increase of δ seems to act as an incentive to wait, because after the revelation the reward is higher when in the High state. Indeed there always exists ADE if δ is close to 1.

Lastly, when δ goes to 0, the game becomes basic because only the following stage is significant. Thus strategies are straightforward: when it becomes possible that some players are obliged to quit because they do not expect a positive reward for the next stage, they leave and their departures reveals the state to the others. Consequently there are more ADE in this case.

2 Sketch of the proofs

We want to show that, except for some limit cases, asymptotic equilibria are either deterministic (when the conditions of existence of theorem 1.2 apply), or the state is not revealed when rst players leave and in this case the average number of exits is bounded w.r.t to N (as in theorem 1.5 and 1.3).

More precisely, we are interested in any sequence of equilibria (Φ N ) N ≥1 for which we can dene a delay n, which is asymptotically the rst stage where some players could decide to leave:

P(k (N ) n-1 = 0) -----→ N →+∞
1 and lim sup

N →+∞ P(k (N ) n = 0) < 1.
Remember that any sequence of equilibria can be divided into subsequences for which we can dene a delay. What we are going to explain still hold for subsequences. Note also that when N is large, all players always remain active before stage n and we can not derive any information from their behaviour. That is why player i's belief over the state at any stage m < n is assumed to be equal to his private belief p i m .

Let us denote n 0 = min{m ≥ 1|π m ≤ p * }. To avoid a limit case, we assume that π n 0 < p * . Stage n 0 + 1 is then the maximum value of the delay n. Indeed if we had n > n 0 + 1, it would imply that P(k

(N ) n 0 +1 = 0) -----→ N →+∞
1. Thus, for N large enough, every player would decide to remain at stage n 0 + 1, whereas a non negligible fraction of them would have a belief below p * . What we will see is that the behaviour of the players is dierent whether n = n 0 + 1 or n < n 0 + 1. In the rst case, players stay active until a fraction of them gets a belief below p * and leaves, which enable other players to learn the state. In the second case, the rst departures happen before any player can get a belief below p * . There can not be too many exits: if not this would give relevant information about the state and staying would be a dominant strategy for any player, as all of them has a belief greater than p * .

2.1 n = n 0 + 1: the Asymptotically Deterministic case

First, let us study the asymptotic equilibrium when n = n 0 + 1.

In this case, players wait at least until stage n 0 + 1 before dropping out. Then a non negligible part of them gets a belief below p * , and is obliged to drop out. Thus there is a signicant fraction of players who leave at stage n 0 + 1. As players get on average better news in the High state than in the Low state, this fraction depends on the state. On the other hand, players who decide to remain active after stage n 0 + 1 can observe this fraction and learn the state very accurately when N is large. So if player i decides to stay, he will get a n 0 + 1-th payo (the expectation of which is p i n 0 θ + (1 -p i n 0 )θ), and then by looking at the fraction of exits he will be able to play in accordance to the state: stay forever if it is High and drop out if it is Low. On average, player i's asymptotic continuation payo is then:

p i n 0 θ + (1 -p i n 0 )θ + δ p i n 0 θ 1 -δ + (1 -p i n 0 )0 = p i n 0 θ 1 -δ + (1 -p i n 0 )θ.
Therefore, by denition of p * , if p i n 0 > p * this payo is non-negative and player i will not drop out. This discussion enables us to conclude that players tend to play with cuto p * at stage n 0 + 1. Now let us see on what conditions this strategic prole is an asymptotic equilibrium. We consider the decision of player i at stage m ∈ {1, ..., n 0 }. If he follows the strategy prole described above, he is going to get n 0 -m + 1 payos, then at stage n he will remain active if p i n > p * , and then he will play in accordance to the state. The average payo of this strategy is:

(

1 + δ + ... + δ n-m-1 ) p i m-1 θ + (1 -p i m-1 )θ +δ n-m p i m-1 θ 1 -δ P θ (p i n-1 > p * |p i m-1 ) + (1 -p i m-1 )θP θ (p i n-1 > p * |p i m-1 ) .
This payo has to be positive. If not this strategy would not be optimal because player i would have better leave, which yields a continuation payo of 0. This even has to be positive for all players in any case. Consequently, this payo is still positive for a player who got the worst news from his private payos, i.e. whose private belief is π m-1 . That gives us inequality ( Ĩm ):

(1 + δ + ... + δ n-m-1 ) π m-1 θ + (1 -π m-1 )θ +δ n-m π m-1 θ 1 -δ P θ (p i n-1 > p * |p i m-1 = π m-1 ) +(1 -π m-1 )θP θ (p i n-1 > p * |p i m-1 = π m-1 ) ≥ 0.
Conversely if strict inequality (I m ) hold for any m ∈ {1, ..., n 0 } and if N is large enough, our strategic prole is an equilibrium. Indeed, any player at any stage m ∈ {1, ..., n 0 } can expect a non negative payo if he stays, whereas leaving would give him 0. Then at stage n each player plays with cuto p * which, as explained before, is the optimal strategy.

2.2 n < n 0 + 1: the average number of exits is bounded Now, let us consider the case n < n 0 + 1. This condition is equivalent to π n-1 > p * , and in this situation the asymptotic proportion of leaving players at stage n is either 0 or 1. Indeed if the fraction were in-between, it would depend on the state because players averagely get worse beliefs in the Low state. Then, as explained in the former case, any player who decides to leave at stage n should deviate and stay, because staying would enable him to watch the fraction of exits, and thus he could learn the state and react accordingly. This strategy would yield a positive payo because private beliefs are greater than p * .

In fact the fraction of exits can not be 1 either. Indeed, the condition P(k

(N ) n-1 = 0) -----→ N →+∞
1 means that, asymptotically, every players have planned to stay until the end of stage n -1, and being that optimistic is not consistent with dropping out for sure at the next stage (see ??).

Thus there are few exits at stage n. We denote by λ θ,N and λ θ,N the average number of leaving players at stage n, in the N -player equilibrium Φ N , respectively in the High and in the Low state:

λ θ,N = E θ [k (N ) n |k (N ) n-1 = 0], λ θ,N = E θ [k (N ) n |k (N ) n-1 = 0].
What we have showed is that

λ θ,N
N and

λ θ,N
N go to zero as N goes to +∞. In fact λ θ,N and λ θ,N are bounded w.r.t. to N because too many exits would still enable active players to have a good guess on the state if N is large enough. λ θ,N is also bounded away from zero: by denition of the delay n some players are likely to leave the game at stage n (that is the condition lim sup

N →+∞ P(k (N ) n = 0) < 1)
, and there are more exits in the Low state than in the High state. Now let us consider the case of symmetric equilibria. As players all play the same strategy, the probability to leave at stage n for each of them is

λ θ,N
N , which depends on the state (θ ∈ {θ, θ}). At stage n the decision only depends on private payos, which are independent across players conditionally to the state. Therefore the number of exits k

(N ) n
is the sum of N independent Bernoulli r.v. with the same parameter

λ θ,N N . So the distribution of k (N ) n
is a binomial, which is usually equivalent to a Poisson distribution when N is large:

∀θ ∈ {θ, θ}, P θ (k (N ) n = k|k (N ) n-1 = 0) ∼ N →+∞ e -λ θ,N λ k θ,N k! .
Let us sum up our two cases: we have an alternative between a massive and deterministic dropping out of a fraction of players (if π n-1 < p * ), and a bounded average number of exits (if π n-1 > p * ). In the rst case we have established that some inequalities must hold for this situation to be an equilibrium. That is the content of theorem 1.2, 1.5 and 1.6.

3 Proofs

Preliminary results

The proof of the main theorems requires some preliminary results that are given in the present section.

Beliefs

Let us give a more detailed presentation of beliefs. As p i 1 has a density, the payos X i 1 have a density f θ under P θ . By means of Bayes rule, we then have an explicit formula:

p i n 1 -p i n = p 0 1 -p 0 f θ (X i 1 ) f θ (X i 1 ) • • • f θ (X i m ) f θ (X i m ) • • • f θ (X i n ) f θ (X i n )
, and in particular we have

p i n 1 -p i n = p i m 1 -p i m f θ (X i m+1 ) f θ (X i m+1 ) • • • f θ (X i n ) f θ (X i n ) . (1)
Now assume that others' strategy prole is xed.

All the information gathered by player i at stage n is then given by his Posterior Belief, denoted q i n :

q i n = P(Θ = θ|X i n , ..., X i 1 , α -i,N n ).
Similarly, we have the following formula by Bayes rules:

q i n 1 -q i n = p i n 1 -p i n P θ ( α -i,N n = α) P θ ( α -i,N n = α) ,
whenever α -i,N n = α. We will often debate the case of every player remaining active until a certain stage n as N is getting large, i.e. P(k

(N ) n = 0) -----→ N →+∞
1. The number of departure observed by

player i is k -i,N n , dened as # j ∈ {1, • • • , N }\{i}|α j,N n = . As k -i,N n ≤ k (N )
n , we have

P(k -i,N n = 0) -----→ N →+∞ 1, and because P(k -i,N n = 0) = p 0 P θ (k -i,N n = 0)+(1-p 0 )P θ (k -i,N n = 0)
one can write:

P θ (k -i,N n = 0) -----→ N →+∞ 1 and P θ (k -i,N n = 0) -----→ N →+∞ 1.
The events { α -i,N n = } and {k -i,N n = 0} are equal, so that player i's posterior belief is equivalent to his private belief when k (N ) n = 0:

q i n 1 -q i n = p i n 1 -p i n P θ (k -i,N n = 0) P θ (k -i,N n = 0) ⇒ q i n = p i n P θ (k -i,N n = 0) p i n P θ (k -i,N n = 0) + (1 -p i n )P θ (k -i,N n = 0) ∼ N →+∞ p i n
This explain the fact mentioned in section 2 that player i can not derive public information from his opponents, the latter being expected to remain active no matter what their private payos could be.

Special Cut-os

One player cut-o π * When there is only one player, the game reduces to an optimal stopping problem which is equivalent to the classic one-arm bandit problem (see [START_REF] Chow | On optimal stopping rules[END_REF] and [START_REF] Ferguson | Optimal stopping and applications[END_REF]) where exit decisions can be assumed reversible. Indeed, if the player nds it optimal not to play at a given stage, it will remain optimal for the following stages. In this case, the optimal policy is to leave as soon as the belief p i n drops below a time-independent given cut-o, denoted π * . Note that, in our multi-player model, if q i n ≥ π * player i will nd it optimal to remain active: in this situation, even if he could not observe the others any more, staying would still be the best decision.

Myopic cut-o p A simple way to decide to stay is to account just for the next stage. Its expected payo, that we call myopic payo and denote myop(q i n ), equals q i n θ + (1 -q i n )θ.

The myopic cut-o, denoted p is dened as the only value such that myop(p) = 0. It is readily seen that if q i n ≥ p, player i has to stay at least one more stage. As this is still true in the one-player game, one has also p ≥ π * .

Best optimal continuation payo cut-o p * We have already introduced the cuto p * .

Let us give an another presentation based on the notion of optimal continuation payo. When facing the decision at the beginning of stage n, a player has to balance two things. On the one hand, there is the next payo with expectation myop(q i n ). On the other hand if he stays he can expect to be informed better for the next decision, thanks to the the payo X i n and to other players' behavior. At most, he could learn the state nearly perfectly. Thus, if he stays he can not expect more than the best optimal continuation payo:

opt(q i n ) = myop(q i n ) + δq i n θ 1 -δ = q i n θ 1 -δ + (1 -q i n )θ
which is possible to get if at stage n + 1 he leaves when the state is Low, or stays forever if the state is High.

In [START_REF] Rosenberg | Social Learning in OneArmed Bandit Problems[END_REF], it is showed that, a strategy prole being xed, the optimal continuation payo, i.e. the expected payo player i can get from a stage n + 1 if he stays at stage n + 1 and then plays optimally, is a function ω i,N n which only depends on p i n and α -i,N n . This means that the optimal strategy consists in staying active as long as

ω i,N n (p i n , α -i,N n ) ≥ 0.
And from what is explained above, we deduce that opt(q

i n ) ≥ ω i,N n (p i n , α -i,N n ).
We dene the best optimal continuation payo p * as the unique cut-o such that opt(p * )=0.

A simple property of p * is that if q i n ≤ p * , it is a dominant strategy to leave. On the contrary, if q i n > p * player i has to stay if he is optimistic enough and/or if he expects to get a good piece of information looking at other players' behavior. In particular, the more players there are, the more information he can expect.

The optimal continuation payo has a role in our results. In an ADE with delay n, when the end of stage n is reached, a wave of exits reveals the state with more and more accuracy as N is getting large. Asymptotically, any player i is facing the optimal continuation payo when making his decision at stage n. Consequently, at stage m, player i expects a continuation payo of:

(1 + δ + ... + δ n-m-1 )myop(p i m-1 ) + δ n-m E[max 0, opt(p i n-1 ) |p i m-1 ].
As myop is non decreasing and p i n-1 is increasing w.r.t. to p i m-1 (equation (1)), this expression is non decreasing w.r.t. p i m-1 : this explains explains the intuitive fact that a player is all the more willing to stay in the game as his belief is higher. Moreover, one can show that:

p i m-1 θ 1 -δ P θ (p i n-1 ≥ p * |p i m-1 ) + (1 -p i m-1 )θP θ (p i n-1 ≥ p * |p i m-1 ) = E[max 0, opt(p i n-1 ) |p i m-1 ]
Combining the last two equalities and with p i m-1 = π m-1 , we nd an other expression of equalities (I m ) and ( Ĩm ). It has to be positive for any player to be right to remain active at stage m (leaving only yields a payo of 0). It is also worth noticing that, the left side of equality ( Ĩm ) being an expression of a continuation payo with belief π m-1 , it is strictly lower than opt(π m-1 ). Consequently if ( Ĩm ) holds then π m-1 > p * . This explains the last part of theorem 1.2: in an ADE, the delay n is necessarily the rst stage such that π n-1 ≤ p * .

No let us give some results about how a player behaviour aects the other players' beliefs. We want to formalize the fact that players get on average better news in the High state than in the Low state, and as a consequence it is good news for a player to observe his opponents remaining active.

Staying is always good news

If a player i (with cut-os π i m ( t)) stays until stage n + 1, his contribution to other active players' beliefs is given by the following likelihood ratio:

P θ (p i n ≥ π i,N n ( α -i,N n ), p i n-1 ≥ π i,N n-1 ( α -i,N n-1 ), ..., p i 1 ≥ π i,N 1 ( α -i,N 1
))

P θ (p i n ≥ π i,N n ( α -i,N n ), p i n-1 ≥ π i,N n-1 ( α -i,N n-1 ), ..., p i 1 ≥ π i,N 1 ( α -i,N 1
)) .

Now, if this player is still active at stage n + 2, the former contribution has to be updated by multiplying by:

P θ (p i n+1 ≥ π i,N n+1 ( α -i,N n+1 )|p i n ≥ π i,N n ( α -i,N n ), ..., p i 1 ≥ π i,N 1 ( α -i,N 1
))

P θ (p i n+1 ≥ π i,N n+1 ( α -i,N n+1 )|p i n ≥ π i,N n ( α -i,N n ), ..., p i 1 ≥ π i,N 1 ( α -i,N 1
)) .

The fact that this ratio is always greater than 1, i.e. that it is always good news to observe a player staying active, is a by-product of proposition 3.2 thereafter. To obtain this result we need the following lemma, the proof of which can be found in the appendix.

Lemma 3.1. For each stage n and each cuto π 1 , ..., π n-1 ∈ [0, 1], the likelihood ratio

π → P θ (p i n ≥ π, p i n-1 ≥ π n-1 , ..., p i 1 ≥ π 1 ) P θ (p i n ≥ π, p i n-1 ≥ π n-1 , ..., p i 1 ≥ π 1 )
is increasing.

We now come to our proposition.

Proposition 3.2. (Conditional stochastic dominance)

For each stage n and k ∈ {0, 1, ..., n -1}, x 1 , x 2 , ..., x n ∈ [0, 1],

P θ (p i n ≥ x n , ..., p i k+1 ≥ x k+1 |p i k ≥ x k , ..., p i 1 ≥ x 1 ) ≥ P θ (p i n ≥ x n , ..., p i k+1 ≥ x k+1 |p i k ≥ x k , ..., p i 1 ≥ x 1 )
Proof. Thanks to Lemma 3.1, as x n ≥ 0, we can write:

P θ (p i n ≥ x n , p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 ) P θ (p i n ≥ x n , p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 ) ≥ P θ (p i n ≥ 0, p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 ) P θ (p i n ≥ 0, p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 ) ≥ P θ (p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 ) P θ (p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 )
.

Hence:

P θ (p i n ≥ x n , p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 ) P θ (p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 ) ≥ P θ (p i n ≥ x n , p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 ) P θ (p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 )
, which is exactly the desired result for k = n -1. We derived from this the whole proposition, as:

P θ (p i n ≥ x n , ..., p i k+1 ≥ x k+1 |p i k ≥ x k , ..., p i 1 ≥ x 1 ) = P θ (p i n ≥ x n |p i n-1 ≥ x n-1 , ..., p i 1 ≥ x 1 ) × P θ (p i n-1 ≥ x n-1 |p i n-2 ≥ x n-2 , ..., p i 1 ≥ x 1 ) ×... × P θ (p i k+1 ≥ x k+1 |p i k ≥ x k , ..., p i 1 ≥ x 1 ).
Let us mention a simple consequence of proposition 3.2 which will be useful subsequently, and which shows that public information is increasing from stage to stage as long as no more players leave.

Corollary 3.3. For all cuto strategy proles, for all stages n > m, and for all i ∈ {1, • • • , N },

P θ k -i,N n = k -i,N m | α -i,N m P θ k -i,N n = k -i,N m | α -i,N m ≥ 1 a.s.
Proof. As the payos are independent across players conditionally to the state, the above ratio is equal to

j =i|α j m = P θ (p j n ≥ π j,N n ( α -j,N m ), ..., p j m+1 ≥ π -j,N m+1 ( α -j,N m )|p j m ≥ π j m ( α -j,N m ), ..., p j 1 ≥ π j,N 1 ( α -j,N 1
))

P θ (p j n ≥ π j,N n ( α -j,N m ), ..., p j m+1 ≥ π j,N m+1 ( α -j,N m )|p j m ≥ π j,N m ( α -j,N m ), ..., p j 1 ≥ π j,N 1 ( α -j,N 1
)) , and all the factors in this product are greater than 1 because of proposition 3.2.

Thus, it has been showed that a player staying active increases his contribution in other players' posterior beliefs from stage to stage. But this is an increase in a large sense, as his contribution can remain constant. For instance, in an ADE every player asymptotically stay active until the revelation stage no matter what their private information may be, and their public contribution remain equal to 1. Now we will show that someone leaving after a stage where all players were still active represents a strict decrease of his contribution to others' posterior belief.

Leaving is bad news

What we want to study specically is what happens when rst players exit. To this aim, we introduce the probability

P n,θ = P θ (• • • |k (N ) n = 0
) and E n,θ the corresponding expectation (a sequence of equilibria being given). Let F i n,θ be the c.d.f. of p i n under this probability:

F i n,θ (x) = P θ p i n ≤ x k (N ) n = 0 . Note that F i n,θ (x) = P θ p i n ≤ x p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1
( ) by independence of payos across players conditionally to the state. In particular, by denition of cuto strategies we have:

P θ (i leaves at stage n + 1|k (N ) n = 0) = F i n,θ (π i,N n ( )).
To show that leaving is meaningful, we need to prove that one can not forecast with certainty that a player i will stop at a given stage. If not, this exit cannot give us any information as it was due to happen, no matter what player i's private information is.

The following lemma states that, in an equilibrium where every player have planned to stay until stage n, the probability that a rational player leaves the game at stage n + 1 is uniformly less than 1. Indeed, being too pessimistic would not be consistent with staying until stage n.

Lemma 3.4. Let (Φ N ) be a sequence of equilibrium such that P(k

(N ) n = 0) -----→ N →+∞ 1.
There exists N 0 ≥ 0 and β θ , β θ ∈ [0, 1) such that:

∀N ≥ N 0 , ∀θ ∈ {θ, θ}, P n,θ (i leaves at stage n + 1|p i n-1 ) ≤ β θ P n,θ -a.s.
In particular:

∀N ≥ N 0 , ∀θ ∈ {θ, θ}, P n,θ (i leaves at stage n + 1) = F i n,θ (π i,N n ( )) ≤ β θ .
Proof. Let us rst prove the existence of β θ .

We are studying the decision of player i at stage n + 1, given that his private belief at stage n, p i n-1 , is known. As we are working under the probability P n,θ , we can also assume that he has not observe any departure from other players yet. So his posterior belief at stage n is also known:

q i n-1 1 -q i n-1 = p i n-1 1 -p i n-1 P θ (k -i,N n-1 = 0) P θ (k -i,N n-1 = 0) .
The fact that player i will not decide to leave at stage n + 1 too often is the consequence of one of two cases: either he has got news good so far and he will mostly remain optimistic at stage n + 1, either he has not but the fact that he has not dropped out until stage n anyway shows that he is still expecting something and will not leave too soon.

Case n • 1: player i is optimistic enough to get a posterior belief at stage n greater than the myopic cuto p.

From the inequality θ < 0 < θ, it is easy to show that there exists , > 0 such that

P θ f θ (X i n ) f θ (X i n ) ≥ 1 + ≥ . Assume that q i n-1 1-q i n-1 > p 1-p 1 1+ .
As it is a strictly dominant strategy to stay when the belief is greater than p, we have:

P n,θ (i stays at stage n + 1|p i n-1 ) ≥ P n,θ (q i n ≥ p|p i n-1 ) = P n,θ q i n 1 -q i n ≥ p 1 -p p i n-1 = P n,θ       q i n-1 1 -q i n-1 f θ (X i n ) f θ (X i n ) P θ (k -i,N n-1 = 0|k -i,N n-2 = 0) P θ (k -i,N n-1 = 0|k -i,N n-2 = 0) ≥1 see corollary3.3 ≥ p 1 -p p i n-1       ≥ P n,θ p 1 -p 1 1 + f θ (X i n ) f θ (X i n ) ≥ p 1 -p p i n-1 = P n,θ f θ (X i n ) f θ (X i n ) ≥ 1 + p i n-1
As p i n-1 and k

(N ) n are measurable w.r.t. σ X j m , 1 ≤ m ≤ N, 1 ≤ m ≤ n -1 , they are inde-
pendent from X i n under P θ , and we have:

P n,θ f θ (X i n ) f θ (X i n ) ≥ 1 + p i n-1 = P θ f θ (X i n ) f θ (X i n ) ≥ 1 + ≥ .
Case n • 2: he is not that optimistic but he still had to experiment. In this case, we have:

q i n-1 1 -q i n-1 ≤ p 1 -p 1 1 + .
We are working under probability P n,θ , so we assume that k (N ) n = 0. In particular player i decides to remain active at stage n and p i n-1 ≥ π i,N n-1 ( ). Consequently the continuation payo that he was expecting to get at stage n is positive. Let us overestimate this continuation payo. At the beginning of stage n, player i's decision is based on the information k

(N )
n-1 = 0 and on p i n-1 . When he stays, he rst gets a myopic payo of expectation myop(q i n-1 ). Then, if he observes k -i,N n = 0 he will stay if p i n ≥ π i,N n ( ). Let us say this will never happen in the Low state and, if he stays in the High state, he will remain active forever (which yields on average θ 1-δ ). Moreover, we can overestimate his continuation payo when k -i,N n = 0 by θ 1-δ in the High state and by 0 in the Low state. So we have the following overestimation: myop(q i n-1 ) +

q i n-1 δθ 1 -δ P θ (p i n ≥ π i,N n ( )|k -i,N n = 0, k (N ) n-1 = 0, p i n-1 )P θ (k -i,N n = 0|k (N ) n-1 = 0, p i n-1 ) + q i n-1 P θ (k -i,N n = 0|k (N ) n-1 = 0, p i n-1 ) θ 1 -δ . As p i n-1 ≥ π i,N n-1 ( ), we have α i,N n = and conditioning by k -i,N n = 0, k (N ) n-1 = 0, p i n-1 is equivalent to conditioning by k (N ) n = 0, p i n-1 .
As a consequence we have:

P θ (p i n ≥ π i,N n ( )|k -i,N n = 0, k (N ) n-1 = 0, p i n-1 ) = P n,θ (p i n ≥ π i,N n ( )|p i n-1 ).
The same argument, together with the fact other players' decisions do not depend on is p i n-1 but only on α i,N n , enables us to write:

P θ (k -i,N n = 0|k (N ) n-1 = 0, p i n-1 ) = P θ (k -i,N n = 0, α i,N n = |k (N ) n-1 = 0, p i n-1 ) ≤ P θ (k (N ) n = 0|k (N ) n-1 = 0, p i n-1 ) ≤ P θ (k (N ) n = 0).

Moreover we can simply overestimate

P θ (k -i,N n = 0|k (N ) n-1 = 0, p i n-1
) by 1. Consequently player i's continuation payo is less than:

myop(q i n-1 ) + q i n-1 δθ 1 -δ P n,θ (p i n ≥ π i,N n ( )|p i n-1 ) + q i n-1 P θ (k (N ) n = 0) θ 1 -δ .
And than:

myop( p 1 + (1 -p) ) + δθ 1 -δ P n,θ (p i n ≥ π i,N n ( )|p i n-1 ) + P θ (k (N ) n = 0) θ 1 -δ .
As player i did decide to remain active at stage n, this payo is necessarily positive: if not he would have better leave, which yields a payo of 0. Consequently we have:

P n,θ (p i n ≥ π i,N n ( )|p i n-1 ) ≥ - 1 -δ δθ myop( p 1 + (1 -p) ) + P θ (k (N ) n = 0) θ 1 -δ .
As P(k

(N ) n = 0) -----→ N →+∞ 1, one can nd N 0 ≥ 1 such that, for any N ≥ N 0 : - 1 -δ δθ myop( p 1 + (1 -p) ) + P θ (k (N ) n = 0) θ 1 -δ ≥ - 1 -δ 2δθ myop( p 1 + (1 -p)
).

As a conclusion of the two cases, we can set

β θ = max(1 -, 1 + myop( p 1+ (1-p) ) 1-δ 2δθ ).
Now, we will prove the existence of β θ .

Let G θ be the c.d.f. of

f θ (X i n ) f θ (X i n ) under P θ .
We have:

P n,θ (p i n ≤ π i,N n ( )|p i n-1 ) = P n,θ p i n 1 -p i n ≤ π i,N n ( ) 1 -π i,N n ( ) p i n-1 = P n,θ f θ (X i n ) f θ (X i n ) p i n-1 1 -p i n-1 ≤ π i,N n ( ) 1 -π i,N n ( ) p i n-1 = G θ π i,N n ( ) 1 -π i,N n ( ) 1 -p i n-1 p i n-1 (2)
because X i n is independent from p i n-1 and k (N ) n under P θ . As G θ is continuous and increasing, we can consider the real r = max G -1 θ ({β θ }). Then G θ (r) = β θ < 1, and, according to equation (2) by the property of β θ we have:

π i,N n ( ) 1 -π i,N n ( ) 1 -p i n-1 p i n-1 ≤ r P n,θ -a.s.
This is equivalent to:

P θ k (N ) n = 0 ∩ π i,N n ( ) 1 -π i,N n ( ) 1 -p i n-1 p i n-1 > r = 0.
And to:

P θ            i = 1, ..., N l = 1, ..., n -1 p i l ≥ π i,N l ( )        ∩ π i,N n ( ) 1 -π i,N n ( ) 1 -p i n-1 p i n-1 > r     = 0.
As the private beliefs have the same support under P θ and P θ , we have:

P θ            i = 1, ..., N l = 1, ..., n -1 p i l ≥ π i,N l ( )        ∩ π i,N n ( ) 1 -π i,N n ( ) 1 -p i n-1 p i n-1 > r     = 0,
and equivalently:

π i,N n ( ) 1 -π i,N n ( ) 1 -p i n-1 p i n-1 ≤ r P n,θ -a.s.
Then, by means of equation (2):

P n,θ (p n i ≤ π i,N n ( )|p i n-1 ) = G θ π i,N n ( ) 1 -π i,N n ( ) 1 -p i n-1 p i n-1 ≤ G θ (r) P n,θ -a.s. As f θ (X i n ) f θ (X i n )
has the same support under P θ and P θ , G θ (r) < 1 so that we can set β θ = G θ (r).

Remark 1. The proof shows us that the existence of β θ and β θ can be written as the existence of a non-negative real r such that

π i,N n ( α i n-1 ) 1-π i,N n ( α i n-1 ) 1-p i n-1 p i n-1 ≤ r P n,θ -a.s. Then β θ = G θ (r),
where

G θ is the c.d.f. of f θ (X i n ) f θ (X i n ) under P θ .
As a consequence of Lemma 3.4, the lemma thereafter states that a player leaving when everybody is still active implies a strict pessimism for the others. Indeed, the evolution of his contribution in public information is then

P θ (p i n ≤ π i,N n ( )|p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( )) P θ (p i n ≤ π i,N n ( )|p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( )) = F i n,θ (π i,N n ( )) F i n,θ (π i,N n ( ))
and is smaller than a constant γ < 1.

Proposition 3.5. Let (Φ N ) be a sequence of equilibria such that P(k (N )

n = 0) -----→ N →+∞ 1.
There exists N 0 ≥ 0 and γ ∈ [0, 1) such that:

∀N ≥ N 0 , ∀i ∈ {1, ..., N }, F i n,θ (π i,N n ( )) ≤ γF i n,θ (π i,N n ( )).
Proof. We rst show that there exists as an upper bound γ < 1 of G θ G θ on (ν, r], where G θ and r have been introduced in Lemma 3.4, and where ν is the inmum of the support of

f θ (X i n ) f θ (X i n ) (for G θ G θ to be dened). Notice that: ∀x ∈ [0, r], G θ (x) = f θ (u) f θ (u) ≤x f θ (u)du ≤ f θ (u) f θ (u) ≤x xf θ (u)du = xG θ (x) ≤ rG θ (x).
Consequently if r < 1, setting γ = r enables us to conclude. If not, thanks to the presence of bad news, there exists γ 1 < 1 such that G θ (γ 1 ) > 0. Then γ 1 > ν, and just as before we have:

∀x ∈ [0, γ 1 ], G θ (x) ≤ γ 1 G θ (x).
In particular:

G θ (γ 1 ) < G θ (γ 1 ) =⇒ 1 -G θ (γ 1 ) 1 -G θ (γ 1 ) > 1.
On the other hand the function

x → 1 -G θ (x) 1 -G θ (x) = P θ f θ (X i n ) f θ (X i n ) ≥ x P θ f θ (X i n ) f θ (X i n ) ≥ x is well dened on [γ 1 , r] (because x ≤ r implies that G θ (x) ≤ G θ (r) < 1)
and increasing (see Lemma 3.1). Thus:

∀x ∈ [γ 1 , r], 1 -G θ (x) 1 -G θ (x) ≥ 1 -G θ (γ 1 ) 1 -G θ (γ 1 ) > 1,
and:

∀x ∈ [γ 1 , r], G θ (x) < G θ (x).
Going back to the function

G θ
G θ , we then see that, on the segment [γ 1 , r], its values are all in (0, 1). As this function is continuous, we have by compactness:

max [γ 1 ,r] G θ G θ < 1.
To conclude, we can set

γ = max(γ 1 , max [γ 1 ,r] G θ G θ ), so that: ∀x ∈ [0, r], G θ (x) ≤ γG θ (x). (3)
γ is indeed the upper bound we were looking for. Now, let us see why γ applies to the conclusion of our lemma. We choose N 0 as given by Lemma 3.4. We have:

F i n,θ (π i,N n ( )) = P n,θ (p i n ≤ π i,N n ( )) = E n,θ P n,θ (p i n ≤ π i,N n ( )|p i n-1 ) = E θ G θ π i,N n ( ) 1 -π i,N n ( ) 1 -p i n-1 p i n-1 p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( )
by means of equation ( 2), and because conditioning by k

(N ) n = 0 is equivalent to conditioning by {p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1
( )} by independence of payos across player conditionally to the state.

As π i,N n ( ) 1-π i,N n ( ) 1-p i n-1 p i n-1
≤ r, (3) applies and one can write by positivity of expectation:

F i n,θ (π i,N n ( )) = E θ G θ π i,N n ( ) 1 -π i,N n ( ) 1 -p i n-1 p i n-1 p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( ) ≤ γE θ G θ π i,N n ( ) 1 -π i,N n ( ) 1 -p i n-1 p i n-1 p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( ) .
In order to conclude, we need to replace

E θ by E θ . As G θ π i,N n ( ) 1-π i,N n ( ) 1-p i n-1 p i n-1
is positive and decreasing w.r.t. p i n-1 , this can be done by approximation by positive linear combination of functions of the form 1 p i n-1 <π , with π in [0, 1]. Consequently, it remains to show that:

P θ p i n-1 < π|p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( ) ≤ P θ p i n-1 < π|p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( ) ,
which is equivalent to:

P θ p i n-1 ≥ π|p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( )) ≥ P θ (p i n-1 ≥ π|p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( ) .
If π ≤ π i,N n-1 ( ), both terms of the inequality equal 1. If not, the former inequality can be written as:

P θ p i n-1 ≥ π, ..., p i 1 ≥ π i,N 1 ( )
P θ p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( ) ≥ P θ p i n-1 ≥ π, ..., p i 1 ≥ π i,N 1 ( )
P θ p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( )
, and:

P θ p i n-1 ≥ π, ..., p i 1 ≥ π i,N 1 ( )
P θ p i n-1 ≥ π, ..., p i 1 ≥ π i,N 1 ( )
≥ P θ p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( )
P θ p i n-1 ≥ π i,N n-1 ( ), ..., p i 1 ≥ π i,N 1 ( )
.

The result then follows from Lemma 3.1.

Main theorems

Proposition 1.6 and consequences

First, let us demonstrate proposition 1.6, and then draw some useful consequences.

Proof. Assume for contradiction that

E θ [k (N ) n |k (N ) n-1 = 0] N ≥1 = N i=1 F i n-1,θ (π i,N n-1 ( )) N ≥1
is not bounded. Up to a subsequence, one has

lim N →+∞ E θ [k (N ) n |k (N ) n-1 = 0] = +∞.
Let us show that this assumption enables to learn the state at the following stage if N is large enough, by comparing k

(N ) n to M N = E θ [k (N ) n |k (N ) n-1 =0]+E θ [k (N ) n |k (N ) n-1 =0] 2 . Indeed k (N ) n
tends to be greater than M N in the Low state and lower than M N in the High State, because players get worse news in the Low state and leave more often. Let us prove this:

P θ k (N ) n < M N k (N ) n-1 = 0 = P θ   k (N ) n < N i=1 F i n-1,θ (π i,N n-1 ( )) + F i n-1,θ (π i,N n-1 ( )) 2 k (N ) n-1 = 0   = P θ       N i=1 F i n-1,θ (π i,N n-1 ( )) -k (N ) n > N i=1 F i n-1,θ (π i,N n-1 ( )) -F i n-1,θ (π i,N n-1 ( )) 2 >0 k (N ) n-1 = 0       ≤ P θ   N i=1 F i n-1,θ (π i,N n-1 ( )) -k (N ) n > N i=1 F i n-1,θ (π i,N n-1 ( )) -F i n-1,θ (π i,N n-1 ( )) 2 k (N ) n-1 = 0   ≤ 4 N i=1 F i n-1,θ (π i,N n-1 ( )) -F i n-1,θ (π i,N n-1 ( )) 2 N i=1 F i n 1 ,θ (π i,N n-1 ( )) -F i n-1,θ (π i,N n ( ))
2 by means of Tchebychev's inequality.

Moreover, thanks to proposition 3.5:

γF i n-1,θ (π i,N n-1 ( )) ≥ F i n-1,θ (π i,N n-1 ( ))
with γ ∈ [0, 1) and N large enough, so that:

P θ k (N ) n < M N k (N ) n-1 = 0 ≤ 4 N i=1 F i n-1,θ (π i,N n-1 ( )) (1 -γ) 2 N i=0 F i n-1,θ (π i,N n-1 ( )) 2 ≤ 4 (1 -γ) 2 N i=1 F i n-1,θ (π i,N n-1 ( )) = 4 (1 -γ) 2 E θ [k (N ) n |k (N ) n-1 = 0] -----→ N →+∞ 0.
Similarly, one can show that:

P θ k (N ) n ≥ M N k (N ) n-1 = 0 ≤ 4 N i=1 F i n-1,θ (π i,N n-1 ( )) (1 -γ) 2 N i=0 F i n-1,θ (π i,N n-1 ( )) 2 ≤ 4 N i=1 F i n-1,θ (π i,N n-1 ( )) (1 -γ) 2 N i=0 F i n-1,θ (π i,N n-1 ( )) 2 = 4 (1 -γ) 2 N i=1 F i n-1,θ (π i,N n-1 ( )) = 4 (1 -γ) 2 E θ [k (N ) n |k (N ) n-1 = 0] -----→ N →+∞ 0.
Now let us see how this aects player i's decision. He is able to make to make a similar comparison, between k -i,N n and M

i N = E θ [k -i,N n |k (N ) n-1 =0]+E θ [k -i,N n |k (N ) n-1 =0] 2
. In this case we have:

P θ k -i,N n < M i N k (N ) n-1 = 0 ≤ 4 (1 -γ) 2 E θ [k -i,N n |k (N ) n-1 = 0] ≤ 4 (1 -γ) 2 E θ [k (N ) n |k (N ) n-1 = 0] -1 (4)
and

P θ k -i,N n ≥ M i N k (N ) n-1 = 0 ≤ 4 (1 -γ) 2 E θ [k (N ) n |k (N ) n-1 = 0] -1 . ( 5
)
Consider the strategy consisting in leaving if k -i,N n ≥ M i N and staying forever otherwise, when everybody is still active at the end of stage n -1, i.e. k

(N )

n-1 = 0. The overall expected payo after stage n -1 is:

opt(q i n-1 ) - δq i n-1 θ 1 -δ P θ k -i,N n ≥ M i N k (N ) n-1 = 0 + (1 -q i n-1 )δθ 1 -δ P θ k -i,N n-1 < M i N k (N ) n-1 = 0 .
Thanks to equation 4 and 5, one can underestimate this by:

opt(q i n-1 ) - 4δ(θ -θ) (1 -δ)(1 -γ) 2 E θ [k (N ) n |k (N ) n-1 = 0] -1 (6)
In our case

q i n-1 1-q i n-1 = p i n-1 1-p i n-1 P θ (k (N ) n-1 =0) P θ (k (N ) n-1 =0) ≥ p i n-1 1-p i n-1
thanks to Lemma 3.3, so that q i n-1 ≥ p i n-1 ≥ π n-1 . Therefore, our strategy yields at least an average payo of:

opt(π n-1 ) - 4δ(θ -θ) (1 -δ)(1 -γ) 2 E θ [k (N ) n |k (N ) n-1 = 0] -1 -----→ N →+∞ π n θ 1 -δ + (1 -π n-1 )θ = opt(π n-1 ) > 0, as π n-1 > p * .
Consequently, this payo is non-negative for any q i n-1 and for N large enough and any player should stay active at stage n. This is absurd because the equilibrium strategy leads some players to leave in some non negligible cases: if not, the sequence E θ [k

(N ) n |k (N ) n-1 = 0] N ≥1
would not converge to +∞.

Remark 2. In this proof, notice that we compared k

(N ) n to M N = E θ [k (N ) n |k (N ) n-1 =0]+E θ [k (N ) n |k (N ) n-1 =0] 2 , but we could equivalently have compared it to any strict convex combination of E θ [k (N ) n |k (N ) n-1 = 0] and E θ [k (N ) n |k (N ) n-1 = 0].
More generally, for every sequence (a N ) N ≥1 converging to a ∈ (0, 1), and if

(E θ [k (N ) n |k (N ) n-1 = 0]) N ≥1 converges to +∞: P θ k (N ) n < a N E θ [k (N ) n |k (N ) n-1 = 0] + (1 -a N )E θ [k (N ) n |k (N ) n-1 = 0] k (N ) n-1 = 0 -----→ N →+∞ 1 if θ = θ 0 if θ = θ .
Others conclusion can be drawn by the former proof, that generalizes the large game result which can be found in [START_REF] Rosenberg | Social Learning in OneArmed Bandit Problems[END_REF].

Proposition 3.6. For any sequence π i,N m ( t)

N ≥1
of equilibria such that

P(k (N ) n-1 = 0) -----→ N →+∞ 1 and E θ [k (N ) n |k (N ) n-1 = 0] -----→ N →+∞ +∞,
the cutos π i,N n-1 ( ) uniformly converge to p * , i.e.:

sup i∈{1,••• ,N } |π i,N n-1 ( ) -p * | -----→ N →+∞ 0.
Moreover there exists a sequence of real numbers (K N ) N ≥1 such that K N -----→ N →+∞ 0 and:

opt(q i n-1 ) ≥ ω i,N n-1 (p i n-1 , ) ≥ opt(q i n-1 ) -K N a.s.
Proof. According to the denition of p * , a player whose posterior belief q i n-1 is below p * should exit. Moreover if no player has left until the end of stage n -1, we have that

q i n-1 1-q i n-1 = P θ (k -i,N n-1 =0) P θ (k -i,N
n-1 =0)

p i n-1 1-p i n-1
. Consequently we can underestimate π i,N n-1 ( ):

π i,N n-1 ( ) 1 -π i,N
n-1 ( )

≥ P θ (k -i,N n-1 = 0) P θ (k -i,N
n-1 = 0)

p * 1 -p * ⇔ π i,N
n-1 ( ) ≥ p * P θ (k -i,N n-1 = 0) (1 -p * )P θ (k -i,N n-1 = 0) + p * P θ (k -i,N n-1 = 0)

. Now we want an overestimation, and for this we have to nd a cuto that makes player i optimistic enough to stay. In the former proof, we provided a strategy that guarantees at least a payo of opt(q i n-1 ) -K N , where

K N = 4δ(θ -θ) (1 -δ)(1 -γ) 2 E θ [k (N ) n |k (N ) n-1 = 0] -1
, and with γ ∈ [0, 1) and N large enough (see equation 6).

If our strategy yields a positive payo, player i has to stay. This is the case if q i n-1 ≥ p * + ∆ N , where

∆ N = 4δ(θ -θ) (1 -γ) 2 (θ -(1 -δ)θ) E θ [k (N ) n |k (N )
n-1 = 0] -1 .

A straightforward calculus leads us to the overestimation of π i,N n ( ) we were looking for:

π i,N n-1 ( ) ≤ P θ (k -i,N n-1 = 0)(p * + ∆ N ) P θ (k -i,N
n-1 = 0)(1 -p * -∆ N ) + P θ (k -i,N n-1 = 0)(p * + ∆ N ) .

Lemma 3.11. Let (Φ N ) be a sequence of equilibria such that P(k (N )

n-1 = 0) -----→ N →+∞ 0, and assume that π n-1 < p * . For every ρ > ρ * , there exists K > 0 and N 0 ≥ 1 such that: ∀N ≥ N 0 , ∀i ∈ {1, ..., N }, ∀ β -i ∈ { , n} N -1 s.t. # j ∈ {1, ..., N }\{i}, β j = ≥ N ρ,

P θ ( α -i,N n = β -i ) P θ ( α -i,N n = β -i ) ≤ e -KN .
Similarly, for every ρ < ρ * , there exists K > 0 and N 0 such that:

∀N ≥ N 0 , ∀i ∈ {1, ..., N }, ∀ β -i s.t. # j ∈ {1, ..., N }\{i}, α j = < N ρ :

P θ ( α -i,N n = β -i ) P θ ( α -i,N n = β -i ) ≥ e KN .
The proof of this lemma is in the appendix.

Let us now prove proposition 1.4.

Proof. First let us show the second condition in the denition of ADE.

We just have to show that P n-1,θ (k

(N ) n+1 < N ) -----→ N →+∞
0, because then:

P θ (k (N ) n+1 = N ) = 1 -P θ (k (N ) n+1 < N ) = 1 -P θ (k (N ) n+1 < N, k (N )
n-1 = 0) -P θ (k

(N ) n+1 < N, k (N )
n-1 = 0) ≥ 1 -P n-1,θ (k

(N ) n+1 < N )P(k (N ) n-1 = 0) -P θ (k (N ) n-1 = 0) -----→ N →+∞ 1.
We set ρ = Proof. Consider the game where each player is obliged to stay until stage n, and is still obliged to stay then if p i n-1 > π n-2 . This game is very similar to the original one, there still exists equilibria and all of them are in cuto strategy. In this new game, we have: P θ (i leaves at stage n|k (N ) n = 0, p i n-2 ) ≤ P θ (p i n-1 ≤ π n-2 |p i n-2 )

≤ P θ (p i n-1 ≤ π n-2 |p i n-2 = π n-2 ) = P θ f θ (X i n-1 ) f θ (X i n-1 ) ≤ 1 < 1.
As the equilibria are symmetric, players all play the same strategy and the probability under P θ (•|k

(N )
n-1 = 0) to leave at stage n for each of them is λ θ,N N (θ ∈ {θ, θ}). Moreover each decision only depends on private payos, which are independent across players conditionally to the state. Therefore the number of exits k .

This asymptotically equals a Poisson distribution:

P θ (k (N ) n = k|k (N ) n-1 = 0) = C k N λ θ,N N k 1 - λ θ,N N N -k = N (N -1) • • • (N -k + 1) N k (λ θ,N ) k k! 1 - λ θ,N N N 1 - λ θ,N N -k ∼ N →+∞ (λ θ,N ) k k! e N log 1- λ θ,N N ∼ N →+∞ (λ θ,N ) k k! e -λ θ,N .
This is clearly the case if µ is small enough and λ θ (λ θ -λ θ ) is large enough, e.g. λ θ = 10 and λ θ = 1 2 . As a conclusion, with these values of λ θ and with δ close enough to 1, all inequalities (I m ) hold so that there exists an ADE with delay n.

  Figure 1: λ θ = 1.1 λ θ = 0.9

F=

  n-1,θ (p * )+ρ * 2. As E θ [k = 0] ∼ N F n-1,θ (p * ) (lemma 3.10), and because ρ * is a convex combination of F n-1,θ (p * ) and F n-1,θ (p * ), remark 2 enables us to write:lim N →+∞ P n-1,θ k (N ) n ≤ N ρ = 0. (10)Then we have:P n-1,θ (k (N ) n+1 < N ) = P n-1,θ k (N ) n+1 < N, k (N ) n > N ρ + P n-1,θ k (N ) n+1 < N, k (N ) n ≤ N ρ ≤ P n-1,θ (k (N ) n+1 < N |k (N ) n > N ρ)P n-1,θ (k (N ) n > N ρ) + P n-1,θ (k (N ) n ≤ N ρ) ≤ P n-1,θ (k (N ) n+1 < N |k (N ) n > N ρ) + P n-1,θ (k (N ) n ≤ N ρ) As P n-1,θ (k (N ) n ≤ N ρ) -----→ N →+∞0, we focus on the other term. We use the basic idea that we mentioned before, i.e. the posterior belief of active player is necessarily greater than p * :P n-1,θ (k (N ) n+1 < N |k (N ) n > N ρ) = P n-1,θ ∃i ∈ {1, ..., N }, α i,N n+1 = k (N ) n > N ρ ≤ P n-1,θ ∃i ∈ {1, ..., N }, q i n ≥ p * and α i,N n = k (N ) n > N ρ ≤ N P n-1,θ q i n ≥ p * and α i,N n = k (N ) N P n-1,θ p i n 1 -p i n P θ ( α -i,N n = α) P θ ( α -i,N n = α) ≥ p * 1 -p * , α i,N n = k (N ) n > N ρ .The r.v. Y i m -v are upper bounded by a real M , and lower bounded by a real M . Using Hoeding's inequality we have (with N large enough to have N K > s):P θ (S i l ≤ s -KN -(l -n)y) ≤ exp -2(s -N K -(l -n)y) 2 (l -n)(M -M ) 2 .This leads us to the nal conclusion sincel≥n+1 N P θ (S i l ≤ s -KN -(l -n)y) ≤ l≥n+1 N exp -2(s -N K -(l -n)y) 2 (l -n)(M -M ) 2 ≤ l≥1 N exp -2(s -N K -ly) 2 l(M -M ) 2and by dominated convergence this converges to 0 as N → +∞. Now let us prove the second part of theorem 1.2.Proposition 3.12. If π n-1 < p * and if inequalities (I m ) (1 ≤ m ≤ n -1) hold, then there exists an ADE with delay n.

  of N independent Bernoulli r.v. with the same parameter λ θ,N N . So the distribution of k (N ) n is a binomial distribution:∀N ≥ 1, ∀k ∈ {0, ..., N }, P θ (k(N )

Acknowledgements

I am indebted to D. Rosenberg and N. Vieille (HEC Paris) for helpful discussions we had on this topic. Financial support from the ANR is also gratefully acknowledged.

Both sides of our estimation tends to p * . The convergence is uniform w.r.t. to i because P θ (k

n-1 = 0) ≤ 1. That gives us the rst part of the proposition. The fact we have a strategy that guarantees a payo of opt(q i n-1 )-K N implies that ω i n-1 (p i n-1 , ) ≥ opt(q i n-1 ) -K N by denition of ω i n-1 . The inequality opt(q i n-1 ) ≥ ω i n-1 (p i n-1 , ) is also a by-product of the denition of ω i n-1 (see section 3.1.2), hence the second part of the proposition.

Theorem 1.2, Necessary conditions

Our aim is to show that if there exists an ADE with delay n, then π n-1 ≤ p * and inequalities (I m ), 1 ≤ m ≤ n -1, hold. We will reach this goal by dividing the proof into simpler intermediate results.

Lemma 3.7. If there exists an ADE with delay n, then E θ [k (N ) n |k

Proof. We proceed using reductio ad absurdum. Up to a subsequence, E θ [k (N ) n |k

is bounded.

And we have:

n-1 = 0)P θ (k

{i stays at stage n} k

1 -F i n-1,θ (π i,N n-1 ( )) P θ (k

n-1 = 0), and

log 1 -F i n-1,θ (π i,N n-1 ( )) + log P θ (k

n-1 = 0) .

The sum has the same behaviour as -N i=1 F i n-1,θ (π i,N n-1 ( )), for we know that F i n-1,θ (π i,N n-1 ( )) ≤ β θ < 1 (see Lemma 3.4) so that, by concavity:

Combining these facts and the fact that P θ k

1, we get:

And in these conditions (see corollary 3.3) P θ (k

= 0) > α, so that we have:

0 by means of the third condition in the denition of ADE. Therefore we have:

And then:

for N large enough. In particular:

Up to a subsequence, one can assume that:

Consequently, we have

2 and by continuity:

As the private beliefs have the same support under P θ and under P θ , one can write:

Therefore, one have, for N large enough:

And then:

This contradicts the fact that P θ (k

Corollary 3.8. If there exists an ADE with delay n, then π n-1 ≤ p * .

Proof. This is a direct consequence of proposition 1.6 and lemma 3.7. Lemma 3.9. If there exists an ADE with delay n then the inequalities ( Ĩm ), 1 ≤ m ≤ n -1, hold.

Proof. Let us prove inequality ( Ĩm ). To this aim, we x an ADE with delay n and we overestimate the continuation payo that player i gets at stage m in such a strategic prole when no player has left, i.e. k (N ) m-1 = 0. Let us say that if any player leaves before stage n, player i could at best play in perfect accordance to the state: stay forever in the High state and drop out in the Low state . If not, he will stay in the game until stage n, and then stay i the optimal optimal continuation payo ω i,N n-1 (p i n-1 , α -i,N n-1 ) is positive (see section 3.1.2). The corresponding overestimation is the following:

, where

. We denote by f N m (p i m-1 ) this upper bound.

We have that {f N m (p i m-1 ) < 0} ∩ {k

m-1 = 0, player i prefers to leaves at stage m (which yields at payo of 0) because his continuation payo is non-positive. Consequently we have

and:

On the other hand the fact that P(k

, it also implies that:

Then thanks to lemma 3.7 and proposition 3.6 we have

, where:

This function is non-decreasing (see section 3.1.2). Consequently there is at most one value of p i m-1 for which f m (p i m-1 ) = 0, and because the law p i m-1 is continuous, we have:

Finally we have that P(k

1 and, up to a subsequence,

From this we deduce that:

The rst part of theorem 1.2 is then the conjunction of corollary 3.8 and lemma 3.9.

Theorem 1.2, Sucient conditions

To prove the second part of theorem 1.2, we rst need to show proposition 1.4, and before that we will begin by two useful lemmas. In proposition 1.4 we have P(k

0 and π n-1 < p * . After stage n, a signicant proportion of players have to leave because their private beliefs are less than p * , and this proportion depends on the state. That is the content of the following lemma. Lemma 3.10. Assume that π n-1 < p * . For any sequence

In particular

Proof. As in the proof of proposition 3.6, the fact that a player whose posterior belief is below p * will necessarily leave implies that:

.

Therefore we have:

converges to p * , and the convergence is uniform w.r.t. i because P θ (k

Consequently we have:

In particular E θ [k

+∞, and by means of proposition 3.6 the cutos π i,N n-1 ( ) uniformly converge to p * . Moreover we have that:

.

And:

Equations ( 8) and (9) together give the result we were looking for.

The basic idea is that, after the wave of exits, in the Low state q i n is mostly below p * so that any player will leave, and in the High state q i n is mostly high enough for all the future believes to be greater than p, so that any remaining player will stay forever. Remember that the posterior belief of player i (after stage n) is expressed by:

whenever the status of the players is α. This can also be written as:

.

The terms

1 and because of lemma 3.10 and proposition 3.6. This leads us to set ρ * such that :

Using convexity properties, it is readily seen that F n-1,θ (p * ) < ρ * < F n-1,θ (p * ). The real ρ * represents a critical fraction of players leaving at stage n above which the posterior beliefs will decrease exponentially to 0 and under which it will increase exponentially, as stated in the lemma below.

The fact that k (N ) n > N ρ and that i is still active implies that, for N large enough and for a given K > 0,

≤ e -KN by means of lemma 3.11. This enables us to write:

And then:

n-1 = 0

by means of Markov inequality. This last term converges to 0. Indeed we have:

• N e -KN -----→ N →+∞ 0,

1 (see equation ( 10))

by independence of payos conditionally to the state. We are then able to conclude that P θ (k

1, hence the second condition in the denition of ADE. Now, let us show the third condition. Similarly to equation (10) we have lim

. And, as in the former point, we just have to show that:

We use the fact that a player whose posterior belief is greater than p necessarily remains active:

.., N }, i leaves at stage l + 1 and k

Since

< N ρ, we can underestimate q i l 1-q i l using lemma 3.11 and corollary 3.3:

for N large enough and for a given K > 0. Consequently:

) (and r = 1) we get the same inequality as in Lemma 3.4, and all that was proven thereafter is still true with these new bounds. In particular, the fact that P(k (N ) n = 0) = 1 and that π n-1 < p * implies thanks to the previous theorem (1.4) that any sequence of equilibria is an ADE. Let (Φ N ) be a sequence of such equilibria. Our goal is to show that there exists N 0 such that (Φ N ) N ≥N 0 is a sequence of equilibria in the original game. First, thanks to lemma 3.10 and to proposition 3.6, the cutos π i,N n ( ) uniformly tend to p * . Inequality (I n-1 ) implies that π n-2 > p * (see section 3.1.2), so that the rule which compels player i to remain active if p i n-1 > π n-2 is still obeyed in the original game for N large enough. Now let us see if any player i is not tempted to deviate unilaterally by leaving at a stage m < n. If this player sticks to his strategy in the constrained game, he will remain active until stage n, and then stay i his continuation payo

) is positive (see section 3.1.2). In the constrained game we have

this implies that p i l = q i l (see section 3.1.1) and that α -i,N l = . This gives us the following underestimation of the payo that player i gets from stage m if he stays and follows his strategy in the constrained game:

By lemma 3.10 and propostion 3.6, we have

0 (irrespective to i). Consequently, by staying at stage m, player i can expect at least a payo of:

(1 + δ + ... + δ n-m-1 )myop(p i m-1 ) + δ n-m E max 0, opt(p i n-1 ) p i m-1 -δ n-m K N As mentioned in section 3.1.2 this lower bound is nearly the left side of inequality (I m ) and is increasing in p i m-1 . Consequently, it is non-negative for N large enough, and player i is right to stay at stage m because leaving would yield a payo of 0.

To conclude the results about ADE, note that the proof of corollary 1.3 can be found in the appendix. Our last proof deals with other asymptotic equilibria.

Theorem 1.5

Proof. Let (Φ N ) be a sequence of symmetric equilibria such that P(k (N ) = 0) is bounded away from 1 and λ θ,N is bounded away from zero. We can also assert that P θ (k

is measurable w.r.t. the p i m (1 ≤ i ≤ N and 1 ≤ m ≤ n -1) and the p i m have the same support under P θ and P θ . Therefore λ N,θ > 0 for N large enough.

Appendix

Proof of Lemma 3.1

Proof. As the link between p i k and the likelihood ratio

Combining this with (12), we get:

Using similar arguments, we nd that P θ (x ) ≥ x P θ (x ).

Then : P θ (x )P θ (x) -P θ (x)P θ (x ) ≥ 0, and the result follows.

Proof of lemma 3.11

Proof. First notice that the function

uniformly converges to F n-1,θ as N → +∞. Indeed, on the one hand we have that:

On the other hand we have:

Similarly, the function

is increasing. Consequently, by denition of ρ * , we have:

Because of the uniform convergences mentioned above and by continuity of F n-1,θ , one can choose K in 0, -ρ log

By lemma 3.10 and proposition 3.6, one can also choose N 0 large enough such that:

∀N ≥ N 0 , ∀j ∈ {1, ..., N }, p * -≤ π N,j n-1 ( ) ≤ p * + .

Then, for all N ≥ N 0 :

= j =i|p j n-1 <π N,i n-1 ( ) log g N,θ (π N,j n-1 ( ), j) g N,θ (π N,j n-1 ( ), j) + j =i|p j n-1 ≥π N,j n-1 ( ) log h N,θ (π N,j n-1 ( ), j) h N,θ (π N,j n-1 ( ), j)

≤ #{j = i| p j n-1 < π N,j n-1 ( )} log , where j N 0 = argmax j =i| p j n-1 <π N,j n-1 ( ) g N,θ (π N,j n-1 ( ),j) g N,θ (π N,j n-1 ( ),j)

and j N 1 = argmax j =i| p j n-1 <π N,j n-1 ( ) h N,θ (π N,j n-1 ( ),j) h N,θ (π N,j n-1 ( ),j)

.

Then, thanks to equation (13) we have:

≤ N ρ log g N,θ (π N,j N 0 n-1 ( ), j N 0 )

g N,θ (π N,j N 0 n-1 ( ), j N 0 )

+ N (1 -ρ) log h N,θ (π

h N,θ (π

1-p 0 . If there exists an ADE with delay n ≥ 2, we have π n-1 < p * ≤ π n-2 which equivalent to µ n-1 p 0 1-p 0 < p * 1-p * ≤ µ n-2 p 0 1-p 0 . To ensure the relation, we set the following equality between the settings of the game:

As suggested in section 1.5, we x all the settings of the games except for p 0 and δ and we show that, when δ is close enough to 1 and under certain circumstances, all the inequalities


Fabrice Rossi

Nathalie Villa

Consistency of Derivative Based Functional Classifiers on Sampled Data

In some applications, especially spectrometric ones, curve classifiers achieve better performances if they work on the m-order derivatives of their inputs. This paper proposes a smoothing spline based approach that give a strong theoretical background to this common practice.

Introduction

Spectrometric data are one particular case of functional data [START_REF] Ramsay | Functional Data Analysis[END_REF]: while each spectrum could be considered as a high dimensional vector, it has been shown that a more appropriate model is to view it as a sampled function [START_REF] Alsberg | Representation of spectra by continuous functions[END_REF][START_REF] Frank | A statistical view of some chemometrics regression tools[END_REF]. One of the first benefits of this functional approach was to solve the difficulties faced by linear methods when confronted to the highly correlated variables resulting from a fine grid sampling of smooth functions (see [START_REF] Ramsay | Functional Data Analysis[END_REF] for a comprehensive presentation of linear methods for functional data).

On a theoretical point of view, Functional Data Analysis (FDA) departs from standard multivariate data analysis in one crucial point: the real data are not the finite dimensional vector representations but the underlying functions. For instance, in the particular case of spectral data, FDA focuses on the underlying spectra, not on their sampling via the spectrometer. As a consequence, standard multivariate consistency theorems cannot be directly applied to FDA. While the functional approach works quite well in practice (see, e.g., [START_REF] Ferraty | The functional nonparametric model and application to spectrometric data[END_REF][START_REF] Rossi | Representation of functional data in neural networks[END_REF]), empirical evidences of success are not sufficient to guarantee its soundness.

Several recent works tackle this problem, mainly by proving that some algorithms are consistent in the sense that they asymptotically estimate E (Y |X) (where X and Y are respectively a functional valued and a real valued random variable) from a learning set, or that they reach the Bayes risk in the limit. A comprehensive presentation of the capabilities of non parametric kernel based regression estimators for functional predictors can be found in [START_REF] Ferraty | NonParametric Functional Data Analysis[END_REF]. In the case of classification, recent results include [START_REF] Biau | Functional classification in Hilbert spaces[END_REF] that proposes a universal consistency result for k-nearest neighbors classifier and [START_REF] Rossi | Support vector machine for functional data classification[END_REF] which extends those results to Support Vector Machine (SVM). However, none of those consistency results covers some important aspects of the FDA methodology, namely the use of functional pre-processing. In spectrometric applications, it is quite common, for instance, to replace functions by their first or second derivatives, as this allows to focus on curvature rather than on the actual values taken by the functions. This improves prediction performances in certain situations (see e.g. [START_REF] Ferraty | The functional nonparametric model and application to spectrometric data[END_REF][START_REF] Rossi | Representation of functional data in neural networks[END_REF][START_REF] Rossi | Support vector machine for functional data classification[END_REF]). Another limitation is that most of the theoretical results assume perfect knowledge of the observed curves and do not take into account sampling (see [START_REF] Rossi | Functional multi-layer perceptron: a nonlinear tool for functional data analysis[END_REF][START_REF] Berlinet | Functional classification with wavelets[END_REF] for examples of results on sampled functions).

This paper addresses both limitations via smooth spline representations of the sampled functions. The remainder of this paper is organized as follows: Section 2 introduces the general setting and outlines the proposed solution. Section 3 gives details about smoothing splines while Section 4 gives the main consistency result.

Setup and notation

We consider a binary classification problem given by the pair of random variables (X, Y ), where X takes values in a functional space X , and

Y in {-1, 1}. A learning set S n,d is constructed via n i.i.d. copies of (X, Y ), the {(X i , Y i )} n i=1
and via a non-random sampling grid

1 of finite length |τ d |, τ d = (t l ) |τ d | l=1 . It consists in the n pairs (X τ d i , Y i ), where X τ d i = X i (t 1 ), . . . , X i t |τ d | T ∈ R |τ d | . From S n,τ d , one builds a classifier φ n,τ d whose mis-classification probability is given by L(φ n,τ d ) = P (φ n,τ d (X τ d ) = Y |S n,τ d ) .
The classifier is consistent if L(φ n,τ d ) asymptotically reaches the Bayes risk for the original functional problem

L * = inf φ: X →{-1,1} P (φ(X) = Y ).
Obviously, one cannot hope to find a consistent classifier without some regularity assumptions on the functions. Indeed if X takes arbitrary values in L 2 ([0, 1]) then the actual value of X(t l ) is not precisely defined. To solve this problem, [START_REF] Rossi | Functional multi-layer perceptron: a nonlinear tool for functional data analysis[END_REF] works on continuous functions while [START_REF] Berlinet | Functional classification with wavelets[END_REF] uses more technical but related regularity assumptions. The present paper targets situations in which the derivatives of the functions convey more information than the functions themselves. It is therefore natural to assume that the functional space X contains only differentiable functions. More precisely, for m > 3 2 , X is the Sobolev space H m of functions from L 2 ([0, 1]) for which D j h exists in the weak sense for all j ≤ m and such that D m h ∈ L 2 ([0, 1]), where D j h is the j-order derivative of h (also denoted h (j) ). Any real interval can be used instead of [0, 1].

The method proposed in this paper relies on smoothing spline representations of the unobserved functions. More precisely, let us consider x ∈ H m sampled on the aforementioned grid. A smoothing spline estimate of x is the solution of

x λ,τ d = arg min h∈H m 1 |τ d | |τ d | l=1 (x(t l ) -h(t l )) 2 + λ 1 0 (h (m) (t)) 2 dt, (1)
where λ > 0 is a regularization parameter that balances interpolation errors and smoothness (measured by the L 2 norm of the m-order derivative of the estimate). The goal of this paper is to show that, under reasonable hypothesis, a classifier built on x T .

Those results stand as a consequence of several major properties of the smoothing splines: they asymptotically estimate the underlying function that generates the sampled curve, there is a one-to-one mapping between x λ,τ d and x = (x(t 1 ), . . . , x(t |τ d | )) T and the L 2 -norm of the derivatives of x λ,τ d can be deduced from the norm of x.

3 Smoothing splines and differentiation kernels

RKHS and smoothing splines

As the goal is to work on x (m) λ,τ d , it might seem natural to consider H m with the metric induced by the inner product (u, v) → 1 0 u (m) (t)v (m) (t)dt. However, a slightly different structure is needed to ensure consistency. It is obtained by decomposing H m into H m = H m 0 ⊕ H m 1 [START_REF] Kimeldorf | Some results on Tchebycheffian spline functions[END_REF], where H m 0 = Ker D m = P m-1 (the space of polynomial functions of degree less or equal to m -1) and H m 1 is an infinite dimensional subspace of H m defined via m boundary conditions. The boundary conditions are given by a full rank linear operator from H m to R m , denoted B = (B j ) m j=1 , such that Ker B ∩ P m-1 = {0}. Then,

u, v m 1 = D m u, D m v L 2 = 1 0 u (m) (t)v (m) (t)dt is an inner product on H m 1 . Moreover, u, v m 0 = m j=1 B j uB j v is an inner product on H m 0 .
Then a combined inner product on H m is given by

u, v H m = 1 0 u (m) (t)v (m) (t)dt + m j=1 B j uB j v. (2)
Equipped with ., . H m , H m is a Reproducing Kernel Hilbert Space (RKHS, see e.g. [START_REF] Berlinet | Reproducing Kernel Hilbert Spaces in Probability and Statistics[END_REF]). The metric induced by ., . H m consists in comparing functions based almost only on their m-order derivatives, up to a correction based on the boundary conditions. The most classical boundary conditions are given by B j h = h (j) (0), 0 ≤ j ≤ m -1, but others can be used [START_REF] Berlinet | Reproducing Kernel Hilbert Spaces in Probability and Statistics[END_REF] depending on the application.

Splines and sampled functions

Now, we need to link u λ,τ d , v λ,τ d H m with u = (u(t 1 ), . . . , u(t |τ d | )) T and v = (v(t 1 ), . . . , v(t |τ d | )) T . This can be done via a theorem from [START_REF] Kimeldorf | Some results on Tchebycheffian spline functions[END_REF]. Compatibility assumptions between the sampling grid τ d = (t l )

|τ d | l=1 is such that: 1. |τ d | ≥ m -1 2. sampling points are distinct with 0 ≤ t 1 < • • • < t |τ d | ≤ 1 3. the m boundary conditions B j are linearly independent from the |τ d | linear forms h → h(t l ), for l = 1, . . . , |τ d | (defined on H m )
Then, using a theorem from [START_REF] Kimeldorf | Some results on Tchebycheffian spline functions[END_REF], one can show 2 the following corollary:

Corollary 1. Under Assumption 1 there is a one-to-one bi-continuous mapping between u and u λ,τ d . In addition, there is a symmetric and positive definite matrix M τ d such that for any u = (u(t 1 ), . . . , u(t

|τ d | )) T and v = (v(t 1 ), . . . , v(t |τ d | )) T in R |τ d | , u λ,τ d , v λ,τ d H m = u T M τ d v. (3)
This corollary defines an inner product on R d which is equivalent to the one chosen on ., . H m . It is therefore possible to work implicitly on the m-order derivatives of the spline representation of sampled functions only by replacing the canonical Euclidean inner product by the one associated to M τ d . In practice, this is done simply by multiplying the sampled functions by

Q τ d , the Cholesky decomposition of M τ d (Q T τ d Q τ d = M τ d )
prior to submitting the obtained vectors to any consistent classification method (see Section 4.3).

Consistency

Spline approximation

¿From the sampled random function X(t 1 ), . . . , X(t |τ d | ), one can reconstruct at best X λ,τ d . To ensure consistency, X λ,τ d must be showed to converge to X. This problem has been studied extensively (see, e.g., [START_REF] Cox | Multivariate smoothing splines functions[END_REF]). Convergence is linked to a well chosen sampling grid, as a badly designed one would not convey in x enough information to recover x. As general hypothesis on the sampling grids are very technical, we limit ourselves in the present paper to a simple particular case:

x λ |τ d | ,τ d -x 2 L 2 = O |τ d | -2m/(2m+1) .
Similar results are also available for the derivatives up to order m (included).

Conditional expectation approximation

L * H m ,τ d = inf φ: H m →{-1,1} P (φ( X λτ d ,τ d ) = Y ).
We have the following corollary:

Corollary 2. Under Assumptions 1 and 2, if

1. E( D m X 2 L 2 ) is finite, 2. or τ d ⊂ τ d+1 , then lim |τ d |→∞ L * H m ,τ d = L * .
Each condition corresponds to a specific proof. Condition 1 uses a general result from [START_REF] Faragó | On the continuity of the error distortion function for multiplehypothesis decisions[END_REF] and a more precise version of Theorem 1 (which relates the convergence speed with the L 2 norm of the m-order derivative of the functions). Condition 2 uses the martingale approach proposed in [START_REF] Biau | Functional classification in Hilbert spaces[END_REF] together with Theorem 1 (this generalizes the results from [START_REF] Villa | Un résultat de consistance pour des svm fonctionnels par interpolation spline[END_REF]).

Wrapping up the results

Let us now consider any consistent classification algorithm for standard multivariate data, such as e.g., Support Vector Machines [START_REF] Steinwart | Support vector machines are universally consistent[END_REF] or Multi-Layer Perceptrons [START_REF] White | Connectionist nonparametric regression: Mutilayer feedforward networks can learn arbitrary mappings[END_REF]. Let us denote φ n,τ d the classifier obtained with this algorithm on the learning set

(Q τ d X τ d i , Y i ) n i=1
. We have the following theorem: Theorem 2. Under the assumptions of Corollary 2 and any additional assumptions needed by the multivariate algorithm,

lim |τ d |→∞ lim n→+∞ E (L * (φ n,τ d )) = L * .
The proof is based on the following steps. First, as Q τ d is a one-to-one continuous mapping, a consistent classifier on (Q In addition to being consistent, this scheme is also "derivative based". Indeed, as shown by Corollary 2

τ d X τ d i , Y i )
Q τ d (u -v) 2 R |τ d | = u λ,τ d -v λ,τ d 2 H m .
Therefore, a classifier constructed on the Q τ d X τ d i compares the underlying functions via the metric induced by the inner product of equation [START_REF] Berlinet | Functional classification with wavelets[END_REF], that is mainly via the m-order derivatives of those functions, up to the boundary conditions. It gives therefore a theoretical background to the common practice of using derivatives for some spectrometric problems [START_REF] Ferraty | The functional nonparametric model and application to spectrometric data[END_REF][START_REF] Rossi | Representation of functional data in neural networks[END_REF][START_REF] Rossi | Support vector machine for functional data classification[END_REF] and more generally in functional data analysis.

  d is a consistent classifier. The proof is based on two steps. The first step constructs an inner product in R |τ d | which can be used to approximate inner products performed on x (m) λ,τ d using the sampled function only. The second step shows that the Bayes risk associated to ( X λ,τ d , Y ) converges to the Bayes risk of the original pair (X, Y ), where X λ,τ d is the solution of equation (1) for the sampled function X τ d = X(t 1 ), . . . , X(t |τ d | )

Assumption 1 .

 1 |τ d | l=1 and the boundary conditions operator B are needed: The sampling grid τ d = (t l )

Assumption 2 .

 2 For each d, the sampling grid τ d = (t l ) |τ d | l=1 is uniformly spaced. Then we have: Theorem 1 ([5]). Under Assumption 2, for λ |τ d | = O |τ d | -2m/(2m+1) ,

Theorem 1

 1 can be used to relate the Bayes risk for the classification problem (X, Y ) to the one for ( X λτ d ,τ d , Y ) when |τ d | goes to infinity, i.e. L * to

n

  i=1 is also a consistent classifier on (Xτ d i , Y i ) n i=1 . As the chosen algorithm is consistent, E (L * (φ n,τ d )) converges with n to L * τ d = inf φ: R d →{-1,1} P (φ(X τ d ) = Y ).According to Corollary 1, the mapping between X τ d and X λτ d ,τ d is also one-to-one and bi-continuous. Therefore L * τ d = L * H m ,τ d . Corollary 2 gives the conclusion.

the sampling points depend on d and should therefore be denoted t d l but this would clutter the notations.