1. Introduction

Game theorists analyze the strategic aspects of interactions. Social network theorists analyze the structures that determine who interacts with whom. Game theory and social network theory meet when those who are connected via a network play a game. An emerging literature explores how players engaged in such network games can gradually settle into an equilibrium. In this literature, the network game is modeled as a dynamical system of players who interact with their neighborsFootnote ¹ and who adjust their strategies over time. The attracting points of certain dynamical adjustment processes are often Nash equilibria of the network game. Some Nash equilibria are also stochastically stable (Foster and Young Reference Foster and Young1990), in the sense that these equilibria emerge and persist when the dynamical system is perturbed with independent random changes in strategy or mutations.Footnote ² Game theorists have proved some powerful convergence theorems for network games that evolve according to dynamics perturbed with independent mutations (Ellison Reference Ellison1993, Reference Ellison2000; Young Reference Young1998, Morris Reference Morris2000). Some argue that these theorems are important in explaining the evolution of social institutions (Young Reference Young1998; Binmore Reference Binmore1998).

In this paper we introduce a dynamical adjustment process for network games with correlated mutations. This is significant because previous convergence results for network games invoke implausibly strong assumptions. In particular, these results assume that random mutations, which perturb the network game, are stochastically independent and identically distributed. But stochastic independence clearly fails in many settings. People often imitate others, even in experimental situations, which prevents mutations from being stochastically independent. In this paper, we present a model that allows players to imitate the behavior of another player who mutates, thereby introducing correlated mutations. This kind of correlated mutation has a natural interpretation: If a player in the network experiments and can signal her intent to some of the other players, those who receive the signal might imitate this signaler if she has sufficient influence over them. The players in this influence neighborhood who imitate the signaler ‘follow the leader’. We show that the dynamical properties of evolutionary games allowing for influence neighborhoods can differ dramatically from ones where all mutations are stochastically independent. We also argue that this dynamics more closely mirrors the process by which societies reform, rather than the dynamics of stochastically independent mutation.

In Section 1 we review some basic notions of network games, using the Assurance game to develop motivating examples. Section 2 discusses how inductive best-response dynamics are applied to network games, giving an example where best-response dynamics with independent random mutation never reaches the stochastically stable equilibrium in a reasonable time frame. We argue that this result casts doubt upon the explanatory power of models that assume stochastically independent mutations. In Section 3 we relax the independence assumption by introducing influence neighborhoods. We show how influence neighborhoods can greatly accelerate the transition from a suboptimal equilibrium to an optimal and stochastically stable equilibrium. We also show how influence neighborhoods can drive a network out of a stochastically stable equilibrium, and even converge to an optimal equilibrium that is not stochastically stable. We argue that this influence neighborhood model can be applied to test the likelihood of cooperation in social dilemmas and Hardin's (Reference Hardin1995) dual coordination account of the persistence and fall of political regimes. In Section 4 we give formal definitions of influence neighborhoods and best-response dynamics with correlated mutations, together with some elementary convergence results.

2. The Assurance Game Played with Neighbors

Figure 1 summarizes the symmetric 2-player Assurance game.Footnote ³ The Assurance game plays an important role in moral and political philosophy. Philosophers use the Assurance game to represent collective action problems ranging from cooperation in the Hobbesian State of Nature to pollution control to political revolutions.Footnote ⁴ The Assurance game also illustrates some of the challenges of accounting for equilibrium selection in games. In the Figure 1 game, (s ₁, s ₁) and (s ₂, s ₂) are both coordination equilibria (Lewis Reference Lewis1969) with the property that neither player's payoff is improved if one of them deviates from either (s ₁, s ₁) or (s ₂, s ₂). The equilibrium (s ₁, s ₁) is Pareto optimal and yields each player his highest possible payoff. However, each player is certain to gain a positive payoff only if he follows s ₂. Should rational players contribute to an optimal outcome or play it safe?

Figure 1.

The Assurance game.

The classical game theory of von Neumann and Morgenstern (Reference von Neumann and Morgenstern1944) and Nash (Reference Nash1950, Reference Nash1951a, [Reference Nash1951b] Reference Nash1996) gives no determinate answer to this question. Harsanyi and Selten (Reference Harsanyi and Selten1988) tried to answer this question by introducing a refinement of the Nash equilibrium concept called risk dominance. A strategy s is a player's best response to a strategy profile of the other players or a probability distribution over these profiles, when s maximizes the player's payoff given this profile or distribution. If the players in a symmetric $2\times 2$ game each assign a uniform probability distribution over the other's pure strategies and s* is the unique best response for both, then (s*, s*) is the risk dominant equilibrium. In the game of Figure 1, (s ₁, s ₁) is risk dominant if $x> y+z$ and (s ₂, s ₂) is risk dominant if $y+z> x$ . Harsanyi and Selten argue that a player should follow her part of a risk dominant equilibrium, because this strategy is the best response over the larger share of possible probabilities with which the other player follows his pure strategies (Harsanyi and Selten Reference Harsanyi and Selten1988, 82–83). Risk dominance is an important concept in game theory, but it raises obvious questions: Why shouldn't a player's probabilities over her opponent's strategies lie outside the range that makes her end of the risk dominant equilibrium her best response? Why shouldn't a player optimistically assign a high probability to her counterpart choosing s ₁, even if (s ₂, s ₂) is risk dominant, or pessimistically assign a high probability to her counterpart choosing s ₂, even if (s ₁, s ₁) is risk dominant? In the end, there really is no determinate solution to the Assurance game. Given appropriate probabilities reflecting a player's beliefs about what the other player will do, either pure strategy can be a best response. Rational players might fail to follow an equilibrium at all, even if they have common knowledge of their rationality.Footnote ⁵

Now suppose that, in a population of players, everyone plays the Assurance game with a subset of the population, known as her ‘neighbors’. At a given time, each player follows one strategy in her interactions with all her neighbors.Footnote ⁶ Explicitly identifying the neighbors with whom each player interacts embeds the Assurance game in a local interaction structure or network. Formally, a network is an undirected graph in which the nodes represent the players. Player j is Player i's neighbor if the nodes representing i and j are linked with an edge. If $n_{i}(s_{1}) $ of i's neighbors follow s ₁ and $n_{i}(s_{2}) $ of i's neighbors follow s ₂, then s ₁ is a best response for i if

s ₂ is a best response if the reverse inequality is satisfied. In the special case where $y=z$ , (1) is equivalent to

That is, s ₁ is a best response if the weighted average of payoffs, which i receives from her neighbors who follow s ₁, exceeds the guaranteed payoff of following s ₂. To illustrate, Figure 2 depicts a ‘propeller’ graph, where eight outer players are each linked with the same central player and one outer player. The outer players form the central player's Moore-8 neighborhood. The Figure 2 graph and Figure 1 game together define a network game. If, for instance, $x=9$ and $y=z=5$ , then by (2), s ₁ is a best response for the central Player i if $9\cdot [ n_{i}(s_{1}) / 8] \geq 5$ or $n_{i}(s_{1}) \geq 40/ 9> 4$ .

Figure 2.

Black players follow $s_{2}$ . Light players follow $s_{1}$ .

A priori analysis cannot predict what players in a network game will do any more than classical game theory can predict what a pair of players who meet in the Assurance game will do. Indeed, local interaction structures complicate the equilibrium selection problem. If the players in a network play the Assurance game with their neighbors, then this system is at one equilibrium if all follow s ₁, and another if all follow s ₂. In addition, there are polymorphic equilibria where some players follow s ₁, while others follow s ₂. If the players in the Figure 2 graph play the Assurance game with $x=9$ and $y=z=5$ for each Player i, then along with the all-s ₁ and all-s ₂ equilibria, any state, where the central player follows s ₁ and exactly two of the outer players linked with each other follow s ₂, is an equilibrium. Figure 2 depicts one of these polymorphic equilibria. Which, if any, of all these equilibria will the players in a local interaction structure adopt?

2.2. Example 1. Assurance Game Played on a Torus with Independent Mutations

Let $m> 1$ be an integer and let $N=\{ 1,\,\ldots,\,n\} $ where $n=m^{2}$ . Define a bijective function $\iota \thinspace{:}\thinspace N\rightarrow \{ 1,\,\ldots,\,n\} \times \{ 1,\,\ldots,\,n\} $ that assigns to each Player i a unique index $\iota (i) =(\iota _{1}(i),\,\iota _{2}(i)) $ . The graph

consists of links between each i and the 8 neighbors that immediately surround i. These links define i's Moore-8 neighborhood. This 2-dimensional graph is topologically a torus, and can be mapped onto a square whose edges ‘wrap around’. A number of authors use this graph to model various local interactions because it roughly approximates the interactions of agents who neighbor each other in a geographic region.Footnote ⁹ We set $m=100$ , so the entire network contains 10,000 players.

Next, we augment the local interaction structure with strategies and payoffs. Each player in the network plays the Figure 3 Assurance game with each of his Moore-8 neighbors, choosing a single strategy for interaction. The risk dominant equilibrium of the Figure 3 game is (s ₁, s ₁). So if players in this system update according to the best-response dynamic with independent random mutations, then the stochastically stable equilibrium of this system is the equilibrium where all follow s ₁. The all-s ₁ equilibrium is the unique stable attractor of this dynamic for any positive rate of mutation, no matter how small (Young Reference Young1998). In particular, if the system starts in the suboptimal equilibrium with all players following s ₂, best-response dynamics with random mutation eventually move the entire population to the optimal all-s ₁ equilibrium.

Figure 3.

Assurance game with $(s_{1},\,s_{1}) $ risk dominant.

One should wonder how long it takes this movement to occur. To test the speed of this convergence, we ran a computer simulation of this system.Footnote ¹⁰ All 10,000 players were initially assigned the strategy s ₂, starting the system at the suboptimal all-s ₂ equilibrium. At each time period, every player played the Figure 3 Assurance game with her Moore-8 neighbors, updating her strategy according to a perturbed best-response dynamic. Stochastically independent mutants appeared at a rate of .05. Each mutant chose one of the pure strategies, s ₁ or s ₂, at random with equal probability. We deliberately chose this rather high mutation rate so as to bias the dynamics against the initial all-s ₂ equilibrium.

While the all-s ₂ equilibrium is not stochastically stable, it proves surprisingly robust in the face of independent random mutations. The system was allowed to evolve for 100 million periods.Footnote ¹¹ Figure 4 depicts the state of this $100\times 100$ lattice at the final stage of this simulation. Even though the mutation rate was relatively high, so that at any stage an average of 5% of the players mutated, the s ₁-mutants were consistently overwhelmed and could not establish a permanent foothold. Hence, the s ₁-strategy never overthrew the incumbent s ₂-equilibrium. Indeed, in this simulation the suboptimal all-s ₂ equilibrium gave the appearance of being stochastically stable!

Figure 4.

State of the model after 100,000,000 iterations. Black players follow $s_{2}$ . Light players follow $s_{1}$ .

One might object that the test of the attracting power of the all-s ₁ equilibrium in Example 1 is too severe. Perhaps rational agents in such a network would seldom, if ever, all begin by following s ₂. In fact, we did relax the severity of the test, and found that the perturbed best-response dynamic with .05 mutation rate can converge to and never overthrow the suboptimal all-s ₂ equilibrium over 100 million rounds of play, even if the system is initially set with as many as 20% of the network players following the strategy s ₁. Still, we think the conditions of Example 1 are not so farfetched. Social dilemmas occur when individuals are reluctant to contribute towards a common good, even when they realize that all are better off if all contribute. A network Assurance game models a social dilemma where a player contributes to the common good by following s ₁ and withholds his contribution by following s ₂. Suppose initially that the benefit of the common good is small compared against the security of not contributing, so that all tend to follow s ₂ so as to avoid the costs of contribution. Then conditions change, making the relative benefit of the common good significantly greater. The Example 1 network corresponds to such a situation, since the (s ₁, s ₁) equilibrium of the Figure 3 game is both optimal and risk dominant. However, by (1) at least half of any player's neighbors must change from s ₂ to s ₁ before s ₁ becomes this player's best response. Example 1 shows that players who best respond to their neighbors’ previous strategies can have great difficulty making the transition from consistently following s ₂ to consistently following s ₁, even when the network is continually ‘bombarded’ by independent random mutations appearing at a high rate. The initial all-s ₂ equilibrium of Example 1 models a state that seems ripe for reform. But the dynamical behavior of this system reflects the fact that the road to social reform can be a long one.

3. Influence Neighborhoods

Theory tells us that random mutations will lead players to converge to stochastically stable equilibria almost surely in the long run. But we have just seen that players in a network who mutate independently at a high rate can fail to reach the stochastically stable equilibrium in over 100 million rounds of play. We believe Example 1 casts doubts upon the explanatory power of stochastic stability theorems applied to network games played by humans. Most, if not all, human interaction networks change and even dissolve long before the people in the network approach a 100 millionth consecutive round of interactions, yet a network of players who mutate independently can fail to approach its long run limit over 100 million rounds. If stochastic stability theorems require extraordinarily long waiting times—as Example 1 clearly shows—how can such theorems be relevant for explaining why actual people behave the way they do? No person changes his belief 100 million times in the course of his life, much less within a single repeated game. While we agree that 100 million rounds of interaction constitutes a short period of time from the point of view of the ergodic theory underlying stochastic stability theorems, one must appreciate a crucial difference between physical and social systems. Ergodic theory provides useful analyses of physical phenomena simply because, according to the time scale of many physical events, each elementary component (i.e., atom, molecule, etc.) can be involved in an extraordinarily large number of interactions in a relatively short period of time. The same is not true for social systems. Social and physical systems fail to be analogous precisely where required if ergodic theory is to be explanatorily relevant.

What if mutations in the dynamics can be correlated? The following examples show that the evolution of behavior in a network of best-response updaters can change dramatically if we relax the assumption that all the mutations are stochastically independent.

3.1. Example 2. Assurance Game Played on a Torus with Influence Neighborhoods

We revisit the network game of Example 1, with players (arranged on a $100\times 100$ torus) who play the Figure 3 Assurance game with Moore-8 neighbors. Again, each player updates his strategy according to a perturbed best-response dynamic. However, now we allow for correlation in the mutations. If a given Player i spontaneously mutates at stage t, then each of i's Moore-8 neighbors and each of their Moore-8 neighbors imitate i's stage t strategy with probability $\lambda _{i}(t) $ .Footnote ¹² The 24 players whose stage t strategies are correlated with i's mutant strategy are i's Moore-24 neighborhood in the torus. Each player in this Moore-24 neighborhood follows the mixed strategy of playing i's mutant strategy with probability $\lambda _{i}(t) $ . $\lambda _{i}(t) $ is a value sampled from the uniform distribution over [0,1], that is, $\lambda _{i}(t) $ is a probability for imitation drawn at random from [0,1], for each i.Footnote ¹³ We set the spontaneous mutation rate for a ‘leader’ at a low .0001, so that an average of only one ‘leader’ appears in the entire network per period. A ‘leader’ spontaneously mutates to s ₁ with probability .5 and to s ₂ with probability .5.Footnote ¹⁴

As in Example 1, in every simulation we ran of this dynamic we started the network game at the suboptimal all-s ₂ equilibrium. In each of these simulations, in fewer than 800 generations, the s ₁-followers had spread throughout the entire system of players so that all followed s ₁ except for occasional areas of s ₂-followers that emerged due to this correlated mutation.Footnote ¹⁵ These occasional s ₂-following clusters were quickly overwhelmed and converted back to s ₁-following. Figure 5 depicts the state of this $100\times 100$ graph at the 100th, 300th, 500th and 700th generations of one of our simulations.

Figure 5.

Black players follow $s_{2}$ . Light players follow $s_{1}$ .

Note that the system converged rapidly to the all s ₁-equilibrium even though at any given stage the overall mutation rate was bounded from above by $25\cdot (1/ 10,000) =.0025$ , the overall expected mutation rate if all of a ‘leader’ player's Moore-24 neighbors imitated the ‘leader's’ strategy.

The correlation in mutations described in Example 2 is a correlation over a ‘leader's’ influence neighborhood. In this example if Player i is a leader mutant at period t, then his influence neighborhood $I_{i}(t) $ is the set of his Moore-24 neighbors. At period t, each $j\in I_{i}(t) $ imitates i with probability $\lambda _{i}(t) $ . A natural to way to justify this sort of correlation in strategies is to allow for the possibility of costless communication, or what game theorists call ‘cheap talk’. If players can communicate, then they can correlate their strategies with the leader players whose messages they receive. When i is a leader at period t, i mutates to strategy $s_{i}(t) $ and communicates this fact to each $j\in I_{i}(t) $ . $\lambda _{i}(t) $ measures the strength of i's influence over those in the neighborhood $I_{i}(t) $ . Those in $I_{i}(t) $ who imitate $i$ 's strategy $s_{i}(t) $ at period t ‘follow their leader’. In Example 2, the correlated mutation of influence neighborhoods moves the network game from the suboptimal to the optimal equilibrium, even though the influence neighborhoods rarely appear. The road to reform in this example is shortened considerably by the introduction of influence neighborhoods.

Example 2 shows that risk dominant play can overtake an interaction network fairly rapidly when some players’ strategies are correlated. This example suggests a framework for modeling the ‘bandwagon’ effect that drives social reformation. Moreover, the next examples show that when correlated influence neighborhood mutations are possible, players who update according to a perturbed best-response dynamic need not converge to risk dominant play. This suggests a framework for modeling the stability of political regimes and the process of revolt.

3.2. Example 3. Assurance Game Played on a Bounded Degree Network with Influence Neighborhoods

Figure 6 depicts a bounded degree network, where each node is linked with at least 4, and at most 8, others. Again, the nodes represent players and the edges define each player's neighbors. Each player plays the Figure 7 Assurance game with each of her neighbors in the network. In Figure 7, the suboptimal (s ₂, s ₂) equilibrium is risk dominant. Consequently, in this network game the all-s ₂ equilibrium is the unique stochastically stable equilibrium of the best-response dynamic. In computer simulations, we found that when updating occurred according to the best-response dynamic with independent random mutations, the network converged to the all-s ₂ equilibrium even if it was initially set at the all-s ₁ equilibrium. Moreover, these random mutations never generated a permanent foothold of s ₁-followers in the network, even when the system was ‘bombarded’ by a high mutation rate of .10 for 100,000 periods. These results were not surprising, given that only all-s ₂ is stochastically stable.

Figure 6.

Black players follow $s_{2}$ . Light players follow $s_{1}$ .

Figure 7.

Assurance game with $(s_{2},\,s_{2}) $ risk dominant.

However, the all-s ₂ equilibrium does not retain its high attracting power when mutations can be correlated via influence neighborhoods. In a second set of computer simulations, the spontaneous mutation rate was set at .001, and again a spontaneous mutant followed s ₁ or s ₂ at random with equal probability. If a leader Player i spontaneously mutated to s _i, then i's neighbors together with their neighbors each followed s _i with probability $\lambda _{i}(t) $ selected at random from [0,1]. In these simulations, even when the network was initially set at the stochastically stable all-s ₂ equilibrium, it oscillated between all-s ₂ and all-s ₁. Figure 8 summarizes the evolution of strategies over this network during 5,000 periods of best-response updating perturbed with these influence neighborhoods. In this network, no equilibrium is stable with respect to these correlated mutations.

Figure 8.

Frequency of $s_{1}$ -followers in the 30-player bounded degree network game who update according to a best-response dynamic with influence neighborhoods.

In Examples 2 and 3, influence neighborhoods appear in the network at a fixed rate and a fixed size across pure strategies. In the next example, influence neighborhoods appear at different rates and in different sizes across the pure strategies.

3.3. Example 4. Assurance Game Played on a Bounded Degree Network with Differential Influence Neighborhoods

We consider another bounded degree network game, where each of 50 players is linked with at least 4, and at most 8, other players. Each player plays the Figure 7 game with her neighbors. As in the network game of Example 3, in this case the all-s ₂ equilibrium is the unique stochastically stable equilibrium of the best-response dynamic. In computer simulations, when the system was set at the all-s ₂ equilibrium the best-response dynamic with independent random mutations could never establish a stable foothold of s ₁-followers over 100,000 periods even with a mutation rate as high as .10. Additionally, the all-s ₂ equilibrium is not robust against the introduction of influence neighborhoods of the sort applied to the network game of Example 3.

We next examined the following perturbed best-response dynamics: At each time step, independent mutants of s ₂-followers appear with probability .1, and s ₁-mutants appear spontaneously with probability .001. When an s ₁-mutant appears spontaneously, her neighbors together with their neighbors each follow s ₁ with probability $\lambda _{i}(t) $ chosen at random from [0,1]. This dynamic always converged to the optimal all-s ₁ equilibrium, even though all-s ₂ is stochastically stable, and at any time period, an average of 10% of the players spontaneously mutated to s ₂. Figure 9 summarizes the results of one computer simulation over 5000 periods where the system was initially set at the all-s ₂ equilibrium.

Figure 9.

Frequency of $s_{1}$ -followers in the 50-player bounded degree network who update according to a best-response dynamic with influence neighborhoods.

In this network game, all-s ₁ is the unique stable attractor of the best-response dynamics perturbed with these influence neighborhoods. This result is especially striking because s ₂-following mutants appear 100 times as often as leader s ₁-following mutants appear, and even when an s ₁-following leader i appears at period t, the correlation in her influence neighborhood might be weak depending upon $\lambda _{i}(t) $ . The high influx of s ₂-mutants cannot prevent the overthrow of the all-s ₂ equilibrium because the s ₁-mutations are correlated. s ₁-mutant leaders appear seldom in the network game, but the coordinated play across their influence neighborhoods enables the s ₁-followers to conquer the network and to suppress the high influx of s ₂-mutants over time.

Example 4 shows that influence neighborhoods appearing at random in a network game can drive this game to an optimal equilibrium, robust against a high rate of independent mutations, even when the suboptimal equilibrium of the 2-player base game is risk dominant. The stability of the optimal equilibrium with respect to this dynamic depends upon the s ₁-mutants being correlated, while the s ₂-mutants remain independent. To explain this asymmetry, one can allow for differences in ability to communicate across individuals. That is, leader s ₁-following mutants may have access to some communication channel used to send messages to those in their influence neighborhoods, while s ₂-mutants have no reliable means of communicating. So even though leader s ₁-mutants appear seldom in the network, their ability to signal their plans to others enables those they have influence over to coordinate more effectively. On the other hand, even though s ₂-mutants appear at a much higher rate, they are unable to communicate and consequently cannot coordinate their activity. So s ₁-followers can overthrow an incumbent all-s ₂ equilibrium and even fight off a continual high influx of new s ₂-followers.

This suggests a method for testing Hardin's (Reference Hardin1995) dual coordination explanation of the duration of regimes and successful revolt. Hardin maintains that a generally despised regime will remain in power so long as agents of the regime can simultaneously coordinate their activity and prevent those under their jurisdiction from coordinating. This explains why repressive regimes suppress communication. Hardin argues that if dissidents become able to communicate and thereby coordinate, while the regime's agents lose these abilities, the regime becomes vulnerable. One can interpret the network game and influence neighborhoods of Example 4 as follows: To follow s ₂ is to obey a regime all dislike. Suppose, though, that dissident s ₁-followers establish an underground broadcasting network enabling them to send messages to others while jamming the attempts of reinforcement sent by the s ₂-following regime. Given these conditions, the s ₁-followers stage a successful revolt.

4. The Formal Model

Let $N=\{ 1,\,\ldots,\,n\} $ denote the set of players and let ij denote the subset $\{ i,\,j\} \subseteq N$ . Each $ij\subseteq N$ with $i\neq j$ is an undirected link (or edge) for N. We use $K_{n}$ to denote the complete undirected graph over N. A subset $\mathstrut{\cal N} \subseteq K_{n}$ defines an interaction network. If $ij\in \mathstrut{\cal N} $ , then i and j are neighbors and are said to be linked. The set of all players that a given Player i is linked to is called the neighborhood of i and is denoted $\mathstrut{\cal N} _{i}$ . Since each player in the network interacts with at least one other player, $\mathstrut{\cal N} _{i}\neq \emptyset $ for all i.

All players in the network play a symmetric, noncooperative 2-player game Γ with pure strategy set S and payoff matrix $u\thinspace{:}\thinspace S\times S\rightarrow \mathstrut{\frak R} ^{2}$ . If i follows $s_{i}$ and j follows $s_{j}$ , the payoff to i is $u(s_{i},\,s_{j}) $ and the payoff to j is $u(s_{j},\,s_{i}) $ . $\mathstrut{\cal N} $ and Γ characterize the network game $N_{\Gamma }$ .

A state of a network game is a vector $\vec{s}=(s_{k_{1}},\,\ldots,\,s_{k_{n}}) $ , specifying a strategy for each player in the network. In each round of play, each player plays the game with all of her neighbors, receiving a score equal to the sum of the payoffs. A strategy $s_{k_{i}}$ is a best response for Player i to $\vec{s}_{-i}$ Footnote ¹⁶ if $s_{k_{i}}$ maximizes $i$ 's payoff, that is,

$S^{*}_{i}(\vec{s}_{-i}) $ denotes the set of Player i's best responses to $\vec{s}_{-i}$ . A state $\vec{s}^{*}=(s^{*}_{k_{1}},\,\ldots,\,s^{*}_{k_{n}}) $ is a Nash equilibrium of $N_{\Gamma }$ ,

and $\vec{s}^{*}$ is strict if exactly one strategy satisfies (4) for each $i\in N$ .

Since players may change strategies over time, we need to add explicit time-indexes to some of the above definitions. Consequently, let $s_{i}(t) $ denote the strategy i follows at time t. Likewise, let $\vec{s}(t) =(s_{1}(t),\,\ldots,\, s_{n}(t)) $ denote the state of the network at time t.

The (inductive) best-response dynamic (BR-dynamic) specifies how individuals change strategies as follows: For each $i\in N$ , let $f_{i}$ be a (possibly random) choice function from subsets of strategies to single strategies, that is, $f_{i}\thinspace{:}\thinspace \mathstrut{\cal P} (S) -\emptyset \rightarrow S$ . At each period $t> 0$ ,

In words, at time t each Player i adopts a strategy that is a best response to the strategies i's neighbors followed at period $t-1$ . If $S^{*}_{i}$ contains more than one pure strategy, then i selects one of these best responses according to his choice function.

Notice that $BR_{i}(t) =BR_{i}(t-1) $ for each $i\in N$ , only if $\vec{s}(t) =\vec{s}(t-1) $ is a Nash equilibrium of $N_{\Gamma }$ , that is, the fixed points of the BR-dynamic are Nash equilibria of the network game. Also note that the converse need not hold, for if $\vec{s}(t-1) $ is a Nash equilibrium but not strict, then at time t some players might choose best responses other than their respective parts of $\vec{s}(t-1) $ . However, any strict Nash equilibrium is a fixed point of the BR-dynamic, since by definition each player's part of such an equilibrium is her unique best response to the others’ strategies.

Let $\sigma _{i}$ denote a completely mixed strategyFootnote ¹⁷ for Player i and $A^{t}_{\varepsilon _{1}},\,\ldots,\,A^{t}_{\varepsilon _{n}}$ denote stochastically independent propositions such that $\mathrm{Pr}\,(A^{t}_{\varepsilon _{i}}) =\varepsilon _{i}$ . Then the $\overline{BR}$ -dynamic with independent random mutation is defined by

where $1_{A}$ denotes the indicator of a proposition A.Footnote ¹⁸ That is, at each stage t, i best responds with probability $1-\varepsilon _{i}$ , and with probability $\varepsilon _{i}$ chooses a pure strategy at random. $\varepsilon _{i}$ is i's mutation rate. One may interpret a mutation $\sigma _{i}$ as i experimenting or making an error, or as one individual being replaced by a fresh individual unfamiliar with the history of play.

Our conception of mutations as being dependent upon the influence neighborhood of a player may be formally defined as follows:

Definition. Given a network game $N_{\Gamma }$ , at each period t there is a matrix

where $(\lambda _{i1}(t),\,\ldots,\,\lambda _{in}(t)) =\vec{\lambda }_{i}(t) $ is a probability distribution. Player i's influence neighborhood (I-neighborhood) at time t is the set $I_{i}(t) =\{ j\in N\thinspace{:}\thinspace \lambda _{ji}(t) > 0\} $ . The size of an I-neighborhood is the cardinality of this set.

The influence neighborhood probabilities can vary over time periods, while the graph that defines the network remains fixed. The underlying intuition here is that changing one's neighbors is prohibitively costly, but cost-free communication with nearby players might at times be possible. So the players’ interaction neighborhoods remain fixed, but their influence neighborhoods can change rapidly. Note that for a given $ij\in \mathstrut{\cal N} $ , we can have $\lambda _{ij}(t) \neq \lambda _{ji}(t) $ . This reflects the idea that influence need not be a symmetric relation between players. The weights can vary across players in a I-neighborhood so that influence might vary across players as well as across time.

The precise manner by which players correlate their strategies is defined by a variant of the best-response dynamic that incorporates influence neighborhoods:

Definition. Let $A^{t}_{i1},\,\ldots,\,A^{t}_{in}$ be mutually exclusive propositions such that $\mathrm{Pr}\,(A^{t}_{ij}) =\lambda _{ij}(t) $ . Then the BR*-dynamic with influence neighborhoods ( $\vec{\lambda }_{N}(t) $ ) is defined as follows: For $i\in N$ ,

where $s_{i}(t) =\overline{BR}_{i}(t,\,\varepsilon _{i},\,\sigma _{i}) $ . In words, Player i imitates the strategy of Player j with probability $\lambda _{ij}(t) $ if i falls in j's influence neighborhood.

If at time t we have $\lambda _{ii}(t) =1$ for all $i\in N$ , then no player has influence over other players. For this special case, the BR*-dynamic with influence neighborhoods reduces to the $\overline{BR}$ -dynamic with independent random mutation. At another extreme, if a Player i has a number of other players falling in her I-neighborhood at period t and $\lambda _{ji}(t) =1$ for each $j\in I_{i}(t) $ , then all of the players in i's influence neighborhood are certain to correlate their strategies with i at period t. One might think of this case as a ‘perfectly disciplined’ influence neighborhood whose members all follow their leader's command.

In Examples 2, 3, and 4, a leader Player i with an influence neighborhood $I_{i}(t) \neq \{ i\} $ appears at random in the network game, and i's influence probability is constant over the influence neighborhood. This is why in these examples it makes sense to write $\lambda _{ji}(t) =\lambda _{i}(t) $ for each $j\in I_{i}(t) $ . In these examples, a leader's influence over those in his influence neighborhood is set at random and lasts only for a single time period, save for the unlikely event that this leader spontaneously mutates over consecutive time periods. Of course, many other configurations of influence neighborhoods are possible. A leader player might have a fixed influence neighborhood over part of the network game and over an indefinite number of consecutive periods. Such fixed influence neighborhood leaders have their analogous counterparts in real life, such as political leaders and military commanders. If a single Player i is such that $\lambda _{ji}(t) =1$ for all time and all $j\in N$ , then the entire network is i's perfectly disciplined influence neighborhood. In this case, i plays a role analogous to Hobbes’ absolute sovereign. As noted above, perfect discipline is an extreme case. In many actual situations, a leader's ‘clout’ varies across the population. Varying influence probabilities reflect a leader's uneven sway over those who receive his messages. One virtue of the framework described here is its flexibility for treating such cases.

When correlated mutations are possible, a variety of long-term outcomes can emerge, depending upon the payoff structure and the topology of the interaction network and the influence neighborhoods. If influence neighborhoods remain fixed and perfectly disciplined over a stretch of time, the network can remain at a polymorphism of strategies where those in the influence neighborhoods follow their leaders and the rest converge to the strategy that defines the stochastically stable equilibrium. Examples 3 and 4 show that stochastically stable equilibria need not be robust against influence neighborhoods even when these neighborhoods appear momentarily at random at very low rates. These examples show that there is no universal convergence property of the best-response dynamic perturbed with influence neighborhoods analogous to that of stochastic stability when all mutations are stochastically independent.

However, it is possible to define convergence concepts for the BR*-dynamic and to identify some sufficient conditions for convergence. Example 2 shows that influence neighborhoods can greatly accelerate the convergence of the network to the strategy of the risk dominant equilibrium. Examples 2 and 4 suggest the following:

Definition. A state $\vec{s}=(s^{*}_{1},\,\ldots,\,s^{*}_{n}) $ of a network game is an attractor of the BR*-dynamic with influence neighborhoods $\vec{\lambda }_{N}(t) $ if for some state $\vec{s}^{\prime }\neq \vec{s}^{*}$ , when $\vec{s}(0) =\vec{s}^{\prime }$ , then

If (8) is satisfied for every state $\vec{s}\neq \vec{s}^{*}$ , then $\vec{s}^{*}$ is the global attractor of the BR*-dynamic.

This definition says that $\vec{s}^{*}$ is an attractor of a BR*-dynamic if, with probability one, from an initial state $\vec{s}(0) $ , players who update according to this dynamic all eventually follow $\vec{s}^{*}$ , except when they mutate. In Example 2, $(s^{*}_{1},\,\ldots,\,s^{*}_{n}) $ is the global attractor of the BR*-dynamic, where each I-neighborhood is a Moore-24 neighborhood of varying discipline. For any initial state of this network, under this BR*-dynamic all the players eventually follow $s_{1}$ except for the occasional I-neighborhood of $s_{2}$ -followers that appears and is then eliminated.

Example 2 shows that a system of BR*-updaters can converge to an optimal Nash equilibrium even when the I-neighborhoods appear randomly in the network at a very low rate, and the initial state is a suboptimal but strict equilibrium. In the remainder of this section, we show why this is the case and at the same time establish some convergence conditions for BR*-dynamics. First, we define the notion of BR-stability for the unperturbed best-response dynamic.

Intuitively, a set of the players is B-stable with respect to the pure strategy s if when all in B start to follow s, the BR-dynamic cannot ‘erode’ the s-following throughout B even when all the rest of the players in $N_{\Gamma }$ do not follow s.

The following proposition establishes a convergence result for the BR*-dynamic provided certain BR-stable sets exist.

Proof. Let $(I_{u}) $ denote the sequence of I-neighborhoods that appears in the network lexically ordered according to time. With probability one, a perfectly disciplined I-neighborhood of maximum size b whose players follow $s^{*}$ appears infinitely often in the sequence of plays. Let $(I_{u_{k}}) $ denote the subsequence of $(I_{u}) $ such that $I_{u_{k}}$ is of size b and each $i\in I_{u_{k}}$ follows $s^{*}$ , and let $(B_{u_{k}}) $ denote the sequence of BR-stable sets of $s^{*}$ -followers that appear in $N_{\Gamma }$ as a result. We claim that $s^{*}$ satisfies (8), that is, $s^{*}$ overtakes the network game with probability one. Each $B_{u_{k}}$ introduces a number of $s^{*}$ -followers that remain in the network over time until $B_{u_{k}}$ is disrupted by some influence neighborhood whose players follow some strategy other than $s^{*}$ . Thus the $B_{u_{k}}$ 's gradually increase the number of $s^{*}$ -followers in the network until all but mutants follow $s^{*}$ unless all but some fixed finite number of the $B_{u_{k}}$ 's are disrupted by ‘counter’ I-neighborhoods whose ‘leaders’ follow strategies other than $s^{*}$ that appear and overlap the $B_{u_{k}}$ 's. But for this containment of the $B_{u_{k}}$ 's to occur, a sequence $(A_{u_{k}}) $ of I-neighborhoods synchronized with the $I_{u_{k}}$ 's must appear in $N_{\Gamma }$ such that all but a fixed number of the $A_{u_{k}}$ 's satisfy the following properties: (i) the leader Player $i_{u_{k}}$ of each $A_{u_{k}}$ follows some strategy other than $s^{*}$ , (ii) $i_{u_{k}}$ appears in a part of the network where $A_{u_{k}}$ overlaps $I_{u_{k}}$ , and (iii) enough players in $A_{u_{k}}$ imitate $i_{u_{k}}$ 's strategy to disrupt the $s^{*}$ -stability of $B_{u_{k}}$ so that the players in $B_{u_{k}}$ do not continue to follow $s^{*}$ . (If these conditions are not met, then a subsequence of the $B_{u_{k}}$ 's is not contained by the $A_{u_{k}}$ 's and this subsequence then overtakes the whole network. But if $A^{\prime }_{u_{k}}$ denotes the proposition that for a given $B_{u_{k}}$ a matching $A_{u_{k}}$ appears satisfying (i), (ii), and (iii), then $\mathrm{Pr}\,(A^{\prime }_{u_{k}}) $ is some value $\eta _{u_{k}}< 1$ . For note that the probability that (i) occurs is fixed by hypothesis. The probability that (ii) occurs is some fixed number, for there are only so many ways a I-neighborhood of size b can overlap one of the $B_{u_{k}}$ 's. The probability that (iii) occurs is bounded from above, since the ‘best case’ scenario for the ‘disrupters’ is if $A_{u_{k}}$ overlaps perfectly with $B_{u_{k}}$ and then sufficiently many players in $A_{u_{k}}$ imitate $i_{u_{k}}$ to destabilize the $s^{*}$ strategy in $B_{u_{k}}$ . So the $\eta _{u_{k}}$ 's are bounded from above by some $\eta < 1$ . Hence if $A^{\prime }$ denotes the event that the necessary sequence of $A_{u_{k}}$ 's appears to contain the $B_{u_{k}}$ 's, then

QED

The key idea behind Proposition 2 is that BR-stable sets of $s^{*}$ -followers appear in the network game and tend to persist, even when they do not appear in consecutive time periods and are not contiguous in the network. So with probability one, the appearance of these BR-stable sets together with the forces of the BR*-dynamic results in $s^{*}$ overtaking the entire network game. This argument differs considerably from the proofs of the stochastic stability results for independent random mutations in works such as Young (Reference Young1993, Reference Young1998), Ellison (Reference Ellison1993, Reference Ellison2000), and Morris (Reference Morris2000), which consider the behavior of a network game in the rare event that sufficiently many independent mutations occur consecutively so as to drive the system out of and away from an equilibrium. Note also that the premises of Proposition 2 do not bias the BR*-dynamic to make the influence neighborhoods of any one strategy more likely to appear or to persist over time than another. Finally, note that the proof of Proposition 2 does not depend upon specific values of ε, q, or p as stated in the hypotheses. So the BR*-dynamics that satisfy these hypotheses ultimately overtake the entire network game no matter how infrequently BR-stable sets of $s^{*}$ -followers appear, as long as they appear with some positive probability at each period.

We can now identify certain network structures where a BR*-dynamic that is not biased in favor of any pure strategy will converge to risk dominant equilibrium play. A network $\mathstrut{\cal N} $ is c-regular if each Player is linked with exactly c other players.

Corollary 3 establishes that when the base game has a risk dominant equilibrium, a large class of BR*-dynamics will converge to risk dominant equilibrium play in the special case where the interaction network is uniformly linked, as are the one-dimensional circular network games analyzed by Ellison (Reference Ellison1993) and the two-dimensional lattice of Examples 2 and 3. Moreover, we can now explain why random mutations failed to overthrow the suboptimal $(s_{2},\,\ldots,\,s_{2}) $ equilibrium of the lattice network of Assurance games in Example 1 while in Example 2 influence neighborhoods that entered the same network game rapidly moved the system to the $(s_{1},\,\ldots,\,s_{1}) $ equilibrium. In order for any BR-stable set of s ₁-followers to appear in the network, at least 12 players in a ‘cross’ configuration must simultaneously mutate to s ₁. Given stochastic independence with $\varepsilon _{i}=.05$ , the probability that even one such group of 12 appears in the network over 100 million generations is bounded from above by $2^{-24}$ .Footnote ¹⁹ So it is not surprising that in Example 1 the independent s ₁-mutants failed to establish a stable bridgehead in the network game over a million generations even though they appeared at such a high rate.

In Example 2, even though I-neighborhoods appeared at a rate of only .001, some of the I-neighborhoods of s ₁-followers that appeared introduced BR-stable sets. Each I-neighborhood was a Moore-24 neighborhood, and since the network game was 8-uniformly linked, all but the four ‘corner’ players of a given I-neighborhood were linked with at least four players in the same I-neighborhood. So when a perfectly disciplined I-neighborhood of s ₁-followers appeared in the network game surrounded by s ₂-followers, the corner players converted to s ₂ on the subsequent round of play but the remaining 20 players formed a BR-stable set of s ₁-followers that persisted in the game. While these BR-stable sets appeared seldom in the network due to the very low leader mutation rate, they started a steady contagion of s ₁-followers that rapidly overtook the network.

Proposition 2 and Corollary 3 are fundamental convergence results for BR*-dynamics. They show that for certain classes of network games, influence neighborhoods large enough to introduce BR-stable sets will ultimately drive a network game to a unique Nash equilibrium, no matter how infrequently leader mutants appear. However, these results cannot be generalized to all network games. Example 3 shows that if the interaction network is not uniformly linked there might be no global attractor, or even a stable equilibrium, of a BR*-dynamic that introduces influence neighborhoods following each pure strategy at equal rates. Example 4 shows that under a BR*-dynamic that introduces influence neighborhoods at rates and of sizes that vary across pure strategies, a nonuniformly linked network game can converge to an equilibrium of nonrisk dominant play that is robust against a high rate of spontaneous mutation. Plainly, the impact of correlated influence neighborhood mutation varies according to the network structure and the specifics of the influence neighborhoods.

5. Conclusion

We have shown that correlated mutations profoundly influence the evolution of strategies across local interaction structures. Previous work established that when the base game of any network game has a risk dominant equilibrium, risk dominant play characterizes the unique stochastically stable state of the best-response dynamic (Ellison Reference Ellison1993; Young Reference Young1998). The generality of this result suggests that the payoffs of the base game alone determine the long-term limits of dynamical updating. However, the examples in this paper show that the tight connection between risk dominant play and dynamic stability dissolves when one relaxes the assumption that all mutations are stochastically independent. Network structure does play a role in determining where the players end up when the correlated mutations of influence neighborhoods can appear. Correlation via influence neighborhoods can help drive a network of players to a stable equilibrium of risk dominant play, or to some other stable equilibrium. And it is possible that no state is stable when influence neighborhoods enter into the network game, even when this game has a unique stochastically stable equilibrium of risk dominant play.

Correlation via influence neighborhoods also dramatically accelerates the evolution of equilibria in some network games. We have seen that when only independent mutations are possible, the players in a network game can find themselves trapped at a suboptimal equilibrium that is not stochastically stable for a very long time. While according to theory, independent mutations will ultimately drive the network game to the stochastically stable equilibrium, this process may take so long that stochastic stability cannot be the basis for any realistic explanation of the emergence of a new optimal social equilibrium in human communities. Communities of people do occasionally reform their practices, and the process does not typically occur as the result of independent aberrations in behavior over millions of consecutive interactions. Successful reform requires coordinated departures from incumbent practice. Typically, such coordination requires planning, communication and leadership. Such coordination also succeeds by generating a ‘bandwagon’ effect that spreads quickly through society. Influence neighborhoods prove useful for modeling this coordination. Moreover, an optimal equilibrium that independent mutation never produces over millions of periods of interaction can emerge quite rapidly under the correlated mutations of influence neighborhoods. We believe that influence neighborhoods can be a valuable tool for analyzing social change.

Most of the literature on network games, including the stochastic stability literature, develops quite general convergence results from powerful assumptions that are mathematically convenient but not really well founded. In this paper, we have explored some of the consequences of relaxing one of these assumptions, namely, that all mutations are stochastically independent. Not surprisingly, we do not get convergence theorems for influence neighborhood dynamics as general as those of the stochastic stability literature, but we do get what we think is a more realistic model of how strategies develop over local interaction structures. Future work should investigate the consequences of relaxing some of the other robust assumptions common in the network game literature, in conjunction with relaxing the stochastic independence assumption. Players might not be so myopic as the literature assumes. Updating rules more sophisticated than the best-response dynamic should be explored. Players might not always interact with the same neighbors. Some authors have already proposed models where the interaction network itself evolves over time (Skyrms and Pemantle Reference Skyrms and Pemantle2000; Goyal and Vega-Redondo Reference Goyal and Vega-Redondo2000; Watts Reference Watts2001, Jackson and Watts Reference Jackson and Watts2001a, Reference Jackson and Watts2001b). Combining different learning rules and evolving network structures with influence neighborhood mutation may produce a theory of network games that has much greater explanatory power than the existing theory.