Sebastian Bervoets
email: sebastian.bervoets@univ-amu.fr.

Mathieu Faure
email: mathieu.faure@univ-amu.fr.

Stability in Games with Continua of Equilibria

Keywords: Best-Response Dynamics, Public Good games, Stability. JEL Codes: C62, C73, D83, H41

)), and where, as we show, continua of equilibria often appear. We provide necessary and sufficient conditions for a component of Nash equilibria to be asymptotically stable vis-à-vis the best-response dynamics. Interestingly, we demonstrate that these conditions relate to the structure of the network in a simple way. We also provide corresponding results for several dynamical systems related to the best response.

Introduction

The recent literature on games played by individuals who interact on social networks has highlighted the relationships between Nash equilibria and the structure of the network (see for instance [START_REF] Jackson | The economic consequences of social network structure[END_REF]). One important contribution is [START_REF] Bramoullé | Public goods in networks[END_REF]. The authors focus on public goods games played on networks, where best responses are linear, actions are strategic substitutes and individuals' payoffs depend on the sum of neighbors' actions. They analyze the set of Nash equilibria and find that despite multiplicity, only very few Nash equilibrium action profiles are stable, where stability refers to the asymptotic stability of the discrete-time best-response dynamics. The authors reiterate their analysis with a more general class of games in [START_REF] Bramoullé | Strategic interaction and networks[END_REF], using the continuous-time best-response dynamics (thereafter, BRD).

1

In this paper we extend and complement their analysis by comprehensively analyzing stability in these games. As we show, the set of Nash equilibria is a finite union of connected components. In the aforementioned papers, the authors focused on isolated equilibria1 , which are specific types of components. However, as we show, these components generally form a continuum of equilibria (section 2). In this paper, we consider all types of equilibria.

We use the concept of stability of sets standard in the dynamical systems literature (see for instance [START_REF] Conley | Isolated Invariant Sets and the Morse Index[END_REF]), i.e. the concept of attractor. In economics, it was introduced by [START_REF] Weibull | Evolutionary game theory[END_REF] under the name of asymptotically stable sets, by contrast with asymptotically stable points. Being an asymptotically stable point and being an attractor are equivalent for isolated equilibria. However, no point can be asymptotically stable in a continuum of equilibria, since any neighborhood of that point contains another Nash equilibrium. Yet the entire component might be an attractor.

Identifying attractors is challenging for at least two reasons. First, there are no general algebraic tools available. In the case of isolated equilibria, the nature of the Jacobian matrix informs us about its stability. However, this does not work for continua. As [START_REF] Seade | The stability of cournot revisited[END_REF] puts it in his paper on stability of Nash equilibria in the Cournot oligopoly problem, "Things would get trickier (...) if equilibria happened not to be regular, that is not even locally unique, isolated. This, one can dismiss as a non-generic, 'unlikely' occurrence, although that is often a risky stand to take." In this paper, we tackle the issue in a context where the 'unlikely' occurrence is generic.

Second, there are no general results to be relied on concerning the best-response dynamics. It may or may not converge, depending on the game played. In discrete-time versions and/or in games with discrete action space, it is known that the dynamics can diverge; in continuous games, the vivid debate about stability of the Cournot solution (see i.a. [START_REF] Theocharis | On the stability of the cournot solution on the oligopoly problem[END_REF], [START_REF] Fisher | The stability of the cournot oligopoly solution: The effects of speeds of adjustment and increasing marginal costs[END_REF], [START_REF] Hahn | The stability of the cournot oligopoly solution[END_REF], [START_REF] Seade | The stability of cournot revisited[END_REF] and al [START_REF] Al Nowaihi | The stability of the cournot oligopoly model: a reassessment[END_REF]) illustrates how the behavior of the best-response dynamics finely depends on the parameters of the game. Even in very structured games such as potential games, additional conditions are needed to guarantee convergence (see [START_REF] Kukushkin | Cournot tatonnement and potentials[END_REF]).

The games we focus on are best-response potential games (see [START_REF] Voorneveld | Best-response potential games[END_REF]), and we show that attractors correspond to the local maximisers of that potential function (as in [START_REF] Sandholm | Potential games with continuous player sets[END_REF]). We also show that attractors are always included in the set of Nash equilibria, and correspond to sets where every point is a local maximum of the potential (section 3).

In section 4, we consider the public good game where actions are perfect substitutes and obtain two results that completely characterize the set of attractors. First, we identify necessary and sufficient conditions for a Nash equilibrium to be a local maximum of the potential. These conditions relate in a simple and tractable way to the topology of the network: either the subgraphs of agents exerting an effort are all complete subgraphs and the Nash equilibrium is a local maximum, or at least one is not complete and the equilibrium is not a local maximum. This property is nice because, although hard to establish, it is easy to check.

Second, our main theorem provides necessary and sufficient conditions for a set of Nash equilibria to be an attractor. First, every attractor must contain some specialized Nash equilibria, i.e. equilibria in which individuals are either active and exert the autarkic effort, or inactive and exert no effort at all. Second, a component of Nash equilibria is an attractor if and only if the specialized equilibria that it contains are themselves local maxima of the potential. Thus, however complex the components of Nash may be, one simply needs to focus on their "extreme points". The previous result already provides the condition determining whether a specialized equilibrium is a local maximum or not. This theorem is a sharp result that provides an algorithmic method to find the attractors.

One corollary is that at least one stable component exists for every network: any component containing a maximum independent set2 of the network is stable. This is an important departure from [START_REF] Bramoullé | Public goods in networks[END_REF], who often find no stable equilibria because of their focus on isolated equilibria. Further, we find the same result as them in the case of isolated equilibria: they obtain that an -isolated -equilibrium is stable for the discrete best-response dynamics if and only if it is specialized and the set of active players forms a maximal independent set of order at least two. When equilibria are isolated, our condition is equivalent to theirs.

In section 5 we turn to the public good game with imperfect substitutes. Although we do not get as sharp a result as for the case with perfect substitutes, we extend the results of [START_REF] Bramoullé | Strategic interaction and networks[END_REF], where the authors restrict their attention to Nash equilibria in which there are no weakly inactive agents, i.e. agents who do not produce any effort but are just on the verge of doing so3 . They identify the lowest eigenvalue of the subgraph of active agents as the determinant of the stability of a Nash equilibrium. We obtain this result and we also consider Nash equilibria in which agents can be weakly inactive.

When interactions are low, i.e. substitutes are very imperfect, a Nash equilibrium will always be a local maximum of the potential (and hence stable if it is isolated), which will never be true if interactions are high. However, we identify a range of intermediate interaction values for which the analysis gets complex. When an equilibrium falls within that range, we provide two different necessary and sufficient conditions for an equilibrium to be a local maximum of the potential.

The first condition amounts to saying that an equilibrium is a local maximum if and only if the set of active agents cannot be reduced. The second condition considers acceptable action profiles, i.e. action profiles such that no one exerting an effort has an aggregate level of contribution that exceeds his autarkic effort. Acceptable action profiles naturally contain Nash equilibria, but not only. The condition then states that an equilibrium is a local maximum if and only if the sum of efforts in that equilibrium is always greater than the sum of efforts in any acceptable action profile on the set of active and weakly inactive agents. Although these conditions are less easy to interpret than those on perfect substitutes, they still provide valuable insights as well as an algorithmic way of determining whether a set is an attractor.

Finally, in section 6, we investigate several alternative dynamical systems which rely on a best response principle. First, we provide sufficient conditions for any continuous-time dynamical system to share the same set of attractors. Second, we focus on three different discrete-time dynamics. We show that the asymptotic behavior of these systems is quite sensible to the features of the dynamics: the set of attractors is the same as for the (BRD) as long as the discrete systems are either sequential or "smooth" in some sense, while it might differ if agents simultaneously "jump" far away from their current position at each step.

2 The local public good game and structure of Nash equilibria

The local public good game

Consider a game G = (N , X, u), where N = {1, . . . , N } is the set of players, X i ⊂ R is a continuous action space and X = × i=1,...,N X i . An action x i ∈ X i can be thought of, for instance, as an effort level chosen by individuals, a price set by a firm, a monetary contribution to a public good. Because in all these examples actions take positive values, we will assume that X i = [0, +∞[. As usual, X -i denotes the set of action profiles of every agent except agent i: X -i = × j =i X j . Finally, u = (u i ) i=1,...,N is the vector of payoff functions. We assume that the payoffs have a network structure in the following sense: there exists an undirected graph G whose vertices are the agents and whose edges represent interactions4 . We denote by Gx the product between matrix G and vector x, and (Gx) i represents it's i-th coordinate: (Gx) i = j∈N i (G) x j , where N i (G) is the set of neighbors of agent i. We consider games with payoff functions u that have unique best responses of the following form

∀i ∈ N , Br i (x -i ) = max {1 -δ(Gx) i , 0} . (1)
where δ ∈ R + represents the rate of substitutability between agents' actions. When δ is equal to one, actions are perfect substitutes between neighbours, while δ equal to zero is the case of autarky. These games exhibit strategic substitutes and best responses depend only on the sum of neighbors' action. The set of games that have best responses of the form (1) is denoted G δ L (where the L stands for "linear"). A prominent member of this class is the game of local public goods introduced in [START_REF] Bramoullé | Public goods in networks[END_REF]. It is the game that we will focus on in this paper. The payoff function is

u i (x) = b (x i + δ(Gx) i ) -cx i (2)
where c > 0 is the marginal cost of effort and b(.) is a differentiable, strictly increasing concave function such that b (1) = c. Further examples of games in G δ L are discussed in [START_REF] Bramoullé | Strategic interaction and networks[END_REF]. The authors show that a specific game in the class G δ L is a potential game, where the potential function P is the one identified in [START_REF] Monderer | Potential games[END_REF], as an exact potential for the Cournot competition game:

P (x) = x, 1 - 1 2 x 2 - 1 2 x, δGx . (3)
Although this function does not serve as an exact potential for the local public good game defined by (2), any game in G L is a best-response potential game with potential P , as introduced in [START_REF] Voorneveld | Best-response potential games[END_REF]. That is Argmax

x i ∈X i P (x i , x -i ) = Br i (x -i ).

Nash equilibria

For games in G δ L , the set of Nash equilibria (NE) is easy to describe:

x * ∈ N E ⇔ ∀i, x * i = max {1 -δ(Gx * ) i , 0} .
Thus, either the neighbors of i provide less than 1/δ and i fills the gap to reach 1, or else they provide more and i enjoys the benefits without exerting any effort.

In the following definitions we adapt the terminology of [START_REF] Bramoullé | Public goods in networks[END_REF]. For an action profile x ∈ X, let A(x) be the set of players that are active, i.e. A(x) := {i : x i > 0}; let I(x) be the set of inactive agents, i.e. the set of agents i such that x i = 0. This set contains the subset W I(x) of weakly inactive agents (those for who δ(Gx) i = 1) and the subset SI(x) of strictly inactive agents (those for who δ(Gx) i > 1). Note that if x is a Nash equilibrium, then {A(x), W I(x), SI(x)} forms a partition of N .

Definition 1 An action profile x is specialized if x i = 1 for all i ∈ A(x). If x is specialized and is a Nash equilibrium, x is called a Specialized Nash equilibrium. An action profile x is distributed if A(x) = N . Now we describe through examples the different kinds of equilibria that exist in this class of games. We start with the simplest possible network, the pair in the case of perfect substitutes, i.e. δ = 1. The profile (1, 0) (where x 1 = 1 and x 2 = 0) is a specialized Nash equilibrium, together with the profile (0, 1), while ( 1 3 , 2 3 ) is a distributed Nash equilibrium. In fact, any profile of the form (α, 1α), with 0 ≤ α ≤ 1, is a Nash equilibrium. We say that the graph supports a continuum of equilibria, represented by the connected component

Λ = {(α, 1 -α) : α ∈ [0, 1]}. Definition 2 A connected set Λ ⊂ N E is a connected component of Nash Equilibria if and only if there exists an open neighborhood U of Λ such that U ∩ N E = Λ. A Nash equilibrium x is isolated if the connected component that contains x is a singleton.
Connected components of Nash equilibria can be singletons. Consider for instance the kite network of Figure 1. Here, when δ = 1 the profiles (1, 0, 1, 0) and (1, 0, 0, 1) are specialized Nash equilibria, they belong to the connected component Λ

1 = {(1, 0, β, 1 -β) : β ∈ [0, 1]},
which is a continuum of equilibria. However, the profile (0, 1, 0, 0) is also an equilibrium, it does not belong to a continuum. Its component is a singleton: Λ 2 = {(0, 1, 0, 0)}. In this case, we say that the equilibrium is isolated. The darkest the circle, the highest the action played. In particular, circles in black represent players playing 1. Left panel: a continuum of equilibria; right panel: an isolated equilibrium.

Proposition 1 The set of Nash equilibria can be described as

N E = ∪ L l=1 Λ l
where every Λ l is a connected component of NE.

Note that since the connected components are disjoint, the family {Λ l } l∈{1,...,L} forms a partition of the set of Nash equilibria.

In the examples we have provided, the continuum is one-dimensional because it involves only two agents. However, in general, continua are much more complex objects. For instance,

α -γ γ α 1 -2α 1 -2α β α -β α - Figure 2: An example with a four-dimensional continuum: α ≤ 1/2, β ≤ α, γ ≤ α, ≤ α.
for δ = 1, the following network with 9 players exhibits a four-dimensional continuum (Figure 2). In fact, the existence of continua of equilibria seems to be the rule rather than an exception. We now provide some insight on this.

Definition 3 Given an undirected graph G, a subset of nodes M is a maximal independent set if

(i) ∀i ∈ M , N i (G) ∩ M = ∅; (ii) ∀j / ∈ M , N j (G) ∩ M = ∅ A maximal independent set is of order k ∈ N * if we have min j / ∈M |N j (G) ∩ M | = k.
For instance, the network of Figure 1 has three maximal independent sets: {1, 3}; {1, 4}; {2}.

Remark 1 [START_REF] Bramoullé | Public goods in networks[END_REF]) Let M be a maximal independent set of the graph G. Then the effort profile in which

x i = 1 if i ∈ M and x i = 0 if i / ∈ M is a specialized
Nash equilibrium of the game with δ = 1. This is true in fact for any δ ≥ 1.

Although we were unable to state necessary and sufficient conditions for a network to support a continuum of equilibria, we have identified the following simple and useful sufficient condition. This condition is not necessary however. Consider the 6-agents circle network . This network supports a continuum of equilibria, although the maximal independent sets are {1, 4}, {2, 5}, {3, 6}, {1, 3, 5} and {2, 4, 6} and thus no pair satisfies the conditions of Proposition 2.

This proposition is useful because it gives an operational method to test for the existence of continua in a network, since many algorithms exist in order to find maximal independent sets. We ran tests on all distinct graphs ranging from N = 4 to N = 10. Results are reported in Table 1. 5These ratios, which are lower bounds, suggest that the fraction of graphs supporting a continuum of equilibria goes to 16 . This also underlines the importance of focusing on components of equilibria rather than isolated equilibria.

3 Dynamics and stability

Continuous-time best-response dynamics

As mentioned earlier, several dynamical systems are analyzed. In this section we focus on the continuous-time best-response dynamics (thereafter, (BRD)), which is a well-known learning process where all players simultaneously revise their strategies in the direction of their best response to the current action profile. As seen in ( 1), best responses are unique. Let Br : X → X, x → Br(x) := (Br 1 (x -1 ), ..., Br n (x -n )). The (BRD) is given by the following dynamical system:

ẋ(t) = -x(t) + Br(x(t)) (4)
The map Br(.) being Lipschitz, the ordinary differential equation (4) has a unique solution curve starting from every initial condition in R N . Because we restrict attention to X = R N + instead of R N and to positive times (t ≥ 0), we consider the semi-flow

ϕ : (x, t) ∈ X × R + → ϕ(x, t) ∈ X, (5)
where, for t ≥ 0, ϕ(x, t) is the unique solution of (4) at time t, with initial condition x ∈ R N + .

Attractors and local maximizer sets

Since we are interested in the stability properties of sets, the concept we use is that of attractors. Attractors were first defined in [START_REF] Conley | Isolated Invariant Sets and the Morse Index[END_REF] and were introduced in economics by [START_REF] Weibull | Evolutionary game theory[END_REF] under the name of asymptotically stable sets. Let V : X → R N be a Lipschitz map.

Definition 4 (Attractor) A ⊂ X is an attractor for ẋ = V (x) if and only if (ii) there exists an open neighborhood U of A with the following property:

(i) A is compact and invariant 7 ,
∀ > 0, ∃T > 0 such that ∀x ∈ U, ∀t ≥ T, d(ϕ(x, t), A) < ,
An attractor for a dynamical system is a set with strong properties. In particular, it uniformly attracts a neighborhood of itself. This notion extends to sets the concept of asymptotic stability that applies to points8 . Now, we show that only sets of Nash equilibria can be attractors, and that attractors are related to local maxima of the potential function.

Lemma 1 The potential P defined in (3) is a strict Lyapunov function for ẋ = -x + Br(x), that is the map t ∈ R + → P (ϕ(x, t)) is strictly increasing, for any x /

∈ N E. Furthermore, if

x and y are two Nash equilibria belonging to the same component Λ, then P (x) = P (y).

Note that this lemma implies that any local maximum of P is a Nash equilibrium. In particular, a global maximum of P is also a Nash equilibrium. Now we make sure that only Nash equilibria are candidates to be rest points of the dynamics. Let ω(x) be the omega limit set of x (i.e. the set of points where the flow goes as time goes to infinity, when starting at point x). We have the following9 : Lemma 2 ∀x ∈ X, the set ω(x) is nonempty and contained in a connected component of Nash equilibria.

One interesting feature of games in the class G δ L is that the potential P , defined in equation (3), is strictly increasing along solution trajectories of the dynamics ẋ = -x + Br(x) with initial conditions outside the set of Nash equilibria. Thus an isolated equilibrium is an attractor for the best-response dynamics if and only if it is a strict local maximum of the potential. Because we are interested in non-trivial components of Nash equilibria, we need to consider the more general notion of local maximizer set: Definition 5 Let Λ ⊂ X be connected and compact. We say that Λ is a local maximizer set of P if P is constant on Λ and there exists an open neighborhood U of Λ such that P (x) > P (y) for any x ∈ Λ, y ∈ U \ Λ.

In the appendix, we show (see Lemma 4) that a connected component Λ of Nash equilibria is a local maximizer set of P if and only if ∀x ∈ Λ, x is a local maximum of P . As in [START_REF] Sandholm | Potential games with continuous player sets[END_REF], we obtain the following characterization of attractors:

Proposition 3 Let Λ be a connected component of Nash equilibria. Then Λ is an attractor for ẋ = -x + Br(x) if and only if ∀x ∈ Λ, x is a local maximum of P .

Remark 2

The set [0, 1] N being invariant for the best-response dynamics, standard results guarantee the existence of at least one attractor (see for instance [START_REF] Conley | Isolated Invariant Sets and the Morse Index[END_REF]). However, this can also be derived by the previous proposition, since the potential function necessarily admits a global maximum on [0, 1].

We are now ready to characterize the attractors by finding the set of strict local maxima of P .

Stability -The Case of Perfect Substitutes

Given an action profile x, we denote by G A(x) the subgraph of G restricted to the agents in A(x). This graph is in general not connected (even if G is) and we denote by C 1 (x), ..., C K (x) the decomposition of G A(x) in connected components. Note that by abuse of notation we also use C k (x) to denote the set of agents in C k (x), so that

A(x) = ∪ K k=1 C k (x). ( 6
)
If x is a specialized Nash equilibrium, we denote by M (x) := A(x) the maximal independent set associated to x.

Definition 6 (Influence set) Let x ∈ N E with decomposition of active agents (C k (x)) k=1,...,K .
Given k ∈ {1, ..., K}, the set

I(C k (x), x) = {j ∈ W I(x) : N j (G) ∩ C k (x) = ∅} will be called the influence set of C k (x).
In the particular case of a specialized Nash equilibrium x with M (x) = {i 1 , ..., i K }, the family (C k (x)) k=1,...,K corresponds to the family of singletons ({i k }) k=1,...,K , and the influence set of agent i k in x is the set of neighbors of i k that have no other neighbor in M (x). For instance, in the network of figure 1, there are three specialized Nash equilibria corresponding to the three maximal independent sets M (x 1 ), M (x 2 ) and M (x 3 ) where x 1 = (0, 1, 0, 0), x 2 = (1, 0, 1, 0) and x 3 = (1, 0, 0, 1). In the first, only individual 2 has an influence set:

I(2, x 1 ) = {1, 3, 4}. In the second, I(1, x 2 ) = ∅ and I(3, x 2 ) = {4}. Now denote by x α the Nash equilibrium (1, 0, α, 1 -α). For α ∈]0, 1[ we have A(x α ) = C 1 (x α ) ∪ C 2 (x α ), where C 1 (x α ) = {1} and C 2 (x α ) = {3, 4}. Moreover I(C 1 (x α) , x α ) = I(C 2 (x α ), x α ) = ∅.
Note that in any network, if M (x) is of order at least 2, then

I(i, x) = ∅ for all i ∈ M (x). For any k ∈ {1, ..., K} we can then define G[C k , x] as the subgraph of G restricted to the agents in C k and I(C k , x). By abuse of notation, when C k is a singleton {i k }, we write G[i k , x].
We illustrate these definitions on Figure 3.

The next proposition characterizes the local maxima of the potential P in terms of the topology of the network. It is the first building block of our main theorem.

Proposition 4 Let x ∈ N E. Then x is a local maximum of P if and only if for all k, the subgraph G[C k , x] is complete.
Remark 3 A direct implication is that whenever x is a local maximum, all the subgraphs G[C k , x] must be disjoint. Indeed, if an agent is connected to two active components, then this agent has to be strictly inactive and not weakly inactive. This is not necessarily the case, when x is not a local maximum. Consider for instance the 5-line and Nash equilibrium

2/3 1/3 C1 C2 1/3 1/3 1/3 G[C2, x] G[C1, x] G[C3, x] C3
x = (1/2, 1/2, 0, 1/2, 1/2). Then we have C 1 (x) = {1, 2}, C 2 (x) = {4, 5} and G[C 1 , x] = {1, 2, 3}, G[C 2 , x] = {3, 4, 5}. Thus G[C 1 , x] ∩ G[C 2 , x] = ∅.
We can now state our theorem:

Theorem 1 A connected set Λ is an attractor for (4) if and only if:

• Λ is a connected component of Nash equilibria containing at least one specialized Nash equilibrium,

• and, for all specialized Nash equilibrium x in Λ, with

M (x) = {i 1 , ..., i k }, G[i k , x] is complete ∀k = 1, ..., K.
The proof of this theorem is long and involves many arguments that we think are interesting, so we provide intuitions together with several illustrating examples in what follows. The uninterested reader can go directly to subsection 4.1. The proof can be divided into two steps.

First, we show that if Λ is an attractor for the dynamics, then Λ contains at least one specialized Nash equilibrium10 . We illustrate this with Figure 4. There are three connected components:

Λ 1 = {(1, 0, 0, α, 1 -α) : α ∈ [0, 1]}, Λ 2 = {(0, 1, 1, 0, 0)} and Λ 3 = {( 1 3 , 1 3 , 1 3 , 1 3 - , ) : ∈ [0, 1 3 ]}.
According to Theorem 1, Λ 1 is a candidate to being an attractor because it contains two specialized Nash equilibria when α ∈ {0, 1}. Λ 2 is also candidate. Finally, Λ 3 cannot be an attractor as it does not contain any specialized Nash equilibrium. The proof of this first part involves several arguments. We use Proposition 4 to show that starting from a non-specialized equilibrium in Λ, we can always move in the component (by transferring efforts) and reduce the number of active agents. Inductively it implies the existence of at least one specialized Nash equilibrium in Λ. The fact that efforts can be transferred while staying in the component crucially depends on the fact that every point in the component is a local maximum of the potential, which implies in particular that the components of actives are complete. Let us illustrate this on the network of Figure 5. The initial profile is a Nash equilibrium. As efforts are transferred from one player in the triangle to another, the profile remains a Nash equilibrium. The final equilibrium is specialized, and this is possible only when components of active players are complete. If we replaced the triangle of this example by a square (which is not a complete network) and started at the equilibrium whre every agent in the square plays 1/3, it would be impossible to continuously transfer efforts from one agent in the square to another without moving out of the set of Nash equilibria.

In the second step of the proof, we show that specialized Nash equilibria in non-singleton components play a special role. In particular, a connected component of Nash equilibria containing specialized Nash equilibria is an attractor if and only if every specialized Nash equilibrium is a local maximum of P . To prove this, we need to show that any equilibrium x in a component Λ containing specialized Nash equilibria which are all local maxima of P is itself a local maximum of P . We use the fact that Λ is connected and thus construct a path starting from a specialized Nash equilibrium x and ending in x by continuously transferring efforts between agents. Along this path, the decomposition of actives C 1 , ..., C K may change, and we need to make sure that the subgraphs G(C k , x) always remain complete. We show that there is always a specialized Nash equilibrium from which one can start such that this In the second action profile (upper right panel), efforts are "transferred" from one agent to another in the triangle and yet, the profile remains in the Nash component. The final profile (lower panel) is a specialized Nash equilibrium.

property holds.

Theorem 1 is nice in several respects. First, it provides a characterization of attractors by relating them to topological properties of the network. Second, the relation we obtain is as simple as it can be, since checking whether graphs are complete or not is a trivial exercise. Third, the restriction to specialized equilibria hugely simplifies the problem. Indeed, however complex a component might be (recall for instance the four-dimensional continuum in Figure 2), it is sufficient to identify the set of specialized Nash equilibria that it contains. These are the only points that matter. Because specialized equilibria are maximal independent sets of the network, they are easy to find, allowing for an easy algorithmic implementation.

Finding attractors

Theorem 1 provides a convenient way of checking whether a given component is an attractor or not. However, it does not tell us how these components can be found. In this section we provide a result which will allow to construct an algorithm finding every attractor. This result is based on Proposition 2. Recall that Proposition 2 provides a sufficient condition for existence of continua of equilibria. Thus, by finding all the maximal independent sets in a given network and applying Proposition 2, we can construct components of equilibria. However, since the condition is only sufficient, we might be losing some components. For instance, in the 6-agents circle network, the maximal independent sets were {1, 4}, {2, 5}, {3, 6}, {1, 3, 5} and {2, 4, 6}. Proposition 2 finds no continuum, since all maximal independent sets of size 2 differ from strictly more than one agent. But there is one, given by the component Λ

= {(α, β, 1-α-β, α, β, 1-α-β); 0 ≤ α, 0 ≤ β, α+β ≤ 1}
, where the three maximal independent sets of size 2 belong.

An algorithm based on finding all maximal independent sets to construct all components of Nash equilibria, by checking whether these maximal independent sets satisfy Proposition 2, would wrongly consider the sets {1, 4}, {2, 5} and {3, 6} as three different components. However, as we show now, this is not a problem when we seek to find all the attractors.

Proposition 5 Let Λ be an attractor and let M and M be two maximal independent sets in Λ of cardinality p. Then there exists a sequence M 1 , ..., M k such that

|M ∩M 1 | = |M i ∩M i+1 | = |M k ∩ M | = p -1.
This Proposition, combined with Proposition 2, tells us that we might be overestimating the number of different components of Nash equilibria, but not the number of attractors.

Since we have an algorithm to find all attractors in a given network, we decided to compute them for all networks formed of N = 4 to N = 10 players, in order to get more insight on how the network structure affects the number of attractors. Our results are in table 2. As can be seen, the fraction of graphs with a single attractor is decreasing. However, we do not know if this pattern continues as N grows, and if it does, to which fraction it converges.

Illustration and implications

Proposition 5 provides an algorithm to find all the potential candidates to being an attractor. Theorem 1 then tells us how to determine whether it is an attractor or not. We illustrate how to implement it on an example.

Example 1 Consider the 8-agents graph in Figure 6.

The maximal independent sets are the following:

M 1 = {3, 4, 6, 7}, M 2 = {1, 2, 3}, M 3 = {1, 2, 8}, M 4 = {6, 7, 8}, M 5 = {5, 6, 8}.
Hence there are five specialized Nash equilibria that we denote by x i , i = 1, ..., 5, that are associated to each maximal independent set. There are three connected components of Nash equilibria containing at least one specialized Nash equilibrium: • a singleton Λ 1 = {(0, 0, 1, 1, 0, 1, 1, 0)} containing x 1 :

Number of different attractors N = 4 N = 5 N = 6 N = 7 N = 8 N = 9 N =
• a continuum Λ 2 = {(1, 1, 1α, 0, 0, 0, 0, α) : α ∈ [0, 1]}, that contains x 2 and x 3 .

• and another continuum Λ 3 = {(0, 0, 0, 0, α, 1, 1α, 1) : α ∈ [0, 1]}, that contains x 4 and x 5 .

There is no point looking for other components of Nash equilibria as they will not contain any specialized Nash, and thus cannot be attractors.

16

• The set M 1 is a maximal independent set of order 2. Therefore, Λ 1 is an attractor (the influence set of every agent i ∈ M 1 is empty).

A priori, nothing differentiates Λ 2 from Λ 3 : the potential is equal to 3/2 along both components and they have similar shapes. In order to determine their nature, our theorem says that we only need to focus on the specialized Nash equilibria:

• For component Λ 2 we have I(1, x 2 ) = I(2, x 2 ) = ∅. Thus {1} ∪ I(1, x 2 ), {2} ∪ I(2, x 2 ), {1} ∪ I(2,
x 3 ) and {2} ∪ I(2, x 3 ) are all singletons, making the induced subgraph complete networks.

Next, I(3, x 2 ) = {8}, thus {3} ∪ I(3, x 2 ) = {3, 8} and the induced subgraph is a connected pair and thus a complete network. This means that x 2 is a local maximum of the potential. Similarly, I(8, x 3 ) = {3}. Hence x 3 is also a local maximum of the potential. Since x 2 and x 3 are the only specialized Nash equilibria in Λ 2 and both are local maxima of the potential, our theorem guarantees that Λ 2 is an attractor.

• For component Λ 3 , we have I(6, x 5 ) = I(8, x 5 ) = ∅ and I(5, x 5 ) = {7}, which makes x 5 a local maximum of the potential. Also I(6, x 4 ) = ∅ and I(7, x 4 ) = {5}. However I(8, x 4 ) = {3, 4}, which does not induce a complete graph (3 and 4 are not linked). As a result, our main theorem claims that x 4 is not a local maximum of the potential. Indeed, for x = (0, 0, , , 0, 1, 1, 1 -2 ) we have P (x ) = 3 2 + 2 > P (x). Thus the dynamics we consider would lead individuals out of the component, following a direction that increases P .

We conclude that there are two attractors, Λ 1 and Λ 2 .

We now illustrate how our results relate to the results in [START_REF] Bramoullé | Public goods in networks[END_REF].

Corollary 1 An equilibrium x is an asymptotically stable point if and only if x is specialized and associated with a maximal independent set of order 2.

The proof of this corollary relies on the fact that when focusing on isolated equilibria, the first step of theorem 1 excludes interior isolated equilibria from being attractors, and on the fact that the conditions of theorem 1 are trivially satisfied in that case: when M is a maximal independent set of order 2, the influence set of every individual in M is empty, thus complete.

Note that this corollary is very close from Theorem 2 in [START_REF] Bramoullé | Public goods in networks[END_REF]. There are two important differences: first they consider discrete-time BRD. Second, in their settings, these asymptotically stable points are the only stable outcomes of the dynamics. In particular many graphs have no stable outcomes. In contrast, as we stated in Remark 2, there is always at least one attractor, for any δ. When δ = 1 we provide a constructive proof to this statement: Let a maximum independent set of an undirected graph G be a maximal independent set of largest cardinality. Now, let x be a specialized Nash equilibrium associated to a maximum independent set of a network M (x). Then G[i, x] is complete ∀i ∈ M (x). Assume it is not the case. This implies the existence of an individual i in M (x) and at least two individuals j 1 and j 2 in I(i, x) that are not linked. Furthermore, they are not linked to any other individual in M (x) by definition. Thus, we can construct another specialized Nash equilibrium x such that M (x ) = M (x) \ {i} ∪ {j 1 , j 2 }. The set M (x ) is also a maximal independent set, and

|M (x )| > |M (x)|, a contradiction.

Stability -The Case of Imperfect substitutes

In this section we consider the case δ = 1, which was investigated in [START_REF] Bramoullé | Strategic interaction and networks[END_REF]. Let us briefly recall the results they obtained regarding stability. First, if interactions are low enough, i.e. λ min (G) > -1/δ11 , then the game has a unique (thus isolated) equilibrium. This implies that it is an attractor because it must be a strict maximum of the potential. Second, whenever interactions are higher, i.e. λ min (G) ≤ -1/δ, then if x is a Nash equilibrium that is both isolated and such that no individual is weakly inactive, x is an attractor if and only if

λ min (G A(x) ) > -1/δ.
Here, we pursue this analysis without restricting our attention to isolated points nor to equilibria without weakly inactive agents. Although we do not get as sharp a characterisation as for the case of perfect substitutes, we provide some useful results. Let Ã(x) := A(x)∪W I(x) and G Ã(x) be the subgraph of G restricted to agents in Ã(x).

Proposition 6 Let x be a Nash equilibrium.

If λ min (G A(x) ) < -1/δ, then x is not a local maximum of P . If λ min (G A(x) ) = -1/δ, then x is not a strict local maximum of P . If λ min (G Ã(x) ) > -1/δ then x is a strict local maximum of P and x is specialized. If λ min (G Ã(x) ) = -1/δ, then x is a local maximum of P .
This proposition is very close to Proposition 4 in [START_REF] Bramoullé | Strategic interaction and networks[END_REF]. The distinction with their result requires some comment that will help understand the main issue caused by the presence of weakly inactive agents.

The importance of the lowest eigenvalue resides in the fact that its associated eigenvector provides the deviation from x that will increase the most the potential. This value is thus critical in determining whether an equilibrium x is a local maximum or not. When there are no weakly inactive agents, this deviation is always admissible, in the sense that the action profile remains in the state space. Indeed, every agent in A(x) plays an action in ]0, 1[, so that after any small deviation their actions remain in ]0, 1[. A consequence is that the lowest eigenvalue of the subgraph of active agents, i.e. G A (x), gives a necessary and sufficient condition.

If some agents are weakly inactive, this direction could be non-admissible, and thus the lowest eigenvalue of the subgraph of active players is no longer a sufficient indicator to determine stability. It remains a necessary condition, while the sufficient condition now relies on the subgraph of active and weakly inactive agents, i.e. G Ã(x) . Now, whenever λ min (G A(x) ) > -1/δ > λ min (G Ã(x) ) many things can happen. As in the previous section, we obtain our results by analyzing the behavior of the potential function. In the case of perfect substitutes, we showed (Proposition 4) that it was sufficient to focus on subgraphs of G. Here we rely on some equivalent property. Let M be a subset of N . We denote by P M the restriction of P to the subgraph induced by vertices in M (so that P N = P ).

Lemma 3 Let x be a Nash equilibrium. Then x is a local maximum of P if and only if the restriction of x to Ã(x), x Ã, is a global maximum of P Ã.

Thus, strictly inactive agents can be ignored when trying to determine whether an equilibrium is a local maximum. Moreover, while x is a local maximum, x à is a global maximum, which makes it easier to check if an equilibrium x can be discarded. This lemma includes the case δ = 1, in which case it says that one can focus on influence sets. This can be seen by noticing that the subgraph induced by all agents in Ã(x) is precisely the union of all the subgraphs G[C k , x].

Based on this, we have the following theorem that helps determining if an equilibrium or a component is an attractor. We define the set Z := {y ∈ [0, 1] N ; y i > 0 ⇒ y i + δ(Gy) i ≤ 1} as the set of all acceptable profiles. The set Z includes all the Nash profiles, but it also includes profiles in which aggregate efforts around some agents are lower than 1.

Theorem 2 Let x be any Nash equilibrium. The following statements are equivalent:

(i) x is a local maximum of the potential. (ii) for any y ∈ Z, if A(y) ⊂ Ã(x) then i x i ≥ i y i ; (iii) for any Nash equilibrium x such that A(x ) ⊂ Ã(x), we have SI(x ) ∩ A(x) = ∅;
This theorem provides two necessary and sufficient conditions, but their interpretation is not as straightforward as for the case δ = 1. Still, it is very useful to check if an equilibrium is not a local maximum.

First, condition (ii) gives us a large set of profiles to choose from (those in Z) and counterexamples can be found on the subgraph G Ã(x) instead of the entire network G. Let us illustrate this on an example. Assume the network of Figure 8 represents a component of active and weakly inactive agents lying in a bigger network, and that an effort profile x is a Nash equilibrium on the entire network with δ = 1/3. In order to check if it is a local maximum, it is sufficient to focus on the subgraph Ã(x) that we have represented. The sum of efforts at x à is 3. However, it is easy to find another profile involving the same set of agents, such that the sum of efforts is greater. Even though this alternative profile is not a Nash equilibrium, theorem 2 tells us that x is not a local maximum. Second, condition (iii) offers an alternative strategy. This one consists in looking for an alternative Nash equilibrium by transforming some agents in Ã(x) into strictly inactive agents, while all the active agents in the new equilibrium are already in Ã(x). Because the number of agents in Ã(x) is finite, this provides an algorithmic procedure to find the equilibria and check whether they are local maxima. We describe this algorithm in the appendix.

Remark 4 Theorem 2 implies that a specialized Nash equilibrium x is a local maximum if and only if G[i k , x] is complete for every k, when δ = 1. To see this, suppose first that for some k 0 , G[i k 0 , x] is not complete. Let j, j ∈ G[i k 0 , x] be un-linked and construct the profile y as: y i k = 1 ∀k = k 0 ; y j = 1, y j = 1 and y i = 0 otherwise.

Clearly {j, j , (i k ) k =k 0 } is an independent set so that y ∈ Z. However i y i > i x i and x is not a local maximum of P by (ii). Let us prove the reverse implication. Suppose that G[i k 0 , x] is complete for every k. Let x be a Nash equilibrium with A(x ) ⊂ Ã(x). Then for any k

we have i k / ∈ SI(x ) because i∈G[i k ,x] x i ≤ 1.
Consequently x is a local maximum of the potential by (iii).

Alternative dynamics

In the previous sections, we characterized the attractors of ẋ = -x + Br(x). As mentioned earlier, this dynamical system is sometimes used to study the asymptotic stability of Nash equilibria. However, other dynamical systems are often examined, either for the same purpose, or because they are related to the behavior of learning processes. In this section, we illustrate how our results are useful for alternative dynamical systems.

Continuous-time dynamics

As the reader might have noticed, the analysis just exposed does not really rely on the properties of the best-response function. Rather, it relies on the existence of a potential function which plays the role of a Lyapunov function with respect to this dynamics. Thus, any dynamical system which has this property will share exactly the same set of attractors. Let V : X → R N be a Lipschitz map and suppose that the two following conditions hold.

Hypothesis 1 ∀x ∈ X, x i = 0 ⇒ V i (x) ≥ 0; x i > 1 ⇒ V i (x) < 0. Let DP (x) := ∂P ∂x 1 (x), ..., ∂P ∂x N (x) . Hypothesis 2 V is such that V (x) = 0 if x ∈ N E and DP (x), V (x) > 0, ∀x / ∈ N E. ( 7
)
Remark 5 The map V (x) = -x + Br(x) satisfies Hypothesis 1 and 2.

Consider the following ordinary differential equation:

ẋ = V (x) (8)
Hypothesis 1 along with the fact that V is Lipschitz guarantee that the system (8) admits unique forward solutions into [0, 1] N , from any x ∈ [0, 1] N . In other terms [0, 1] N is positively invariant. This implies the existence of a semi-flow ϕ on [0, 1] N such as in ( 5). Hypothesis 1 is natural in our context, since individuals that are alone would choose to exert an effort level of 1. Thus no one would increase its effort above 1 when efforts are substitute.

Hypothesis 2 guarantees that the potential P is a strict Lyapunov function for ẋ = V (x) and thus Lemma 1 holds.

Proposition 7 Under Hypothesis 1 and 2, both Theorem 1 and Theorem 2 hold for the dynamical system ẋ = V (x).

Discrete-time dynamics

In the learning literature, discrete-time dynamics have often be considered. Here, we explore the connections between (BRD) and other standard discrete-time dynamics which make use of the best response. We distinguish between systems where players revise their actions simultaneously, and systems where they revise sequentially.

The first system is the best-response dynamics with incomplete adjustments (SimBR κ ), which was introduced by [START_REF] Fisher | The stability of the cournot oligopoly solution: The effects of speeds of adjustment and increasing marginal costs[END_REF], where players simultaneously adjust their action in the direction of (and not necessarily to) the best response; the second is the best-response with simultaneous updating and vanishing speeds of adjustments (SimBR κt ), and the third one is the sequential best-response where one player is picked at random at every period and is given the opportunity to adjust his action (SeqBR).

(SimBR κ ) Let κ ∈]0, 1]. The discrete-time best-response dynamics with simultaneous updating and parameter κ is given by

x t+1 = (1 -κ)x t + κBr(x t ); (9)
(SimBR κt ) Let (κ t ) t be a sequence of positive real numbers such that lim t κ t = 0 and t κ t = +∞. The vanishing discrete-time best-response dynamics with simultaneous updating is given by

x t+1 = (1 -κ t )x t + κ t Br(x t ); (10)
(SeqBR) Let π ∈ ∆(N ) be a probability distribution with full support (π := min i π(i) > 0) and I t be a sequence of i.i.d random variables taking values in N with distribution π. The discrete-time best-response random process with sequential updating is given by

x It t+1 = Br i (x -It t ), x i t+1 = x i t for i = I t . ( 11
)
As we show with the following propositions, attractors for the sequential best-response process and for the simultaneous vanishing best-response coincide with the attractors for (BRD). However, the simultaneous best-response with parameter κ behaves differently: if Λ is an isolated attractor for (BRD) (i.e. a maximal independent set of order 2) then Λ is an attractor for (SimBR κ ), for any κ ∈]0, 1]12 . However, attractors for (BRD) are not necessarily attractors for (SimBR κ ), and some strange, disconnected non-equilibrium sets can be attractors for (SimBR κ ) while they are not for the (BRD). This is due to the nonvanishing size of adjustment between subsequent iterations that these dynamics allow for.

Let x be a specialized Nash equilibrium. Define p(x) := max i∈A(x) {|G[i, x]|} and p(Λ) := max x∈Λ p(x).

Proposition 8 (SimBR κ ) Assume Λ is an attractor for (BRD). If κ ≥ 2 p(Λ) then Λ is not an attractor for (SimBR κ ). Since this dynamical system's behavior is different, let us provide some details. The (BRD) consists in marginal increments in the direction of the best response, while the SimBR κ makes discrete adjustments towards the best response. These jumps are responsible for the difference in behavior.

Whenever these jumps are small enough, the behaviors sometimes coincide, while they always differ when these jumps become large. The differences are of two kinds. First, some attractors for (BRD) are not attractors for (SimBR κ ); second, attractors for (SimBR κ ) are not necessarily connected components (and thus cannot be attractors for (BRD)). Consider the simplest network formed of a pair. There is a unique component of Nash equilibria, which is an attractor for (BRD), given by Λ = {(1α, α), α ∈ [0, 1]}. It contains two specialized Nash equilibria, (1, 0) and (0, 1), thus p(Λ) = 2. Proposition 8 tells us that attractors will differ as soon as κ ≥ 1. Assume κ = 1. Then the dynamical system is given by x t+1 = Br(x t ). Assume that the process starts in a neighborhood of, say, ( 23 , 1 3 ), which is a Nash equilibrium; for instance at the profile x 0 = ( 23 -1 , 1 3 + 2 ) for arbitrary small values of 1 and 2 . Then

x 1 = ( 2 3 -2 , 1 3 + 1 ), and x 2 = ( 2 3 -1 , 1 3 + 2 ) = x 0 .
In fact, x 2n = x 0 and x 2n+1 = x 1 for any n, so that the system never goes back to ( 23 , 1 3 ). However, as soon as κ < 1, the system will go back to the initial equilibrium and the component Λ will be an attractor. Now, consider the three agents complete network. Here again, there is a unique component of Nash equilibria, which is an attractor for (BRD), given by Λ

= {(α, β, 1 -α -β), α, β, 1 - α -β ∈ [0, 1]}.
Here, p(Λ) = 3 and thus the critical value is for κ = 2 3 . When κ ≥ 2 3 , the same reasoning as above illustrates why Λ is not an attractor for (SimBR κ ). Moreover, taking initial conditions (a, a, a) with a = 1/3 we can show that the (one-dimensional) system converges to the periodic orbit (

1 1+3(1-κ) , 1-κ 1+3(1-κ)
). This set is non-connected and contains only non-Nash profiles.

Proposition 9 (SimBR κ t and SeqBR) The systems (BRD), (SimBR κt ) and (SeqBR) have the same attractors.

Note that ( 11) is stochastic and ( 10) is not time-homogeneous. Hence we must be careful with the definitions of an attractor. We give precise statements and prove them in the appendix.

This result suggests that our analysis is robust to variations of the dynamical system, as long as the systems do not consist of discontinuities of non-vanishing size.

Appendix

Proofs of Sections 2 and 3

Proof of Proposition 1. We first show that NE is a finite union of compact convex sets. Let A be a subset of agents and N E A be the set {x ∈ N E :

x i = 0 ∀i / ∈ A, x i + δ(Gx) i = 1 ∀i ∈ A} . It is not hard to see that N E A is closed. Now let x, y ∈ N E A , λ ∈ [0, 1] and z = λx + (1 -λ)y. If i / ∈ A, x i = y i = 0. Hence z i = 0. If i ∈ A z i + (Gz) i = λ(x i + δ(Gx) i ) + (1 -λ)(y i + δ(Gy) i ) = 1.
Clearly N E = ∪ A∈P(N ) N E A where each N E A is compact and convex. As a consequence there exist connected components of NE Λ 1 , ..., λ L such that

N E = ∪ L l=1 Λ l .
Proof of Proposition 2. Let M = {m 1 , . . . , m p-1 , m p } and M = {m 1 , . . . , m p-1 , m p }, with m p = m p . Then necessarily m p and m p are linked. Indeed, because M is a maximal independent set, every agent in N \ M is linked to at least one individual in M . This is true in particular for individual m p . However, because m p ∈ M , he cannot be linked to anyone in {m 1 , . . . , m p-1 }. Thus he is linked to m p . Then, one can check that the profile x is a NE, where

x i = 0 if i ∈ N \ (M ∪ m p ),
x m i = 1 for all i ∈ {1, . . . p -1}, and

x mp = α, x m p = 1 -α, for any α ∈ [0, 1].
Proof of Lemma 1. We have

∂P ∂x i (x) = 1 -x i -δ(Gx) i . Thus DP (x), -x + Br(x) = i ∂P ∂x i (x)(-x i + Br i (x -i )). If i ∈ SI(x) then -x i +Br i (x -i ) = 0. Also ∂P ∂x i (x) = -x i +Br i (x -i ) if i / ∈ SI(x). Consequently DP (x), -x + Br(x) = i / ∈SI(x) (-x i + Br i (x -i )) 2 ≥ 0.
If x / ∈ N E, then this quantity is strictly positive. This proves the first point.

We now prove that P is constant on N E A . Let P A : R A → R be defined as

P A (z) = i z i - z 2 2 - 1 2 δ z, G A z .
For x ∈ N E A , let x A = (x i ) i∈A . We then have P A (x A ) = P (x). Moreover, for i ∈ A,

∂P A ∂z i = 1 -z i -δ(G A z) i .
By definition of N E A , we then have

{x A : x ∈ N E A } ⊂ {z ∈ R A : ∇ z P A = 0}. Now P A is C ∞ and, by Sard's Theorem, P A ({x A : x ∈ N E A }) has Lebesgue measure zero in R A . As an immediate consequence, P A is constant on {x A : x ∈ N E A } , which directly implies that P is constant on N E A .
Since N E is a finite union of sets on which P is constant, P must remain constant on any connected component of N E.

Proof of Lemma 2. Although this is a classical result from the dynamical system theory, the proof might slightly differ with respect to the assumptions made. Hence we sketch the proof in our settings for convenience. We prove this lemma for any dynamical system ẋ = V (x) where V (.) satisfies Hypothesis 1 and 2 in section 6. This includes the case of ẋ = -x+Br(x). First, w(x 0 ) is a connected compact and invariant (possibly empty) set. Note that, for any x 0 ∈ X and any r > 1, ϕ(x 0 , t) ∈ [0, r] N for t large enough. Indeed, if x i ≥ r then ẋi = V i (x) < 0. That means that, for any x 0 ∈ X, ω(x 0 ) is nonempty and contained in [0, 1] N . For any x ∈ ω(x 0 ), we have P (x) = lim t→+∞ P (ϕ(x 0 , t)) because P increases along trajectories. Now ω(x 0 ) being invariant directly implies that ϕ(x, t) ∈ ω(x 0 ) and hence that P (ϕ(x, t)) = P (x) = P (ϕ(x, 0)) for any t ≥ 0. This means that x ∈ N E by lemma 1. Thus ω(x 0 ) ⊂ N E. Since ω(x 0 ) is nonempty and connected, it must necessarily be contained in a connected component of NE, i.e. ω(x 0 ) ⊂ Λ l for some Λ l in the decomposition of proposition 1.

Proof of Proposition 3. First we prove the following lemma:

Lemma 4 Let Λ be a connected component of NE and assume that for any x ∈ Λ, x is a local maximum of P . Then Λ is a local maximizer set of P .

Proof. By Lemma 1, P is constant on Λ. Let v := P (Λ). Assume by contradiction that there exists a sequence (x n ) n ∈ X \ Λ such that lim n d(x n , Λ) = 0 and P (x n ) ≥ v. By compactness of Λ, we can assume without loss of generality that lim n x n = x ∈ Λ. Let U be an open neighborhood of x such that P (x) ≥ P (y), ∀y ∈ U . We have P (ϕ(x n , t) > v for t > 0. Let t n be a sequence of real numbers such that t n ↓ n 0. For n large enough and t small enough ϕ(x n , t) ∈ U , a contradiction. Now we can prove the proposition. Let Λ be a connected component of Nash equilibria. By Lemma 4, we only need to prove that Λ is an attractor if and only if it is an isolated local maximizer set of P . Let us first prove the direct implication. Λ is connected and by Lemma 1, P is constant on Λ. Let v := P (Λ). If Λ was not a local maximizer set of P then there would exist a sequence x n such that d(x n , Λ) → n 0 and P (x n ) > v. Since Λ is isolated in NE we have x n ∈ X \ N E and P (ϕ(x n , t)) > P (x n ) > v for any t > 0. Hence d(ϕ(x n , t), Λ) 0 and Λ is not an attractor.

We now prove the reverse implication, namely that if Λ is a local maximizer set of P then it is an attractor for ẋ = -x + Br(x). Since P is a strict Lyapunov function for ẋ = -x + Br(x), the statement we want to prove is then a consequence of Proposition 3.25 in [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF]. We adapt the proof in our context for convenience. Let U r := {x ∈ U : P (x) > v -r}. Clearly ∩ r U r = Λ. Also ϕ(U r , t) ⊂ U r , for t > 0, r small enough13 . This implies that Λ = ∩ r>0 U r contains an attractor A (see [START_REF] Conley | Isolated Invariant Sets and the Morse Index[END_REF]). The potential being constant on Λ, A cannot be strictly contained in Λ and therefore Λ is an attractor.

Proofs of Sections 4 and 5

We first prove a lemma that will be useful in what follows.

Lemma 5 We have

• Let x ∈ N E and v be such that x + v ∈ R N + . Then P (x + v) = P (x) + i∈SI(x) v i (1 -δ(Gx) i )) - 1 2 v 2 + v, δGv .
• Let x and y be a Nash equilibria. Then

P (y) -P (x) = 1 2   i∈SI(x) y i (1 -δ(Gx) i ) - i∈SI(y) x i (1 -δ(Gy) i )   Proof.
Let us prove the first point.

P (x + v) = P (x) + v, 1 -v, x - 1 2 v 2 - 1 2 δ ( v, Gx + x, Gv + v, Gv ) = P (x) + v, 1 -x -δGx - 1 2 v 2 + v, δGv = P (x) + i∈SI(x) v i (1 -δ(Gx) i ) - 1 2 v 2 + v, δGv .
For the second point, if y is a Nash equilibrium. Let v = yx. Using the previous equality,

P (y) -P (x) = i∈SI(x) v i (1 -δ(Gx) i )) - 1 2 v 2 + v, δGv . and P (x) -P (y) = i∈SI(y) -v i (1 -δ(Gy) i )) - 1 2 v 2 + v, δGv .
Combining these two inequalities, we obtain

2(P (y) -P (x)) = i∈SI(x) v i (1 -δ(Gx) i )) + i∈SI(y) v i (1 -δ(Gy) i )) = i∈SI(x) y i (1 -δ(Gx) i )) - i∈SI(y) x i (1 -δ(Gy) i ))
which gives the result.

Proof of Proposition 4. First assume that there exists k such that G[C k , x] is not complete.

Then one of the two following cases occurs: a) there exists j ∈ I(C k , x) such that the restriction of G to C k ∪ {j} is not complete. Let then v be the eigenvector associated to the lowest eigenvalue λ of this graph with v j ≥ 0. We then have

P (x + v) = P (x) - 1 2 v 2 + v, Gv = P (x) - 1 2 (1 + λ) v 2 > P (x),
because λ < -114 . Thus x is not a local maximum of P .

b) otherwise there necessarily exist j 1 , j 2 ∈ I(C k , x) such that j 1 j 2 / ∈ G. Pick any i ∈ C k and let x ε be defined by x ε j 1 = x ε j 2 = ε, x ε i = 1 -2ε. We then have

P (x ε ) = P (x) - 1 2 4 2 -6 2 > P (x),
which concludes the proof of the first implication.

Suppose now that G[C k , x] is complete for any k. Then any j ∈ W I(x) belongs to exactly one influence set. Let v be such that x i + v i > 0 for any i ∈ A(x) and v j ≥ 0 for any j / ∈ A(x).

We must prove that P (x + v) ≤ P (x). We have

P (x + v) ≤ P (x) - 1 2 v 2 + v, Gv ≤ P (x) - 1 2 K k=1 v k 2 + v k , G k v k ≤ P (x),
where

G k := G[C k , x
] and v k is the restriction of v to the agents in G k . The second inequality is due to the fact that v, Gv is equal to K k=1 v k , G k v k with the addition of positive terms (the other links are between inactive agents, for which v j ≥ 0). The last inequality is due to the fact that λ min (G k ) = -1, and

v k , G k v k ≥ λ min (G k ) v k 2 .
Proof of Theorem 1.

We prove theorem 1 by showing the two following properties:

Along this path, the decomposition of actives (6) changes. However, note that if C t k is complete, it can only become an incomplete graph if a new agent enters C t k . Indeed, if an agent leaves C t k , then the complete graph remains complete. Assume first that ∀i ∈ N and ∀t < t we have i ∈ SI(x(t)) ⇒ i ∈ SI(x(t )) (that is strictly inactive agents always remain so along the path) then G t k is obtained from G 0 k by possibly removing some agents (agents in G 0 k that become strictly inactive along the path). Thus for any t ∈ [0, 1] and any k, G t k is complete, which proves the result. Otherwise there exists 0 = t 0 < t 1 < t 2 < ... < t N ≤ 1 such that

t n+1 := inf{t > t n : ∃i ∈ I(x(t)), ∃ > 0 such that i ∈ SI(x(t )) ∀t ∈]t -, t[}
These are the instants along the path when some strictly inactive agents become weakly inactive (and hence enter some G[C t k , x(t)]). Consider the following property:

∀j ∈ SI(x(t)), ∃k ∈ {1, ..., K(t)} : C t k ⊂ N j , (P(t))
that is, at time t, any strictly inactive agent is linked to all agents of at least one connected component of active agents. Note that the set {t : P(t) does not holds} is an open set.

Let n ∈ {0, ..., N -1}. We claim that if x(t n ) is a local maximum of P and (P(t n )) holds then x(t) is a local maximum for any t ∈ [t n , t n+1 ], and (P(t)) holds for any t ∈ [t n , t n+1 ]. Since x(0) = x is a local maximum of P by assumption and P(0) holds since x is a specialized Nash equilibrium, this will prove the result. Note that for t ∈]t n , t n+1 [, every strictly inactive agent remains strictly inactive so that G t k remains complete. Therefore x(t) is a local maximum. Suppose that (P(t)) does not hold for some t ∈]t n , t n+1 ]. We will show that this allows to construct a specialized Nash equilibrium profile x which belongs to Λ and is not a local maximum of the potential. This will contradict the hypothesis that every specialized Nash equilibrium is a local maximum of P . The arguments which follow are illustrated on Figure 9.

If (P(t)) does not hold for some t ∈]t n , t n+1 ], then necessarily there would exist some t * ∈ [t n , t n+1 [15 such that (P(t)) holds for t ∈ [t n , t * ] and does not hold for t ∈]t * , t * + [, for sufficiently small > 0. In that case there would exist j * ∈ SI(x(t * )) and n * ≥ 1 such that {1, ..., n * } = {k ∈ {1, ..., K(t * )} :

C t * k ⊂ N j * }
and i 1 ∈ I(C t * 1 ), ..., i n * ∈ I(C t * n * ) such that j * is not linked to any of the i n and i n ∈ C t n for t ∈]t * , t * + [. 16 . We now construct a specialized Nash equilibrium x belonging to Λ which is not a local maximum of the potential. Note that x is not necessarily on the path (x(t)) t∈ [0,1] .

Assume for simplicity that n * = 1. Pick any l 1 ∈ C t * 1 . For k = 2, ..., K(t * ), choose l k ∈ C t * k which is not linked to j * . Let x be defined as follows:

xl k = 1 for k = 1, ..., K(t * ) xi = 0 otherwise (in particular, xj * = 0).

Then x belongs to Λ and is a specialized Nash equilibrium (any strictly inactive agent is connected to every agent in at least one C t * k , and consequently is linked to at least one of the l k ). However G[l 1 , x] is not complete, because it contains both j * and i 1 , who are not linked together. Thus x is not a local maximum of the potential. This proves that P(t) holds for t ∈ [t n , t n+1 ]. A construction in the same spirit allows us to reach the same conclusion when n * > 1. 17

We finally need to prove that x(t n+1 ) is a local maximum of P , that is G t n+1 k is complete for k = 1, ..., K(t n+1 ). Suppose that agents j 1 , ..., j P go from strictly inactive to weakly inactive at time t n+1 . By property P(t n + 1) there exists a partition (J 1 , ..., J R ) of {j 1 , ..., j P } (with R ≤ P ) and k 1 , ..., k R such that

C t n+1 kr ⊂ N jp , ∀j p ∈ J r .
Note that since j p is linked to every agent in C t n+1 kr and is not strictly inactive at time t n+1 we necessarily have

N jp ∩ C t n+1 k = ∅ for k = k r . Now choose i 1 , ..., i K(t n+1 ) in respectively C t n+1 1 , ..., C t n+1 K(t n+1
) and consider a profile x * defined as follows: x * i k = 1 and x * i = 0 otherwise. Let us prove that x * is specialized. Consider any path going from x(t n+1 ) to x * by continuously transferring effort from agents in C t n+1 k \ {i k } to i k . Then the sum of effort in C k remains equal to one. Now let us partition the weakly inactive and strictly inactive agents at time t n+1 in three categories and check that they remain active or weakly inactive (that is none of them has strictly less than one among his neighbors):

16 To sum up, at time t * , j * is a strictly inactive agent who is linked to every agents in C1(t * ), ..., Cn * (t * ). However agents i1, ..., in are not linked to j * and become active precisely after instant t * (so that i1 ∈ C t 1 for t > t * ), which means that property P(t) does not hold any more after time t * . 17 If n * > 1 then the construction of x needs to be modified. Pick any l

* n ∈ C t * n * . For k = n * + 1, ..., K(t * ), choose l k ∈ C t *
k which is not linked to j * . Then define x as follows:

   xin = 1 for n = 1, ..., n * -1 xl k = 1 for k = n * , ..., K(t * ) xi = 0 otherwise (in particular, xj * = 0).
Then the conclusion follows from the same fact: G[ln * , x] contains both j * and in * who are not linked together.

j * 2/3 1/3 1/2 1/3 1/6 l2 l1 i1 C t * 1 C t * 2 j * 2/3 l2 l1 i1 G([l2, x) G[l1, x]
Figure 9: Illustration of the construction of x when n * = 1. Left panel: the profile x(t) is a Nash equilibrium. Agent j * is strictly inactive, and linked to every agent in the component C t * 1 , and not to every agent in component C t * 2 . Agent i 1 belongs to I(C t * 1 ). This is the configuration which should arise if property P(t) did not hold after time t * . Right panel: With such a configuration, we can construct the profile x, where black circles represent agents exerting an effort of 1 and white circles represent agents exerting 0 effort. This profile is a Nash equilibrium and it is specialized. Agent j * now belongs to G[l 1 , x], which is not complete since i 1 also belongs to G[l 1 , x]. Thus x is not a local maximum of the potential, which contradicts the hypothesis. * agents j 1 , ..., j P are connected to every agent in exactly one of these components so that they remain weakly inactive along the path; * agents in I(C t n+1 k ) \ {j 1 , ..., j P } remain weakly inactive along the path, as they are connected to every agent in C t n+1 k ; * at last strictly inactive agents remain strictly inactive or at least weakly inactive agents along the path, because they are linked to at least one of the i k .

Consequently x * is specialized and G[i k , x * ] is complete by assumption. However we have G

t n+1 k = G[i k , x * ]
. This concludes the proof.

Proof of Proposition 5. Suppose that Λ is an attractor and let x, x be two specialized Nash equilibria (with corresponding maximal independent sets M, M ). Let x(•) : [0, 1] → Λ be a continuous path such that x(0) = x and x(1) = x and D t (x) be the decomposition in (disjoint) complete subraphs of agents in N \ SI(x(t)). Define

T 1 := inf{t > 0 : D t (x) = D 0 (x)}, T k+1 := inf{t > 0 : D t (x) = D T k (x)}
We assume that the path we chose is such that this sequence is finite: D T K (x) is the decomposition corresponding to x . Note that it can be implicitely assumed without loss of generality that for any t any maximal independent set M ∈ D t (x) (i.e. that can be constructed in by putting in each complete subgraph exactly one agent at one) is on the path. At time T k , two mutually exclusive events can occur: (i) (at least) one agent becomes strictly inactive (i.e. inactive at time T k and strictly inactive at time t > T k ). In that case D T k (x) = D T + k ;

(ii) (at least) one agent stops being strictly inactive (i.e. strictly inactive for t < T k and not strictly inactive at time T k ). Here D

T k (x) = D T - k
Case (i) is not really relevant because any maximal independent set that can be constructed at time T + k already existed at time T k . As a consequence proving our claim amounts to showing that, for any k for which case (ii) occurs there exists a pair maximal independent sets

M - k ∈ D T - k (x) and M k ∈ D T k (x) such that |M - k ∩ M k | = p -1. Pick a pair of maximal independent set M - k ∈ D T - k , Mk ∈ D T k
and assume they differ from exactly m agents that stop being strictly inactive precisely at time T k : M - k = {i 1 , i 2 , i m , i m+1 ..., i p } and Mk = {j 1 , j 2 , j m , i m+1 ..., i p }). Since they all become weakly inactive together at instant T k , each j l simultaneously enters into the influence set of some active players. They cannot enter in the same influence set, otherwise they would have to be linked, which is a contradiction. Thus they belong to m distinct influence sets. As a consequence we can construct another maximal independent set M k ∈ D T k (x) where only j 1 is active, that is

|M - k ∩ M k | = p -1.
This concludes the proof.

Proof of lemma 3. Cleary if x is local maximum of P then x à is a local maximum of P Ã. Now suppose that there exists a sequence (x n ) n in R N + such that lim n x n = x and P (x n ) > P (x). Let z n be defined as z n i := x n i for i ∈ Ã(x) and z n i = 0 for i ∈ SI(x).

P (z n ) -P (x n ) = - i∈SI(x) x n i + 1 2 i∈SI(x) (x n i ) 2 + i∈SI(x) x n i (Gx n ) i = i∈SI(x) x n i x i n 2 -1 + (Gx n ) i
Now by definition of SI(x),

lim n→+∞ x i n 2 -1 + (Gx n ) i = -1 + (Gx) i > 0.
Hence, P (z n ) ≥ P (x n ) > P (x) = P Ã(x Ã) for large enough n, a contradiction. This concludes the proof.

Before proving Theorem 2, let us prove a preliminary result. Recall that Z = {y ∈ [0, 1] N ; y i > 0 ⇒ y i + δ(Gy) i ≤ 1}. Then for any x ∈ Z, P (x) ≥ 1 2 i x i . Furthermore, P (x) = 1 2 i x i if and only if x ∈ Z is such that y i > 0 ⇒ y i + δ(Gy) i = 1. This implies that P (x) = 1 2 i x i for any x ∈ NE.

Proof: We have

P (x) = i∈A(x) x i - 1 2 i∈A(x) x i (x i + δ(Gx) i ) ≥ 1 2 i x i
for any x ∈ Z, as x i (x i + δ(Gx) i ) ≤ x i for any i ∈ A(x). Now the equality holds if and only if x i + δ(Gx) i = 1 for any i ∈ A(x).

Proof of Theorem 2. If x is a Nash equilibrium such that A(x ) ⊂ Ã(x) then by second point of Lemma 5 we have

P (x ) -P (x) = - 1 2 i∈SI(y) x i (1 -δ(G Ãy) i ),
thus P (x ) ≥ P (x) with equality if and only if A(x) ∩ SI(x ) = ∅.

• Let us prove that (ii) implies (iii). Under (ii) we have P (x ) = 1 2 i x i ≤ 1 2 i x i = P (x). Hence P (x) = P (x ), which means that A(x) ∩ SI(x ) = ∅, that is (iii) holds.

• Suppose now that (iii) holds. We then have P (x) = P (x ) for any Nash equilibrium x such that A(x ) ⊂ Ã(x). In other terms, x à is a global maximum of P Ã. By Lemma 4 this derives (i).

• At last Let us prove that (i) implies (ii). Pick y ∈ Z such that A(y) ⊂ Ã(x). Suppose by contradiction that i y i > i x i . We then have P (y) ≥ 1 2 i y i > P (x). Let u = yx. For any ∈ [0, 1] we have x + u ∈ S and, by first point of Lemma 5,

P (x + u) -P (x) = - 2 2 u 2 + u, δGu .
In particular, 0 < P (y)-P (x) = -1 2 u 2 + u, δGu , which means that u 2 + u, δGu < 0 and concludes the proof that (i) ⇒ (ii).

Algorithm implementing Theorem 2:

Consider a network G and an equilibrium x. STEP 1: Find the set Ã(x) and form the network G Ã(x) by deleting agents that are strictly inactive in x. Form all the different possible subsets of agents in Ã(x), including the empty set. Index these subsets by i. For each subset i: STEP 2: Construct the subgraph G i Ã(x) by deleting the agents in subset i from G Ã(x) and compute its lowest eigenvalue λ min (G i Ã(x) ). • STEP 2.1: If λ min (G i Ã(x) ) > -1/δ then there is a unique equilibrium y on G i Ã(x) where every agent is active. It is obtained by inverting the matrix I + δG i Ã(x) and summing the lines. Set y j = 0 for all the agents that have been deleted, check if this new profile is a Nash equilibrium on G and check if at least one agent j who has been deleted is strictly inactive at that profile.

-STEP 2.1.1: If both conditions are true, then x is not a local maximum.

-STEP 2.1.2: If at least one condition is not true, turn to subset i + 1 and go to STEP 2 • STEP 2.2: If λ min (G i Ã(x) ) ≤ -1/δ, then turn to subset i + 1 and go to STEP 2 If all subsets have been tested, then x is a local maximum.

Obviously this algorithm can be adapted in case we do not have an equilibrium to start with: every time the algorithm goes to STEP 2.1.1, then compute the sum of efforts of the corresponding equilibrium and store the value. At the end of the program, compare all values.

The equilibrium with highest value is a global maximum.

Proofs of Section 6

Proof of Proposition 7. The proofs of Lemma 1, Lemma 2 and Proposition 3 carry through naturally for the dynamics ẋ = V (x) under Hypothesis 1 and 2. The proofs of Theorem 1 and Theorem 2 only rely on these three results.

Proof of Remark 5. The form of the best responses (1) directly implies that Hypothesis 1 holds. The proof that (BRD) satisfies Hypothesis 2 can be found in [START_REF] Bramoullé | Strategic interaction and networks[END_REF] for instance but we provide it for convenience. It amounts to showing that, for any x / ∈ N E we have DP (x), -x + Br(x) = i

(1x iδ(Gx) i )(-x i + Br i (x -i )) > 0.

Let i be such that x i = Br i (x -i ). Then

• if BR i (x -i ) > 0, then Br i (x -i ) = 1δ(Gx) i . This implies (1x iδ(Gx) i )(-x i + BR i (x -i )) = (1x iδ(Gx) i ) 2 > 0, since x i = Br i (x -i ).

• if Br i (x -i ) = 0, then 1δ(Gx) i ≤ 0 < x i (since x i = Br i (x -i )) and (1

-x i - δ(Gx) i )(-x i + BR i (x -i )) = -x i (1 -x i -δ(Gx) i ) > 0.
This concludes the proof.

Proof of Proposition 8. Let x ∈ Λ be a specialized Nash equilibrium and î ∈ A(x) be such that |G[ î, x]| = p(Λ). Let x * be defined by

x * i = 1 if i ∈ A(x) \ { î}, x * i = 1/p if i ∈ G[ î, x
] and x * i = 0 otherwise.

Then x * ∈ Λ. Define now x 0 as the following: x 0,i := x * i for i / ∈ G[ î, x] and x 0,i = 1/p if i ∈ G[ î, x]. Then ∀t ∈ N we have

x t,i = x * i ∀i / ∈ G[ î, x]; x t,i = x t,j ∀i, j ∈ G[ î, x], hence x t only depends on the quantity z t defined as the common value of the x t,i , when i ∈ G [ î, x]. We now show that, lim inf t→+∞ |z t -1/p| > 0, which will conclude the proof. Note that

z t+1 = (1 -κ)z t + κ(1 -(p -1)z t ) = (1 -pκ)z t + κ if z t ≤ 1 p-1 , (1 -κ)z t if z t > 1 p-1
As a consequence if |z t -1/p| < 1 p(p-1) then z t+1 = (1pκ)z t + κ. Thus |z t+1 -1/p| = |1 -pκ||z t -1/p|. If κ ≥ 2/p then lim inf t→+∞ |z t -1/p| > 0.18 Proof of Proposition 9. We now prove the following claims, which formally rephrase the statement of Proposition 9: let Λ be a compact connected set. Then: (i) Λ is an attractor for (BRD) if and only if it is an attractor19 for (SimBR κt ): there exists an open neighborhood U of Λ and T 0 > 0 such that for every T ≥ T 0 we have lim On the other hand if Λ is not an attractor for (BRD) then given any open neighborhood U of A, there exists x ∈ U such that lim inf t→+∞ d(x t , Λ) > 0 if x 0 = x.

Proof of (i): First note that, given any bounded set U , there exists some positive constant c > 0 (that might depend on U ) such that, if x t ∈ U we have the following inequality: P (x t+1 ) -P (x t ) ≥ κ t -x t + Br(x t ) | 1x t -Gx tκ 2 t c .

Suppose that Λ is a local maximizer of P and pick an open neighborhood U of P such that P (x) < P (Λ) for any x ∈ U \ Λ. Let V (a) := {x ∈ U : P (x) > P (Λ) -a}20 and V n := V (2 -n ). We claim that there exists an increasing family (T n ) n∈N such that if x T 0 ∈ V 0 then x t ∈ V n and for any t ≥ T n . This will conclude the proof that Λ is an attractor. Since d(V n \ V n+2 , N E) > 0 there exists a constant c n > 0 such that -y + Br(y) | 1y -Gy > c n for any y ∈ V n \V n+2 . Let τ n be an increasing sequence of real numbers such that c n κ t -c κ 2 t ≥ c n κ t /2 for any t ≥ τ n . We now construct the sequence (T n ) n as follows: let T 0 := τ 0 . Given T n , define T n+1 as the following:

T n+1 = max{τ n+1 , T n + s n },
where s n := min{s > 0 : Tn+s Tn κ t > 1 2 n cn }. By contruction, if x Tn ∈ V n then x T n+1 ∈ V n+1 . Indeed if x t ∈ V n+1 for some t ≥ T n then x s ∈ V n+1 for any s ≥ t. Suppose now that x T n+1 / ∈ V n+1 . Then P (x T n+1 ) ≥ P (x Tn ) + c n /2 Tn+sn t=Tn κ t ≥ P (Λ) -1 2 n + 1 2 n+1 = P (Λ) -1 2 n+1 , a contradiction. This concludes the proof.

Suppose now that Λ is not a local maximizer of P , let U be an open neighborhood of Λ and T 0 > 0. Choose x ∈ U such that P (x) > P (Λ) and let V := {y ∈ U : P (y) ≥ P (x)}. Since we have d(V, N E) > 0, by continuity of the best responses there exists a constant c > 0 such that for any y ∈ V we have -y + Br(y) | 1y -Gy > c Hence, if x t ∈ V we have

P (x t+1 ) -P (x t ) ≥ c t - c t 2
Choose now T > T 0 large enough so that c T -c T 2 > 0. Clearly lim inf t d(x t , Λ) > 0 and (7.3) does not hold.

Proof of (ii). We first note that the potential is (strictly) increasing with time as long as the process does not reach a Nash equilibrium: more precisely we claim that P (x t+1 ) ≥ P (x t ); P(P (x t+1 ) > P (x t ) | x t /

∈ N E) > π

Figure 1 :

 1 Figure 1: The kite. Circles in white represent inactive players. Circles in grey represent active players.The darkest the circle, the highest the action played. In particular, circles in black represent players playing 1. Left panel: a continuum of equilibria; right panel: an isolated equilibrium.

Proposition 2

 2 If the graph G admits two maximal independent sets M and M such that |M | = |M | = p and |M ∩ M | = p -1, then G supports a continuum of Nash equilibria when δ = 1.

Figure 3 :

 3 Figure 3: Components of active agents (in dotted lines) and the subgraphs induced by their influence sets (in solid lines).

  Figure 4: A 5 agents network. Left panel: Λ 1 , a continuum of equilibria containing two specialized equilibria; Middle panel: Λ 2 , an isolated equilibrium; Right panel: Λ 3 , a continuum without any specialized equilibria.

Figure 5 :

 5 Figure 5: An example with 5 players. The initial action profile (upper left panel) is a Nash equilibrium.In the second action profile (upper right panel), efforts are "transferred" from one agent to another in the triangle and yet, the profile remains in the Nash component. The final profile (lower panel) is a specialized Nash equilibrium.

  Figure 6: An 8-agents graph

Figure 7 :

 7 Figure 7: Left panel: component Λ 1 , (singleton); middle: component Λ 2 , right: component Λ 3 .

  t (T, x), Λ) = 0, where φ t (T, x) denotes the value of the (unique) solution of (10) such that x(T ) = x.(ii) If Λ is an attractor for (BRD), with basin of attraction of Λ. ThenP lim t→+∞ d(x t , Λ) = 0 | x 0 ∈ U = 1

Table 2 :

 2 Number of graphs having a given number of attractors. For instance, there are 853 nonisomorphic graphs with 7 agents. Out of these, 674 graphs have a unique attractor, 171 have two distinct attractors and 8 have three distinct attractors. The fraction of graphs having a unique attractor is 0.79.

	10

  Figure8: δ = 1/3. A subgraph containing two pairs and a six agents graph. The dark line means that both agents in both pairs are linked to all six agents in the bottom graph. Upper left panel: a Nash equilibrium x where the agents in the bottom graph are weakly inactive. Upper right panel: a non-Nash profile where the sum of efforts exceeds that of x. This is sufficient to conclude that x is not a local maximum. Lower Panel: A Nash equilibrium which is a local maximum, where active agents are now strictly inactive.

	3/4	3/4	3/4	3/4
				6/7	3/7	6/7

We say that a Nash equilibrium x is isolated if there is a neighborhood around x that contains no other Nash equilibrium.

The maximum independent sets of a network are the largest maximal independent sets.

As opposed to strictly inactive agents, who produce no effort and where it would take a severe reduction in neighbors' efforts for them to start producing.

We will also denote by G the corresponding adjacency matrix.

The list of non-isomorphic graphs was found at http://users.cecs.anu.edu.au/ bdm/data/graphs.html. We thank Alex Teytelboym for providing this link to us.

Although we consulted with graph theorists, we were unable to prove this conjecture. In particular, we were unable to characterize graphs for which all maximal independent sets have order at least 2, which are graphs that do not support a continuum. Complete k-partite graphs are an example of such graphs.

Let S be a subset of R N . Then S is invariant for the flow ϕ if a) ∀x ∈ S, ∀t ∈ R, ϕ(x, t) ∈ S, and b) ∀y ∈ S, ∀t ∈ R, there exists x ∈ S such that ϕ(x, t) = y

[START_REF] Bramoullé | Public goods in networks[END_REF] and[START_REF] Bramoullé | Strategic interaction and networks[END_REF], the authors consider asymptotic stability of isolated equilibria with respect to the (respectively discrete-time and continuous time) Best-Response Dynamics, which is precisely the definition of an attractor restricted to singleton components. An isolated equilibrium x is asymptotically stable if and only if point (ii) holds with A = {x}. However when an equilibrium is not isolated, (ii) cannot hold with A = {x}. This explains, for instance, why[START_REF] Bramoullé | Strategic interaction and networks[END_REF] find that the pair has no stable equilibrium (see Proposition 4), because there are no isolated equilibria. As we will see, with the notion of attractor, it appears that the entire component is stable.

We prove a more precise statement in a companion unpublished paper: the omega limit-set is always a singleton, i.e. (BRD) converges. However, for the issue under scrutiny here, lemma 2 is enough.

This, by the way, implies that isolated interior equilibria cannot be stable.

Recall that λmin(G) denotes the lowest eigenvalue of G.

[START_REF] Bramoullé | Public goods in networks[END_REF], this statement was proved for κ = 1 but the proof can be adapted for any κ ∈]0, 1].

We need to make sure that r is small enough such that Ur = P -1 ([v -r, v]) ⊂ U

Since λ(Kn) = -1, where Kn is the complete network of size n, and λ(G) < λ(Kn) for any non-empty network G of size n different from Kn.

Carefully observe that if (P(t)) holds for t ∈ [tn, tn+1[ then P(tn+1) also holds, since no agent can be active at time tn+1 while being weakly inactive for t ∈]tn+1 -, tn+1[.

It is actually not hard to prove that (zt)t then converges to the periodic orbit1 1+p-κp , 1-p 1+p-κp

Note that (SimBRκ t ) is a non-homogeneous discrete-time dynamical system and the definition of attractor must be adapted accordingly.

Note that V (a) is a decreasing (as a goes to zero) family of open sets whose intersection is equal to Λ

Acknowledgments

We wish to thank Y. Bramoullé, F. Bloch and N. Allouch for useful conversations, three anonymous referees for their valuable insights, as well as participants of the several conferences where this work was presented. The authors thank the French National Research Agency (ANR) for their financial support through the program ANR 13 JSH1 0009 01. Mathieu Faure gratefully acknowledges the support of the French National Research Agency, under grant ANR CIGNE (ANR-15-CE38-0007-01).

Claim 1 Let Λ be an attractor for ẋ = -x + Br(x). Then Λ contains at least one specialized Nash equilibrium Claim 2 Let Λ be a connected component of NE containing some specialized Nash equilibria.

Then Λ is an attractor if and only if, for every specialized Nash equilibrium x that it contains, x is a local maximum of P Proof of Claim 1. Let Λ be an attractor, that we assume to be connected without loss of generality. We need to prove that it intersects the set of specialized Nash equilibria. let x ∈ Λ and assume without loss of generality that x is not specialized. Let A(x) = C 1 ∪ C 2 ∪ ... ∪ C K be the decomposition (6) according to the active agents in x. Since Λ is an attractor, every G[C k , x] is a complete graph by proposition 4. Since G A(x) is a union of complete graphs, one of which is not a singleton (otherwise x would be specialized), we have λ min (G A(x) ) = -1. Let u ∈ R |A(x)| be a unit eigenvector associated with eigenvalue -1 and v ∈ R N be defined by

We then have P (x + λv) = P (x) by Lemma 5. Thus, as long as x + λv ∈ R N + , it is a Nash equilibrium. Indeed assume that this is not the case. Then there would exist λ 0 > 0 such that x + λ 0 v ∈ Λ and x + λ n v /

∈ N E for some sequence

This is in contradiction with the fact that x + λ 0 v is a local maximum of P and therefore in contradiction with the fact that Λ is an attractor. Now let λ := max{λ > 0 : x + λv ∈ R N + }. Necessarily there exists i ∈ A(x) such that x i + λv i = 0. Clearly x + λv ∈ Λ and |A(x + λv)| < |A(x)|. By reiterating this reasoning, the set of active agents will be reduced until every component is a singleton, i.e. until reaching some x that is specialized.

Proof of Claim 2. The first implication is a direct consequence of Proposition 3.

For the reverse implication, assume Λ is a connected component of Nash equilibria that intersects the set of specialized Nash equilibria and suppose that every specialized Nash equilibrium in Λ is a local maximum of P . Consider any x ∈ Λ with decomposition of actives C 1 , ..., C k . We must prove that G[C k , x] is complete for all k = 1, ..., K, since that will guarantee that x is a local maximum. Pick any specialized Nash equilibrium x and any continuous path x : [0, 1] → Λ such that x(0) = x, x(1) = x. Denote by (C t k ) k=1,...,K(t) the decomposition of actives in x(t), that is

To prove this, suppose that x / ∈ N E, pick i such that x i = Br i (x -i ) and consider x defined as

It is sufficient to show that P (x ) > P (x).

In both cases P (x ) -P (x) > 0, which concludes the proof of the claim. Now let x 0 = x ∈ U . Since P (x t ) is an increasing sequence it must converge. Let P * < P (Λ). Is is sufficient to prove that P (lim t→+∞ P (x t ) ≤ P * ) = 0. On the event {lim t→+∞ P (x t ) ≤ P * }, by continuity of the best responses, there exists some constant c > 0 and some agent i(t) ∈ N such that |x

)| ≥ c > 0 for any t ≥ 0. However we proved that, for any t ≥ 0,

which implies that P P (x t+1 ) -P (x t ) ≥ 1 2 c 2 ≥ π for any t. This contradicts the fact that lim t P (x t ) = P * and the first part is proved. Now to prove the second statement pick x ∈ U such that P (x) > P (Λ) and x 0 = x. Then P (x t ) ≥ P (x 0 ) for any t ≥ 0. Hence lim inf t→+∞ P (x t ) ≥ P (x 0 ) > P (Λ) which proves the result.


Arnaud Travert
email: arnaud.travert@ensicaen.fr

IR OPERANDO STUDY OF THE DYNAMICS, THERMODYNAMICS AND INTRINSIC CRACKING KINETICS OF ALCANES IN ZEOLITES

Keywords: IR operando spectroscopy, alkanes, zeolites, activation entropy, diffusion

INTRODUCTION

The monomolecular cracking of alkanes over zeolites, discovered by Dessau and Haag thirty five years ago [START_REF] Haag | Proc. 8th Int. Congress Catal[END_REF], can be considered as archetypal of acid-catalyzed reactions. Because of the interplay between adsorption and surface kinetics, the interpretation of structureactivity trends have long been subject to discussion. It is now generally admitted that the variations of apparent cracking rates are primarily governed by the intrinsic kinetics [START_REF] Gounder | [END_REF][3][4][5][6]. However, strong discrepancies still persist as to the rate parameter which determines these changes, i.e. activation entropy [START_REF] Gounder | [END_REF][3][4] vs. activation energy [5], as well as the magnitude of these parameters, in particular entropic factors. Overall, depending on the studies, the estimates of the coverage of active sites and of the intrinsic kinetics span several order of magnitude [START_REF] Gounder | [END_REF][3][4][5][6][7]. The origin of these huge discrepancies lies in the absence of experimental measurement of the coverage prevailing at reaction conditions, which up to now could only be assessed by extrapolation of low temperature measurements [START_REF] Gounder | [END_REF]3] or state of the art simulations [3][4][5][6][7]. In this lecture, we will show how infrared operando spectroscopy can be used to determine the coverage of active sites by alkanes in transient or steady state conditions, thus allowing determining alkane diffusion coefficients in micropores, adsorption equilibruium constants and intrinsic cracking kinetics of the alkane-acid sites complexes by IR operando spectroscopy [8,9,10].

RESULTS AND DISCUSSION

It will be shown that the reactive state of the alkanes in the zeolite, hydrogen bonded OHalkane complexes, can be identified unambiguously and quantified at reaction conditions using IR operand spectroscopy. Further, we have been able to study the contribution of the two types of weak interactions prevailing in the zeolite pores -H-bonding vs. van der Waals -on the adsorption parameters of n-alkanes. This was achieved by employing a new experimental technique combining gravimetric analysis and IR spectroscopy.

The determination of the coverage can in turn be used to determine the intrinsic cracking kinetic parameters by correlating the apparent rates with the coverage of the bridged OH groups. Our results show that the intrinsic activation energies are constant for all the alkanes and zeolites investigated in this study (187 ± 4 kJ mol -1 ) lying in the lower range of values currently predicted by from low temperature adsorption experiments or molecular simulations On the other hand, significant differences were found in activation entropies which consistently increased with the alkane chain length and the decrease of characteristic pore or cage size of the zeolite. Examination of the entropic balance shows that the confinement primarily decreases the entropy of the adsorbed state while the entropy of the transition states is much less affected. For instance, the entropy of adsorbed propane is lowered by ~25 J mol -1 K -1 in H-FER with respect to HMFI, whereas the entropy of the corresponding transition states differs by only ~5 J mol -1 K -1 .

-30 Analysis of the selectivities of these reactions shows that they are also ruled by entropic parameters, leading to a symmetric, pairwise distribution of lower alkane products. It will be shown that a model where adjacent CC bonds involved in the cracking reaction equally contribute to the activation entropy through the loss of their torsional degrees of freedom at the transition state consistently accounts for the activity trends and the observed symmetric distribution of products.

CONCLUSIONS

In summary, the application of IR operando methodology to the study of protolytic cracking of alkanes has allowed for the first direct experimental assessment of the intrinsic parameters of this reaction with inprecedented precision. Our data confirm that the relative monomolecular cracking rates of alkanes over zeolites are chiefly controlled by their intrinsic activation entropies at high temperature. IR spectroscopy allows for unambiguous definition and quantification of the initial state of the reaction, namely alkane-acid site hydrogen bond complexes at reaction conditions, which is key to properly quantify adsorption and activation entropic terms. Further, the confidence intervals of activation parameters determined by operando spectroscopy were found lower than those currently predicted by state of the art calculations. In this respect, the present work could provide guidelines for theoretical predictions of alkane adsorption and reactivity on zeolites acid sites at elevated temperatures. The applicability of the methodology and concepts developed here to other zeolite types and reactions will be discussed.

Figure 1 :

 1 Figure 1: Relationship between monomolecular cracking activation entropy and confinement index.