Int J Game Theory DOI 10.1007/s00182-015-0463-0

Information, interaction and memory V. Masson

Accepted: 12 January 2015 © Springer-Verlag Berlin Heidelberg 2015

Abstract This paper extends previous work on evolutionary games by introducing non-trivial memory into a model where information flows and interactions are captured using networks, as in Alós-Ferrer and Weidenholzer (J Econ Theory 143:251– 274, 2008). We consider two-player K × K coordination games and analyze best response dynamics as well as imitation dynamics. We show that for any arbitrary information network, including those with asymmetric information exchanges, the introduction of non-trivial memory corroborates the results of previous studies: with best response, agents select the 21 -dominant strategy while imitators favor efficiency. Furthermore, we expose the sensitivity of the efficiency results to the interaction patterns. Keywords

Contagion · Networks · Coordination games · Best response · Imitation

1 Introduction The question of equilibrium selection based on evolutionary dynamics was originally addressed by the papers of Foster and Young (1990), Kandori et al. (1993), Matsui (1991), Robson (1990), and Young (1993a, 1998b). From these seminal studies, it became apparent that the selection process depends on the way information flows between agents, how they interact with each other and the type of memory they have. Typically, these models consider a population of agents who play a coordination game that exhibits tension between efficiency and risk dominance, as defined by Harsanyi and Selten Harsanyi and Selten (1988). In order to choose which strat-

V. Masson (B) School of Economics, The University of Adelaide, Adelaide, SA 5005, Australia e-mail: [email protected]

123

V. Masson

egy to play, agents use information about current and/or past plays. The information they access and how they use it usually depends on three factors: memory length, behavioural rules and sampling procedures. The analysis is often conducted on a mistake-free environment, and then extended to a perturbed one where agents’ mistakes or experiments allow the identification of the stable sets. If the selection of the risk dominant outcome prevailed in Foster and Young (1990), Kandori et al. (1993) and Young (1993a), changes to the informational structure showed it was possible to select the efficient outcome, as illustrated by Robson (1990) through the argument of secret hand shake and by Matsui (1991) through the introduction of cheap talk. This lead us to investigate further the dependence between equilibrium selection and informational structure. In this paper, we contribute to this literature by introducing non-trivial memory into an evolutionary framework where information flows and interactions are modeled using networks. The game played is a K × K coordination game which has a 1 2 -dominant action, as defined by Morris et al. (1995). We find that when agents imitate efficiency is favored in the long-run, while the 21 -dominant action is preferred when agents use best-response. To this extent, these results complement the findings of previous studies with best-response dynamics, e.g. KMR Kandori et al. (1993), Ellison (1993), and Young (1993a), and imitation dynamics, e.g. Robson and VegaRedondo (1996) and Alos-Ferrer and Weidenholzer (2006), Alós-Ferrer and Weidenholzer (2008). Our approach considers agents with bounded memory, as in Young (1993a, b, 1998a, b), Sarin (2000), Alós-Ferrer (2004, 2008), Alós-Ferrer and Shi (2012), and shows that the introduction of non-trivial memory does not affect the results of the selection process. It also complements evolutionary studies where information flows and interactions are modeled using networks, e.g. Ellison (1993) and Morris (2000). Here, we follow the approach of Durieu and Solal (2003), Mengel (2009), and AlósFerrer and Weidenholzer (2008), where the information and the interaction networks are distinct, with the notable difference that our networks need not overlap. This allows us to highlight the sensitivity of some results to the interaction network, as in Jackson and Watts (2002). Amongst current literature, this study is most closely related to that of Alós-Ferrer and Weidenholzer (2008) who examine imitation in networks where the information neighborhood might be larger than the interaction neighborhood. However, we introduce asymmetric information flows using a directed network and focus on twoplayer K × K coordination games with best response as a possible behavioural rule. We show that the 21 -dominant uniform convention emerges as stochastically stable when the sample size is within specific bounds and agents are best repliers. Also, we find that the efficient uniform convention is stochastically stable under certain conditions when agents imitate. However, efficiency results are sensitive to variations of the interaction network. In Sect. 2, we describe the networks, the game played by the agents and the decision rules used. Absorbing sets and stochastically stable sets are presented in Sect. 3. Section 4 concludes.

123

Information, interaction and memory

2 The model First, we introduce the information network and decompose its graph into strongly connected components, as these play a major role in describing the absorbing sets of the system. We then describe the interaction network and ensure that the pairing of all agents is always possible. Finally, we describe the game played and explain how agents choose their actions, using either imitation or best response. 2.1 Networks 2.1.1 Information network We represent the information network as a directed graph over the set of agents I = {1, 2, ..., 2n} with adjacency matrix G. An element gi j of the adjacency matrix equals 1 if there is an information flow from i to j (i.e. i → j) and 0 otherwise. To allow for non-reciprocal information exchanges, gi j need not equal g ji .   For every agent i ∈ I , we define a set of neighbors Ni = j ∈ I, g ji = 1 . We assume that agent i accesses his own information, i.e. gii = 1 and hence i ∈ Ni . Agents remember their m < ∞ most recent actions and corresponding payoffs which is what we refer to as information. Since we consider any information network, we want to decompose the network into tractable objects. In order to do so, we first introduce the notion of directed path: Definition 1 A directed path between two vertices i 0 and i k denoted Pi0 ik is a nonempty directed graph with distinct vertices {i 0 , i 1 , ..., i k } for which gir −1 ir = 1 for all ir , r = 1, ...k. A directed path is therefore a sequence of directed links from one agent to another. When a directed path Pi j exists, it captures the influence agent i can exert over agent j through transmission of information, but it does not guarantee that agent j observes agent i’s information. If a directed path exists between any pair of agents within a group of agents, it forms a strongly connected component (SCC). Definition 2 A strongly connected component C ⊆ I of an information network is a maximal set of vertices such that for all i, j ∈ C, with i = j, directed paths Pi j and P ji exist. As every directed graph is a directed acyclic graph of its SCCs, it is possible to uniquely decompose an information network into its strongly connected components1 and identify the channels by which information disseminates through the population. There are two main types of SCCs: source (no incoming edge) and sink (no outgoing edge). Formally, Definition 3 A strongly connected component C ⊆ I of an information network is said to be source if there are no i ∈ I \C and j ∈ C such that gi j = 1. 1 See Dasgupta et al. (2006).

123

V. Masson

Hence, agents within a source SCC never receive information from agents outside the SCC. Similarly, Definition 4 A strongly connected component C ⊆ I of an information network is said to be sink if there are no i ∈ I \C and j ∈ C such that g ji = 1. The difference between this definition and the previous one resides in the change from gi j = 1 to g ji = 1. Therefore, agents in a sink SCC never provide information to agents outside their SCC. Finally, an SCC whose agents never provide nor receive information to and from other SCCs is called disconnected. Definition 5 A strongly connected component C ⊆ I of an information network is said to be disconnected if it is source and sink. For the rest of the paper, we denote C = {C1 , ..., Ck , ...} the set of all SCCs of the information network, and S the set of all source SCCs of the information network. Example In order to provide a better understanding of the above-mentioned definitions, Fig. 1 reports an information network featuring nine SCCs. Figure 1 Panel A illustrates the network at the agent level, while Fig. 1 Panel B exemplifies the decomposition of the network into SCCs. For purposes of clarity, we did not draw edges from an agent to himself and this convention is adopted throughout the paper. Three of the SCCs are source: C1 , C7 and C9 ; six are sink : C2 , C3 , C4 , C6 , C8 , and C9 ; one is neither source nor sink: C5 ; one is identified as being both, source and sink, and is therefore disconnected: C9 .

C4 C9

C1 C3

C2

C8

C5

C7

Panel A

C6

Panel B

Fig. 1 Decomposition of an information network into the directed acyclic graph of its strongly connected components

123

Information, interaction and memory

2.1.2 Interaction network All potential interactions are described by an undirected graph with agents as vertices. An edge (undirected link) between two agents represents the possibility that these agents could be paired to play the game. Denote M the adjacency matrix of the graph. An element m i j of M is equal to 1 if there is a probability in the interval (0, 1] that agents i and j can be paired, and 0 otherwise. Of course, m ii = 0 and m i j = m ji for all i ∈ I . Although our interaction network resembles that of Alós-Ferrer and Weidenholzer (2008), it is important to note that the interactions it captures are only potential. An interaction neighbourhood in our framework reflects the pool of potential partners one may be paired with for playing the game. We define a matching of a set of vertices V in graph (V, E) as a set E  ⊆ E of pairwise non-adjacent edges; that is no two edges have a common vertex. A perfect matching is one that matches all vertices in V . To ensure every player can be paired with exactly one partner, we thus assume the following: Assumption 1 For any perfect matching of I  ⊆ I there exists a perfect matching of I \ I . Example To illustrate this assumption and the role it plays, we consider four agents numbered from 1 to 4. Figure 2 illustrates an interaction network where m 12 = m 13 = m 24 = 1 but m 14 = m 23 = m 34 = 0. In this case, Assumption 1 is violated since for I  = {1, 2}, there is no perfect matching of {3, 4}. The interaction network need not be connected. For example, an interaction network whose graph is represented by the union of disjoint complete bipartite subgraphs fulfils the requirement imposed by Assumption 1. By defining the interaction network this way we can, for example, restrict some agents from ever being paired with one another. Or, follow previous studies, and model that information neighbors are more likely to be paired. We can also account for rare or infrequent encounters. In the next section, we introduce the game played every period and describe in detail the decision rules which agents follow. 2.2 The game We consider a two-player symmetric coordination game. The set of pure strategies is denoted S and contains K strategies, i.e. S = {s1 , s2 , ..., s K }. If one agent plays Fig. 2 Interaction network violating Assumption 1

1

2

4

3

123

V. Masson

strategy sk against an agent who chooses strategy sl , the payoff of the first player is denoted u(sk , sl ). We focus our attention on strict coordination games, as in AlósFerrer and Weidenholzer (2007), i.e. games where coordination on any pure strategy is a strict Nash Equilibrium. Formally, u(sk , sk ) > u(sl , sk ) for all sk , sl ∈ S with k = l. Furthermore, without loss of generality, we order strategies such that: u(sk , sk ) > u(sl , sl ), if k < l. We thus refer to s1 as the efficient action. In most of the literature, particular attention is given to the case where K = 2. In this case, it is common to define q as the probability associated with playing action s1 in the mixed strategy Nash Equilibrium of the game. If q ≥ 1/2, then action s2 is said to be risk dominant as defined by Harsanyi and Selten (1988). The higher the value of q, the more risk dominant action s2 is. To accommodate larger K × K games, Morris et al. (1995) generalized the notion of risk dominance by introducing the concept of 21 -dominance. A strategy sk is said to be 21 -dominant if it is a best response to all mixed strategy profiles which involve at least a probability of 21 on strategy sk . This notion is almost inescapable when looking at the dynamics of a system under best response. This is why we assume that there exists s ∗ ∈ S s.t s ∗ is 21 -dominant. More general results for 3 × 3 coordination games however exist and are presented in Alós-Ferrer and Weidenholzer (2007). 2.3 Behavioral rules We consider two decision rules: best response (BR) and imitate-the-best (IM). The choice of these two rules is motivated by the different perspectives they offer. BR is concerned with the frequency of occurrence of each action and ignores realized payoffs, while for IM actions’ relative performances matter. Agents choose their action based on a sample of s observations taken randomly from the set of all observations in the last m periods they access from their neighbors. Using the terminology adopted by Alós-Ferrer (2004) and Alós-Ferrer and Weidenholzer (2008), agents observe the last m − 1 periods in addition to the current one. Models without memory hence assume m = 1, as in Kandori et al. (1993), and models with non-trivial memory where agents use all past information, as in Alós-Ferrer (2004) and Alós-Ferrer and Weidenholzer (2008), assume s = m. Denote s i,t the strategy of agent i at time t and S Pi,t the sample drawn by agent i at time t from his information neighborhood. Sample S Pi,t is a collection of strategy   and corresponding payoff pairs (s j,t , u j,t ), where t  ∈ [t, t − m + 1], j ∈ Ni , and   u j,t ∈ R corresponds to the payoff actually obtained by the sampled agent using s j,t . When using BR, agents focus only on the strategies present in the sample and ignore corresponding payoffs. In effect, they interpret the sample they drew as a mixed strategy and play best-response against it as in Young (1993a). Formally, denote Σ the set of

123

Information, interaction and memory

mixed strategies over S. Given σ ∈ Σ and sk ∈ S, σ (sk ) is the probability attached to sk by σ . The support of σ is thus given by P(σ ) = {sk ∈ S|σ (sk ) > 0}. Given a mixed strategy σ , the set of pure best responses to σ is denoted by B R(σ ) = {sk ∈ S|u(sk , σ ) ≥ u(sl , σ ), for all sl ∈ S, l = k} Hence, at time t, if agent i uses BR and observes only two strategies in his sample, agent i chooses to play s j and sl , which appear x times and y times   respectively, s i,t ∈ B R(σ ), where σ has support P(σ ) = s j , sl and σ (s j ) = xs , σ (sl ) = sy . With IM, we assume that agents base their decision on realized payoffs, and that an agent chooses to play the strategy associated with the highest payoff in the sample. Formally, s i,t = s j,t







with s j,t ∈ arg maxs j,t  ∈S Pi,t u j,t .

If an agent identifies more than one strategy using either BR or IM, we assume he chooses among them randomly. 3 Stability of the system 3.1 Absorbing sets of the process Define Θ, the state of the system in a given period, as the ordered collection of the m most recent strategies played by every agent i ∈ I . We refer to Θ k as the uniform convention where all agents played strategy sk for the last m periods. Similarly, Θ ∗ is the uniform convention involving the 21 -dominant strategy s ∗ . The dynamics described above define a finite Markov process over the state space for which standard techniques apply. First, we want to characterize the absorbing sets of the process. An absorbing set is defined as a minimal set of states that has positive probability to be reached but cannot be left. A singleton absorbing set is referred to as an absorbing state. These sets capture the stability of the system when agents make no mistakes, i.e. when agents choose their action according to one of the decision rules described above. Furthermore, these sets are also the only candidates for stochastic stability, which we will study later. The characterization of all absorbing sets necessitates that we introduce a number of concepts, the first of which is the notion of local state. Similarly to Θ, denote θC p , the local state within C p ∈ C, as the ordered collection of the m most recent strategies played by every agent i in C p . If all agents within C p played the same m most recent strategies, then θC p is called a local convention. It is denoted θ k if all agents in C p played strategy sk for the last m periods. Furthermore, denote L C p , the set of source SCCs which provide some information to C p . Formally,   L C p = Cl ∈ S s.t there are i ∈ Cl and j ∈ C p for which a directed path Pi j exists We can now state Proposition 1.

123

V. Masson

Proposition 1 Consider an arbitrary information network and an interaction network satisfying Assumption 1. Either all agents play IM or BR. If s ≤ m/2, a set of states is absorbing if and only if both conditions are satisfied: (1) ∀ C p ∈ S, θC p = θ k for some k ∈ {1, 2, ..., K } (2) ∀ C p ∈ C \ S, θC p = θ k if ∀ Cl ∈ L C p , θCl = θ k , for some k ∈ {1, 2, ..., K } .



Proof See Appendix.

As stated in Proposition 1, absorbing states are characterized entirely by the structure of the information network. Indeed, an agent who only observes one strategy does not switch, no matter the decision rule he uses and whom he interacts with. Intuitively, source SCCs play a regulatory role in the stability of the system as their agents never receive information from outside. Hence, if a source SCC follows a local convention, it cannot leave it. This is captured by the first condition of Proposition 1. However, for non-source SCCs, what is being played outside matters. In particular, if C p and all SCCs in L C p follow the same local convention, then θC p will not change, as only one strategy can be sampled. This is captured by the second condition of Proposition 1. On the other hand, when SCCs in L C p do not all follow the same local convention, C p may never settle in a local convention, as information related to more than one strategy can be sampled. Although this cannot be found in an absorbing state, it can be part of an absorbing set. The following example is an illustration of Proposition 1. Example Consider the information network presented in Fig. 1 and let K = 2. We identify L C p for each of the nine SCCs: L C2 = L C3 = L C4 = L C5 = {C1 } , L C6 = {C1 , C7 } and L C8 = {C7 }. Note that by definition, L C1 = L C7 = L C9 = ∅. Given the structure of the information network considered, there are eight possible absorbing sets: the two uniform conventions, and the 6 absorbing sets described in Table 1 below. In Table 1, each column represents the local state within each of the SCCs and hence each line characterizes an absorbing set. The notation θ stands for any local state within the SCC, including θ 1 and θ 2 . To relate our results to more commonly adopted assumptions in the evolutionary literature, we look at the case where information links are double-sided (symmetTable 1 Characterization of absorbing sets C1

C2

C3

C4

C5

C6

C7

C8

C9

Abs set # 1

θ1

θ1

θ1

θ1

θ1

θ1

θ1

θ1

θ2

Abs set # 2

θ1

θ1

θ1

θ1

θ1

θ

θ2

θ2

θ2

Abs set # 3

θ1

θ1

θ1

θ1

θ1

θ

θ2

θ2

θ1

Abs set # 4

θ2

θ2

θ2

θ2

θ2

θ2

θ2

θ2

θ1

Abs set # 5

θ2

θ2

θ2

θ2

θ2

θ

θ1

θ1

θ2

Abs set # 6

θ2

θ2

θ2

θ2

θ2

θ

θ1

θ1

θ1

123

Information, interaction and memory

ric information) and interactions only occur between information neighbors. Both assumptions are formalized below. First, information is symmetric: Assumption 2 For any i, j ∈ I, gi j = g ji . Then, the interaction neighborhood is contained in the information neighborhood, as in Alós-Ferrer and Weidenholzer (2008). Assumption 3 For any i, j ∈ I, m i j = 1 only if gi j = 1. One of the consequences of Assumption 2 is that the information network presents only disconnected SCCs. Furthermore, it is worth noting that Assumptions 1, 2 and 3 eradicate the possibility of neighborless agents. As suggested by Proposition 1, the role played by the interaction network in determining the absorbing sets of the system is irrelevant. Hence results presented in the following Corollary hold with or without Assumption 3: Corollary 1 Consider an arbitrary information network satisfying Assumption 2 and an interaction network satisfying Assumption 1. Either all agents play IM or BR. A set of sets is absorbing if and only if s ≤ m/2 and θC p = θ k for some k ∈ {1, 2, ..., K } for all C p ∈ S. Proof An information network satisfying Assumption 2 only possesses disconnected SCCs. Hence, all SCCs are source SCCs and all follow a local convention if and only if the system is in an absorbing set.

In other words, when information is symmetric, the system presents only absorbing states, where each of the SCCs follows a local convention. Our next step consists in perturbing the system so as to study its stochastic stability. 3.2 Stochastic stability We consider a perturbed version of the Markov process described above and study the stochastic stability of the system. The perturbed dynamics are generated by assuming that each player independently and with probability  > 0 in each period picks a strategy at random from a uniform distribution.2 Using the method of radius-coradius from Ellison (2000), we then identify stochastically stable sets. In what follows, we explain in more detail the concepts of radius and coradius. We then look at the stochastic stability of the system depending on the decision rule in place. 3.2.1 Radius and coradius Denote B(Θ) the basin of attraction of an absorbing set Θ. The basin of attraction of Θ is the set of initial states from which the unperturbed Markov process converges 2 Although we are fully aware of the criticism by Bergin and Lipman (1996) regarding the uniformity of the

perturbations, we believe that adopting uniform mistakes or experimentations is appropriate for our study.

123

V. Masson

to Θ with probability one. The radius of the basin of attraction of Θ, denoted R(Θ), is the mimimal number of mistakes needed to leave B(Θ) when play begins in Θ. The coradius of B(Θ), denoted C R(Θ), is the maximum over all other states of the minimum number of mistakes needed to reach B(Θ). A state Θ is said to be stochastically stable if R(Θ) > C R(Θ). In our framework, the Radius-Coradius method focuses entirely on source SCCs. If C p ∈ S leaves the local convention it follows under Θ for a local state that could lead it to switch convention, then we have left the basin of attraction of Θ. The number of mistakes needed to achieve such result is the Radius of Θ. For the computation of the coradius of Θ, we introduce Θ, the furthest possible state from Θ. Note that Θ may not be unique. Formally, consider C p ∈ S and let θCΘp be the local state of C p in state Θ. Then define Θ such that for all C p ∈ S : θCΘp = θ j if θCΘp = θ k with j either 1, ..., k − 1, k + 1, ..., K , such that the minimum number of mistakes required to switch from local convention θ j to local convention θ k is the largest. The Coradius of Θ is the minimum number of mistakes needed to go from Θ to B(Θ). In what follows, we study the stochastic stability of the system first with BR, and then with IM. The reason for such a split resides in the role, or absence of role, played by the interaction network in computing radius and coradius. Furthermore, since the radius of any absorbing state is 1 when s = 1, which means that the expression R(Θ) > C R(Θ) can never be satisfied, we conduct our analysis with a sample size s ≥ 2. 3.2.2 BR and stochastic stability: only information matters Since BR depends only on the frequency of plays and ignores realized payoffs, the interaction network is irrelevant in determining stochastic stability. Hence, under BR, the stochastic stability of the system is relatively straightforward and entirely deducted from the properties of the information network. Denote x the value of x if x is an integer, or the integer part of x + 1 if x is not an integer. Also, denote by r the largest minimum number of mistakes required for a source SCC to switch from local convention θ k to local convention θ ∗ . Proposition 2 Consider an arbitrary information network and an interaction network satisfying Assumption 1. All agents play BR. If s ≤ m/2 and Car d(S) < r1s , the 2s

uniform convention Θ ∗ is stochastically stable.



Proof See Appendix.

Proposition 2 states that given certain restrictions on the sample size, when agents use best reply, the 21 -dominant uniform convention is stochastically stable. In particular, when Car d(S) = 1, i.e. when the information network contains only one strongly connected component, the expression Car d(S) < r1s is always true. 2s

123

Information, interaction and memory

Hence, when looking at connected undirected information graphs, such as rings, if agents use best reply, the risk dominant uniform convention prevails in the long run. This corroborates results by Ellison (1993) and Durieu and Solal (2003). Furthermore, since the interaction network plays no role in determining stochastic stability with BR, whether or not interactions occur only between neighbors is irrelevant. Hence, with BR, we can have a complete independence of the two networks and still draw some conclusion regarding the stochastic stability of the system. This is not however the case with IM. 3.2.3 IM and stochastic stability: both networks matter When all agents play IM, some assumptions tying up the two networks are required to get analytical results. We thus introduce the notion of an information hub. The information hub of a given source SCC, say C p , is the set of SCCs, including C p , whose agents can be reached through a directed path from some agents in C p . Formally, HC p = PC p ∪ C p where   PC p = Cl ∈ C \ C p s.t there are i ∈ C p and j ∈ Cl for which a directed path Pi j exists

In the example presented in Fig. 1 Panel B, there are three information hubs: HC1 = {C1 , C2 , C3 , C4 , C5 , C6 } , HC7 = {C6 , C7 , C8 } and HC9 = {C9 }. In what follows, we use this example to illustrate how the existence (or nonexistence) of interactions between agents from different information hubs can affect the computation of radii. Suppose that K = 2 and that the system presented in Fig. 1 Panel B is in an absorbing state Θ where C9 follows θ 2 while all other SCCs follow θ 1 . This is absorbing set # 1 in Table 1. To leave B(Θ), some mistakes from agents in either C1 , C7 or C9 are required, so that one of these three source SCCs can depart from its current local convention and possibly never return to it. We first consider C9 . The number of mistakes needed from some agents in C9 to leave B(Θ) depends on the interactions that can be realized. If agents from C9 cannot be paired with agents from other hubs, then two simultaneous mistakes made by two paired agents in C9 are necessary. This allows the highest payoff to be sampled, and hence, makes it possible for the system to leave B(Θ). If however an agent from C9 can interact with an agent outside C9 and makes the mistake of playing s1 , one mistake is enough. This agent from C9 then gets the highest possible payoff, which can then be sampled by other agents in C9 and prompts them to switch to s1 , thus allowing the system to depart from B(Θ). Another possibility for the system to depart from B(Θ) is to consider agents in either C1 or C7 . Either of these two source SCCs can lead the system out of B(Θ), if one agent makes s mistakes. Agents within the same source SCC can then draw samples which only contain s2 and thus switch to s2 . This is enough for the system to depart from B(Θ). It is worth noting that in this last case the number of mistakes is

123

V. Masson

independent of the interaction network. This is because the payoffs generated by s2 cannot surpass those from s1 . From our example, it is clear that R(Θ) is contingent upon two things: the sample size, and the ties existing between the information network and the interaction network. Since we consider s ≥ 2, R(Θ) is either 1 or 2, depending on whether agents from distinct information hubs can interact. Hence, we consider two possible scenarios: one that allows interactions within and between information hubs and one that restricts interactions within information hubs. The first scenario is formally captured by Assumption 4. Assumption 4 For any HC p and HCl , there exist i ∈ C p and j ∈ HCl such that m i j = 1. With Assumption 4, the propagation of mistakes is made easier, as illustrated earlier when agents from C9 could interact with agents from other information hubs. The radius of absorbing sets computed under this assumption are therefore expected to be lower than those computed under the next assumption. Assumption 5 captures the possibility that some segregation exists between information hubs, as exemplified earlier when agents from C9 could only be paired with themselves. In this case, agents from different information hubs cannot be paired. Furthermore, if two information hubs happen to have common SCCs, then agents within these SCCs can only interact with themselves. This makes it harder for a source SCC to leave its current local convention, and hence makes it harder for the system to leave the basin of attraction of its current absorbing set. Assumption 5 For any HC p and HCl , if HC p ∩ HCl = ∅, there are no agent i ∈ HC p and agent j ∈ HCl such that m i j = 1. Furthermore, if HC p ∩ HCl = ∅ then for any     agent i ∈ HC p ∩ HCl , m i j = 1 only if agent j ∈ HC p ∩ HCl . To compute the radius of every absorbing set, we first start by looking at both uniform conventions, as in both cases the interaction network is irrelevant, and move on to other absorbing sets where we consider Assumptions 4 and 5 respectively. Results are presented in Lemmata 1–4 in the Appendix. A couple of remarks regarding the possible candidates for stochastic stability are in order. From Lemma 1, we know that uniform conventions are always candidates for stochastic stability as their radius is always greater or equal to 2. All other absorbing sets also admit a radius greater or equal to 2 if Assumption 5 is satisfied, as stated by Lemma 3. However, under Assumption 4, absorbing sets that are not uniform conventions admit a radius of one (Lemma 2) thus eliminating them from the pool of possible stochastically stable sets. Results regarding the computation of coradii are presented in Lemma 4 in the Appendix. We now consider the stochastic stability of the system under Assumption 4 and Assumption 5 respectively. With Assumption 4, we already noted that the only relevant absorbing sets are the uniform conventions. It turns out that, given specific conditions on the sample size, Θ 1 is stochastically stable when interactions between agents from different hubs are allowed.

123

Information, interaction and memory

Proposition 3 Consider an arbitrary information network and an interaction network satisfying Assumptions 1 and 4. All agents use IM. If Car d(S) < s ≤ m/2, then Θ 1 is stochastically stable. Proof From Lemma 1, R(Θ 1 ) = s. Furthermore, from Lemma 4, under Assumption 4,

C R(Θ 1 ) = Car d(S). Hence, if s > Car d(S) then R(Θ 1 ) > C R(Θ 1 ). In Proposition 4, the interactions between agents from different information hubs makes it easier for SCCs to switch local conventions. This leads to a decrease in coradius, but it also leads to a decrease in the radii of absorbing sets that are not uniform conventions, thus precluding them from being stochastically stable. The stochastic stability of the uniform efficient convention is confirmed when Assumption 4 is replaced with Assumption 5. However, the requirements regarding the sample size differ and the allowed range becomes narrower in most cases. Proposition 4 Consider an information network and an interaction network satisfying Assumptions 1 and 5. All agents use IM. If 2 · Car d(S) < s ≤ m/2, then Θ 1 is stochastically stable. Proof From Lemma 1, R(Θ 1 ) = s. Furthermore, from Lemma 4, under Assumption 5,

C R(Θ 1 ) = 2 · Car d(S). Hence, if s > 2 · Car d(S) then R(Θ 1 ) > C R(Θ 1 ). When agents imitate, and given specific conditions on the sample size, the efficient convention is stochastically stable, whether interactions between information hubs are allowed or not. These results confirm the conclusions made by Alós-Ferrer and Weidenholzer (2008), and also highlight the sensitivity of the requirements regarding the sample size to the interaction network. Broader interactions, i.e interactions between agents who belong to different information hubs, widen the possible range of the sample size, thus making the stochastic stability of the efficient uniform convention more likely. 4 Conclusion This paper introduces non-trivial memory in an evolutionary model where information exchanges and interactions are modeled using distinct networks. We first fully characterize medium run outcomes for arbitrary networks, and show that these results are independent of the interaction network and the decision rule used by the agents. In other words, for medium run predictions, only information is relevant. In the long run, we show that the 21 -dominant uniform convention prevails when agents are best repliers, and when the sample size is within certain bounds. The uniform efficient convention is also proven to be stochastically stable when agents imitate and the sample size belongs to some range which varies depending on the interaction pattens. We find that broader interactions facilitate efficiency by expanding the range of acceptable values of the sample size. In a way, agents do not need to sample as much when they are allowed to interact with agents from other hubs in order to reach efficiency.

123

V. Masson Acknowledgments I am particularly grateful to Fabrice Collard and Paul Pezanis-Christou for their interest in this paper, the multiple discussions we had and their very valuable support. I also would like to thank two anonymous referees for their constructive comments, Alexander Matros, Robert Garrard, Firmin Doko Tchatoka, Dimitriy Kvasov, Matthew Jackson, Kieron Meagher, Mandar Oak and audiences at UNSW, ANU and Massey University for their valuable comments and numerous suggestions. Also thanks to Mark Dodd, Steven Hail, Ros Whysall, Sam Henderson and Markus Brueckner for their comments at different stages of this manuscript.

Appendix Proof of Proposition 1 We define R p , the set of SCCs containing agents who are neighbors to other agents in C p , as follows:   R p = Cl ∈ C \ C p s.t there are i ∈ Cl and j ∈ C p for which gi j = 1 . Without loss of generality, let all source SCCs be of order 1. Denote OC p the order of C p ∈ C and define it as: OC p = maxCl ∈R p OCl + 1 This creates a partial order on the SCCs of the information network. This partial order is used to describe how a given action propagates from one SCC to another. In what follows, we first show that the states described in Proposition 1 are either absorbing or part of an absorbing set. We then demonstrate that these absorbing states are reached with positive probability from any arbitrary state. First, consider C p ∈ S. By definition, there are no i ∈ C p and j ∈ I \ C p such that g ji = 1. Hence if θC p = θ k with k either 1, 2...K , then agents in C p can only sample action k, thus maintaining the status quo. Therefore, when a source SCC follows a local convention, it never leaves it. Consider now C p ∈ C, with OC p = 2. By definition, ∃ i ∈ R p and ∃ j ∈ C p such that gi j = 1. This means that some agents in C p can sample the actions of some agents in R p . If θCl = θ k for all Cl ∈ R p , then agents in C p can only sample action k outside of C p . Since θC p = θ k as per condition 2 of Proposition 1, no agents in C p can sample an action different from k and hence, agents keep playing the same action. Applying this reasoning recursively to all SCCs of order greater than 2, one can see that if condition 2 is satisfied, then no agents change their action. Therefore, when both conditions are satisfied, the system is in an absorbing state or set. Note that nothing is mentioned in Proposition 1 when there are Cl ∈ R p and Cm ∈ R p such that θCl = θCm . In this case, agents in C p may sample different actions outside of C p and hence C p may not follow a local convention. This can happen in an absorbing set. The reasoning presented above holds whether all agents play BR or all agents play IM. We now need to show that these absorbing sets can be reached with positive probability from any arbitrary state.

123

Information, interaction and memory

Consider an arbitrary state Θ and without loss of generality let C1 ∈ S. Pick agent i in C1 . With positive probability, since s ≤ m/2, agent i can sample the same set of actions for s periods. Agent i thus plays a unique strategy k ∗ for his s most recent plays. From here, it is possible that agent i has a memory uniquely composed of k ∗ , as he can sample from himself. If agent i is the only agent in C1 , then C1 follows a local convention.   If car d(C1 ) > 1, let Ai = j ∈ C1 s.t gi j = 1 . We apply the same reasoning as the one presented above to all agents in Ai ∪ C1 . We then do so recursively to all agents whose neighbors belong to Ai ∪ C1 and so on. Thus, C1 can follow a local convention, which depends on agent i’s initial sample. By applying a similar argument to all C p ∈ S, we show that there is a positive probability that from any arbitrary local state, all source SCCs can follow a local convention. Once this is the case, we know that the local state within each of the source SCCs does not change. Consider now C p ∈ C \ S, with OC p = 2. By definition, there exist i ∈ C p and j ∈ L p such that agent i can sample the same action k for m periods from an agent in one of the source SCCs. In which case, the memory of this agent in C p who samples information from outside C p contains only action k. Following the reasoning described above, all agents in C p can then have a memory containing only action k. Furthermore, if all Cl ∈ L C p follow the same local convention θ k , then θC p = θ k for all periods after that. To complete the proof, the steps described above are repeated to SCCs of order 3, then to SCCs of order 4, and so on. This shows that the only absorbing sets are those described in Proposition 1.

Proof of Proposition 2 Consider C p ∈ S with θC p = θ j where strategy j = s ∗ , i.e. action j is not 21 -dominant.   With positive probability, one agent within C p , agent i, can make 21 s successive mistakes of playing action s ∗ . All agents in Ni ∩ C p can then sample the string of mistakes and play s ∗ for s periods. This is enough to create a memory containing only action s ∗ for all agents in Ni ∩C p . The same reasoning can be applied to the neighbors of these agents, and the neighbors of the neighbors of these agents within C p until   θC p = θ ∗ . Hence, R(Θ) = 21 s for any absorbing state Θ = Θ ∗ . Similarly, we can prove that R(Θ ∗ ) = r s, where r > 21 . Consider Θ and denote J the number of source SCCs which follow θ j , where s j = s ∗ under Θ. The number of source SCCs which follow the local convention θ ∗ is therefore equal to Car d(S) − J . Thus, under Θ, J source SCCs follow θ ∗ , and Car d(S) − J source SCCs follow Θ j where action j is the action which requires the least number of mistakes to convince agents to switch from s ∗ . Using the above arguments, we find that:  C R(Θ) = J r s + (Car d(S) − J )

1 s 2



123

V. Masson

with r > 21 . Hence, for  = ∗ , the condition R() > C R() becomes 1  1  r s > 1 2 s > J r s + (Car d(S) − J ) 2 s , which cannot be satisfied as 1 d(S ) and J +1−Car J Car d(S) < r1s 2s

2s

∗ ,

≤ 1. However, for  = and hence J=0, the condition becomes and can be satisfied for some s and Car d(S).

Lemma 1 Consider an arbitrary information network and an interaction network satisfying Assumption 1. All agents use IM and s ≥ 2. Then, R(Θ 1 ) = s and R(Θ k ) = 2 for some k ∈ {1, 2, ..., K }. Proof Consider Θ k = Θ 1 and C p ∈ S. We have θC p = θ k = θ 1 . If agent i ∈ C p , and his opponent simultaneously make the mistake of playing s1 , then agent i’s memory contains the highest possible payoff. Agent i’s neighbors can then sample this payoff and thus choose s1 . This also applies to the neighbors of agent i’s neighbors and so on. This is enough to leave B(Θ k ), sk = s1 . Hence, R(Θ k ) = 2, with k either 2, ...K . Similarly, we compute the radius of Θ 1 . Consider C p ∈ S which follows a local convention θ 1 . The system can leave B(Θ 1 ) if one agent in C p makes s successive mistakes of playing sk = s1 rather than s1 . This is because the neighbors of this agent can then draw samples uniquely composed of action sk = s1 , thus choosing action sk themselves. Applying this reasoning recursively to the neighbors of these agents, and then the neighbors of the neighbors of these agents and so on, we have left B(Θ 1 ).

Hence, R(Θ 1 ) = s. Lemma 2 Consider an arbitrary information network and an interaction network satisfying Assumptions 1 and 4. All agents use IM. Then, R(Θ) = 1 for any absorbing set Θ = Θ k , for some k ∈ {1, 2, ..., K }. Proof Since Θ = Θ k , there exist C p ∈ S and Cl ∈ S such that θC p = θ 1 and θCl = θ k = θ 1 . Also, from Assumption 4, there exist i ∈ C p and j ∈ Cl such that m i j = 1. Hence, there is a positive probability that agents i and j are paired and that agent j mistakenly chooses action 1, thus recording the highest possible payoff in his memory. Applying a similar reasoning to the one developed in the proof of Lemma 1, we have left B(Θ). Hence, R(Θ) = 1.

Lemma 3 Consider an arbitrary information network and an interaction network satisfying Assumptions 1 and 5. All agents use IM. Then, R(Θ) = 2 for any absorbing set Θ = Θ k , for some k ∈ {1, 2, ..., K }. Proof Since Θ = Θ k , there exist C p ∈ S and Cl ∈ S such that θC p = θ k = θ 1 and θCl = θ 1 . From Assumption 5, agents in C p [resp. Cl ] cannot interact with agents from a SCC which follows θ 1 [resp. θ k = θ 1 ]. To leave B(Θ), one agent from C p and the agent he interacts with can make two simultaneous mistakes. Or, an agent in Cl can make s successive mistakes. Using the arguments presented in the proof of Lemma 1, we can see that the value of the radius of Θ is 2.

Lemma 4 Denote by Car d(S) the total number of source SCCs and by 0 ≤ P ≤ Car d(S) the number of source SCCs which follow θ 1 under Θ. Consider an arbitrary

123

Information, interaction and memory

information network and an interaction network satisfying Assumption 1. All agents use IM. Then, for any absorbing set Θ

C R(Θ) =

sCar d(S) + P(1 − s) sCar d(S) + P(2 − s)

if Assumption 4 is satisfied; if Assumption 5 is satisfied.

Proof Consider Θ and denote P the number of source SCCs which follow θ 1 under Θ. By definition, P is also the number of source SCCs which follow θ k = θ 1 under Θ. The number of source SCCs which follow the local convention θ k = θ 1 under Θ is therefore equal to Car d(S) − P. We need to compute the number of mistakes needed to go from Θ to Θ. This means that Car d(S) − P source SCCs need to switch convention from θ 1 to θ k = θ 1 , and P source SCCs should go from θ k = θ 1 to θ 1 . When Assumption 4 is satisfied, only one mistake per source SCC following θ k = 1 θ is needed to switch local convention, and s mistakes are needed per source SCC following θ 1 to have them also switch their local convention. Hence, C R(Θ) = s(Car d(S) − P) + P = sCar d(S) + P(1 − s) if Assumption 4 is satisfied. With Assumption 5, agents from source SCCs following θ k = θ 1 cannot interact with agents playing action 1. Hence, each of these SCCs requires two mistakes to switch local convention. Furthermore, s mistakes per source SCC following θ 1 is needed. Therefore, C R(Θ) = s(Car d(S) − P) + 2P = sCar d(S) + P(2 − s) if Assumption 5 is satisfied.

References Alós-Ferrer C (2004) Cournot versus walras in dynamic oligopolies with memory. Int J Ind Org 22:193–217 Alós-Ferrer C (2008) Learning, bounded memory and inertia. Econ Lett 101:134–136 Alós-Ferrer C, Shi F (2012) Imitation with asymmetric memory. Econ Theory 49:193–215 Alos-Ferrer C, Weidenholzer S (2006) Imitation, local interactions, and efficiency. Econ Lett 93:163–168 Alós-Ferrer C, Weidenholzer S (2007) Partial bandwagon effects and local interactions. Games Econ Behav 61:1–19 Alós-Ferrer C, Weidenholzer S (2008) Contagion and efficiency. J Econ Theory 143:251–274 Bergin J, Lipman BL (1996) Evolution with state-dependent mutations. Econometrica 64:943–956 Dasgupta S, Papadimitriou C, Vazirani U (2006) Algorithms. McGraw-Hill, New York Durieu J, Solal P (2003) Adaptative play with spatial sampling. Games Econ Behav 43:189–195 Ellison G (1993) Learning, local interaction and coordination. Econometrica 61:1047–1071 Ellison G (2000) Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution. Rev Econ Stud 67:17–45 Foster D, Young P (1990) Stochastic evolutionary game dynamics. Theor Popul Biol 38:219–232 Harsanyi J, Selten R (1988) A general theory of equilibrium in games. MIT Press, Cambridge Jackson M, Watts A (2002) On the formation of interaction networks in social coordination games. Games Econ Behav 41:265–291 Kandori M, Mailath G, Rob R (1993) Learning, mutation and long-run equilibria in games. Econometrica 61:29–56 Matsui A (1991) Cheap-talk and cooperation in a society. J Econ Theory 54:245–258 Mengel F (2009) Conformism and cooperation in a local interaction model. J Evolut Econ 19:397–415 Morris S (2000) Contagion. Rev Econ Stud 67:57–78 Morris S, Rob R, Shin H (1995) p-dominance and belief potential. Econometrica 63:145–157 Robson A (1990) Efficiency in evolutionary games: Darwin, Nash and the secret handshake. J Theor Biol 144:379–396 Robson A, Vega-Redondo F (1996) Efficient equilibrium selection in evolutionary games with random matching. J Econ Theory 70:65–92

123

V. Masson Sarin R (2000) Decision rules with bounded memory. J Econ Theory 90:151–160 Young P (1993a) The evolution of conventions. Econometrica 61:57–84 Young P (1993b) An evolutionary model of bargaining. J Econ Theory 59:145–168 Young P (1998a) Conventional contracts. Rev Econ Stud 65:773–792 Young P (1998b) Individual strategy and social structure. Princeton University Press, Princeton

123