Networks Preserving Evolutionary Equilibria and the Power of Randomization Michael Kearns mkearns@cis.upenn.edu Siddharth Suri ssuri@cis.upenn.edu Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 ABSTRACT We study a natural extension of classical evolutionary game theory to a setting in which pairwise interactions are restricted to the edges of an undirected graph or network. We generalize the definition of an evolutionary stable strategy (ESS), and show a pair of complementary results that exhibit the power of randomization in our setting: subject to degree or edge density conditions, the classical ESS of any game are preserved when the graph is chosen randomly and the mutation set is chosen adversarially, or when the graph is chosen adversarially and the mutation set is chosen randomly. We examine natural strengthenings of our generalized ESS definition, and show that similarly strong results are not possible for them. Categories and Subject Descriptors J.4 [Social and Behavioral Sciences]: Economics General Terms Economics, Theory 1. INTRODUCTION In this paper, we introduce and examine a natural extension of classical evolutionary game theory (EGT) to a setting in which pairwise interactions are restricted to the edges of an undirected graph or network. This extension generalizes the classical setting, in which all pairs of organisms in an infinite population are equally likely to interact. The classical setting can be viewed as the special case in which the underlying network is a clique. There are many obvious reasons why one would like to examine more general graphs, the primary one being in that many scenarios considered in evolutionary game theory, all interactions are in fact not possible. For example, geographical restrictions may limit interactions to physically proximate pairs of organisms. More generally, as evolutionary game theory has become a plausible model not only for biological interaction, but also economic and other kinds of interaction in which certain dynamics are more imitative than optimizing (see [2, 16] and chapter 4 of [19]), the network constraints may come from similarly more general sources. Evolutionary game theory on networks has been considered before, but not in the generality we will do so here (see Section 4). We generalize the definition of an evolutionary stable strategy (ESS) to networks, and show a pair of complementary results that exhibit the power of randomization in our setting: subject to degree or edge density conditions, the classical ESS of any game are preserved when the graph is chosen randomly and the mutation set is chosen adversarially, or when the graph is chosen adversarially and the mutation set is chosen randomly. We examine natural strengthenings of our generalized ESS definition, and show that similarly strong results are not possible for them. The work described here is part of recent efforts examining the relationship between graph topology or structure and properties of equilibrium outcomes. Previous works in this line include studies of the relationship of topology to properties of correlated equilibria in graphical games [11], and studies of price variation in graph-theoretic market exchange models [12]. More generally, this work contributes to the line of graph-theoretic models for game theory investigated in both computer science [13] and economics [10]. 2. CLASSICAL EGT The fundamental concept of evolutionary game theory is the evolutionarily stable strategy (ESS). Intuitively, an ESS is a strategy such that if all the members of a population adopt it, then no mutant strategy could invade the population [17]. To make this more precise, we describe the basic model of evolutionary game theory, in which the notion of an ESS resides. The standard model of evolutionary game theory considers an infinite population of organisms, each of which plays a strategy in a fixed, 2-player, symmetric game. The game is defined by a fitness function F. All pairs of members of the infinite population are equally likely to interact with one another. If two organisms interact, one playing strategy s 200 and the other playing strategy t, the s-player earns a fitness of F(s|t) while the t-player earns a fitness of F(t|s). In this infinite population of organisms, suppose there is a 1 − fraction who play strategy s, and call these organisms incumbents; and suppose there is an fraction who play t, and call these organisms mutants. Assume two organisms are chosen uniformly at random to play each other. The strategy s is an ESS if the expected fitness of an organism playing s is higher than that of an organism playing t, for all t = s and all sufficiently small . Since an incumbent will meet another incumbent with probability 1 − and it will meet a mutant with probability , we can calculate the expected fitness of an incumbent, which is simply (1 − )F(s|s) + F(s|t). Similarly, the expected fitness of a mutant is (1 − )F(t|s) + F(t|t). Thus we come to the formal definition of an ESS [19]. Definition 2.1. A strategy s is an evolutionarily stable strategy (ESS) for the 2-player, symmetric game given by fitness function F, if for every strategy t = s, there exists an t such that for all 0 < < t, (1 − )F(s|s) + F(s|t) > (1 − )F(t|s) + F(t|t). A consequence of this definition is that for s to be an ESS, it must be the case that F(s|s) ≥ F(t|s), for all strategies t. This inequality means that s must be a best response to itself, and thus any ESS strategy s must also be a Nash equilibrium. In general the notion of ESS is more restrictive than Nash equilibrium, and not all 2-player, symmetric games have an ESS. In this paper our interest is to examine what kinds of network structure preserve the ESS strategies for those games that do have a standard ESS. First we must of course generalize the definition of ESS to a network setting. 3. EGT ON GRAPHS In our setting, we will no longer assume that two organisms are chosen uniformly at random to interact. Instead, we assume that organisms interact only with those in their local neighborhood, as defined by an undirected graph or network. As in the classical setting (which can be viewed as the special case of the complete network or clique), we shall assume an infinite population, by which we mean we examine limiting behavior in a family of graphs of increasing size. Before giving formal definitions, some comments are in order on what to expect in moving from the classical to the graph-theoretic setting. In the classical (complete graph) setting, there exist many symmetries that may be broken in moving to the the network setting, at both the group and individual level. Indeed, such asymmetries are the primary interest in examining a graph-theoretic generalization. For example, at the group level, in the standard ESS definition, one need not discuss any particular set of mutants of population fraction . Since all organisms are equally likely to interact, the survival or fate of any specific mutant set is identical to that of any other. In the network setting, this may not be true: some mutant sets may be better able to survive than others due to the specific topologies of their interactions in the network. For instance, foreshadowing some of our analysis, if s is an ESS but F(t|t) is much larger than F(s|s) and F(s|t), a mutant set with a great deal of internal interaction (that is, edges between mutants) may be able to survive, whereas one without this may suffer. At the level of individuals, in the classical setting, the assertion that one mutant dies implies that all mutants die, again by symmetry. In the network setting, individual fates may differ within a group all playing a common strategy. These observations imply that in examining ESS on networks we face definitional choices that were obscured in the classical model. If G is a graph representing the allowed pairwise interactions between organisms (vertices), and u is a vertex of G playing strategy su, then the fitness of u is given by F(u) = P v∈Γ(u) F(su|sv) |Γ(u)| . Here sv is the strategy being played by the neighbor v, and Γ(u) = {v ∈ V : (u, v) ∈ E}. One can view the fitness of u as the average fitness u would obtain if it played each if its neighbors, or the expected fitness u would obtain if it were assigned to play one of its neighbors chosen uniformly at random. Classical evolutionary game theory examines an infinite, symmetric population. Graphs or networks are inherently finite objects, and we are specifically interested in their asymmetries, as discussed above. Thus all of our definitions shall revolve around an infinite family G = {Gn}∞ n=0 of finite graphs Gn over n vertices, but we shall examine asymptotic (large n) properties of such families. We first give a definition for a family of mutant vertex sets in such an infinite graph family to contract. Definition 3.1. Let G = {Gn}∞ n=0 be an infinite family of graphs, where Gn has n vertices. Let M = {Mn}∞ n=0 be any family of subsets of vertices of the Gn such that |Mn| ≥ n for some constant > 0. Suppose all the vertices of Mn play a common (mutant) strategy t, and suppose the remaining vertices in Gn play a common (incumbent) strategy s. We say that Mn contracts if for sufficiently large n, for all but o(n) of the j ∈ Mn, j has an incumbent neighbor i such that F(j) < F(i). A reasonable alternative would be to ask that the condition above hold for all mutants rather than all but o(n). Note also that we only require that a mutant have one incumbent neighbor of higher fitness in order to die; one might considering requiring more. In Sections 6.1 and 6.2 we consider these stronger conditions and demonstrate that our results can no longer hold. In order to properly define an ESS for an infinite family of finite graphs in a way that recovers the classical definition asymptotically in the case of the family of complete graphs, we first must give a definition that restricts attention to families of mutant vertices that are smaller than some invasion threshold n, yet remain some constant fraction of the population. This prevents invasions that survive merely by constituting a vanishing fraction of the population. Definition 3.2. Let > 0, and let G = {Gn}∞ n=0 be an infinite family of graphs, where Gn has n vertices. Let M = {Mn}∞ n=0 be any family of (mutant) vertices in Gn. We say that M is -linear if there exists an , > > 0, such that for all sufficiently large n, n > |Mn| > n. We can now give our definition for a strategy to be evolutionarily stable when employed by organisms interacting with their neighborhood in a graph. 201 Definition 3.3. Let G = {Gn}∞ n=0 be an infinite family of graphs, where Gn has n vertices. Let F be any 2-player, symmetric game for which s is a strategy. We say that s is an ESS with respect to F and G if for all mutant strategies t = s, there exists an t > 0 such that for any t-linear family of mutant vertices M = {Mn}∞ n=0 all playing t, for n sufficiently large, Mn contracts. Thus, to violate the ESS property for G, one must witness a family of mutations M in which each Mn is an arbitrarily small but nonzero constant fraction of the population of Gn, but does not contract (i.e. every mutant set has a subset of linear size that survives all of its incumbent interactions). In Section A.1 we show that the definition given coincides with the classical one in the case where G is the family of complete graphs, in the limit of large n. We note that even in the classical model, small sets of mutants were allowed to have greater fitness than the incumbents, as long as the size of the set was o(n) [18]. In the definition above there are three parameters: the game F, the graph family G and the mutation family M. Our main results will hold for any 2-player, symmetric game F. We will also study two rather general settings for G and M: that in which G is a family of random graphs and M is arbitrary, and that in which G is nearly arbitrary and M is randomly chosen. In both cases, we will see that, subject to conditions on degree or edge density (essentially forcing connectivity of G but not much more), for any 2-player, symmetric game, the ESS of the classical settings, and only those strategies, are always preserved. Thus a common theme of these results is the power of randomization: as long as either the network itself is chosen randomly, or the mutation set is chosen randomly, classical ESS are preserved. 4. RELATED WORK There has been previous work that analyzes which strategies are resilient to mutant invasions with respect to various types of graphs. What sets our work apart is that the model we consider encompasses a significantly more general class of games and graph topologies. We will briefly survey this literature and point out the differences in the previous models and ours. In [8], [3], and [4], the authors consider specific families of graphs, such as cycles and lattices, where players play specific games, such as 2 × 2-games or k × k-coordination games. In these papers the authors specify a simple, local dynamic for players to improve their payoffs by changing strategies, and analyze what type of strategies will grow to dominate the population. The model we propose is more general than both of these, as it encompasses a larger class of graphs as well as a richer set of games. Also related to our work is that of [14], where the authors propose two models. The first assumes organisms interact according to a weighted, undirected graph. However, the fitness of each organism is simply assigned and does not depend on the actions of each organism"s neighborhood. The second model has organisms arranged around a directed cycle, where neighbors play a 2 × 2-game. With probability proportional to its fitness, an organism is chosen to reproduce by placing a replica of itself in its neighbors position, thereby killing the neighbor. We consider more general games than the first model and more general graphs than the second. Finally, the works most closely related to ours are [7], [15], and [6]. The authors consider 2-action, coordination games played by players in a general undirected graph. In these three works, the authors specify a dynamic for a strategy to reproduce, and analyze properties of the graph that allow a strategy to overrun the population. Here again, one can see that our model is more general than these, as it allows for organisms to play any 2-player, symmetric game. 5. NETWORKS PRESERVING ESS We now proceed to state and prove two complementary results in the network ESS model defined in Section 3. First, we consider a setting where the graphs are generated via the Gn,p model of Erd˝os and R´enyi [5]. In this model, every pair of vertices are joined by an edge independently and with probability p (where p may depend on n). The mutant set, however, will be constructed adversarially (subject to the linear size constraint given by Definition 3.3). For these settings, we show that for any 2-player, symmetric game, s is a classical ESS of that game, if and only if s is an ESS for {Gn,p}∞ n=0, where p = Ω(1/nc ) and 0 ≤ c < 1, and any mutant family {Mn}∞ n=0, where each Mn has linear size. We note that under these settings, if we let c = 1 − γ for small γ > 0, the expected number of edges in Gn is n1+γ or larger - that is, just superlinear in the number of vertices and potentially far smaller than O(n2 ). It is easy to convince oneself that once the graphs have only a linear number of edges, we are flirting with disconnectedness, and there may simply be large mutant sets that can survive in isolation due to the lack of any incumbent interactions in certain games. Thus in some sense we examine the minimum plausible edge density. The second result is a kind of dual to the first, considering a setting where the graphs are chosen arbitrarily (subject to conditions) but the mutant sets are chosen randomly. It states that for any 2-player, symmetric game, s is a classical ESS for that game, if and only if s is an ESS for any {Gn = (Vn, En)}∞ n=0 in which for all v ∈ Vn, deg(v) = Ω(nγ ) (for any constant γ > 0), and a family of mutant sets {Mn}∞ n=0, that is chosen randomly (that is, in which each organism is labeled a mutant with constant probability > 0). Thus, in this setting we again find that classical ESS are preserved subject to edge density restrictions. Since the degree assumption is somewhat strong, we also prove another result which only assumes that |En| ≥ n1+γ , and shows that there must exist at least 1 mutant with an incumbent neighbor of higher fitness (as opposed to showing that all but o(n) mutants have an incumbent neighbor of higher fitness). As will be discussed, this rules out stationary mutant invasions. 5.1 Random Graphs, Adversarial Mutations Now we state and prove a theorem which shows that if s is a classical ESS, then s will be an ESS for random graphs, where a linear sized set of mutants is chosen by an adversary. Theorem 5.1. Let F be any 2-player, symmetric game, and suppose s is a classical ESS of F. Let the infinite graph family {Gn}∞ n=0 be drawn according to Gn,p, where p = Ω(1/nc ) and 0 ≤ c < 1. Then with probability 1, s is an ESS. The main idea of the proof is to divide mutants into 2 categories, those with normal fitness and those with ab202 normal fitness. First, we show all but o(n) of the population (incumbent or mutant) have an incumbent neighbor of normal fitness. This will imply that all but o(n) of the mutants of normal fitness have an incumbent neighbor of higher fitness. The vehicle for proving this is Theorem 2.15 of [5], which gives an upper bound on the number of vertices not connected to a sufficiently large set. This theorem assumes that the size of this large set is known with equality, which necessitates the union bound argument below. Secondly, we show that there can be at most o(n) mutants with abnormal fitness. Since there are so few of them, even if none of them have an incumbent neighbor of higher fitness, s will still be an ESS with respect to F and G. Proof. (Sketch) Let t = s be the mutant strategy. Since s is a classical ESS, there exists an t such that (1− )F(s|s)+ F(s|t) > (1 − )F(t|s) + F(t|t), for all 0 < < t. Let M be any mutant family that is t-linear. Thus for any fixed value of n that is sufficiently large, there exists an such that |Mn| = n and t > > 0. Also, let In = Vn \ Mn and let I ⊆ In be the set of incumbents that have fitness in the range (1 ± τ)[(1 − )F(s|s) + F(s|t)] for some constant τ, 0 < τ < 1/6. Lemma 5.1 below shows (1 − )n ≥ |I | ≥ (1 − )n − 24 log n τ2p . Finally, let TI = {x ∈ V \ I : Γ(x) ∩ I = ∅}. (For the sake of clarity we suppress the subscript n on the sets I and T.) The union bound gives us Pr(|TI | ≥ δn) ≤ (1− )n X i=(1− )n− 24 log n τ2p Pr(|TI | ≥ δn and |I | = i) (1) Letting δ = n−γ for some γ > 0 gives δn = o(n). We will apply Theorem 2.15 of [5] to the summand on the right hand side of Equation 1. If we let γ = (1−c)/2, and combine this with the fact that 0 ≤ c < 1, all of the requirements of this theorem will be satisfied (details omitted). Now when we apply this theorem to Equation 1, we get Pr(|TI | ≥ δn) ≤ (1− )n X i=(1− )n− 24 log n τ2p exp „ − 1 6 Cδn « (2) = o(1) This is because equation 2 has only 24 log n τ2p terms, and Theorem 2.15 of [5] gives us that C ≥ (1 − )n1−c − 24 log n τ2 . Thus we have shown, with probability tending to 1 as n → ∞, at most o(n) individuals are not attached to an incumbent which has fitness in the range (1 ± τ)[(1 − )F(s|s) + F(s|t)]. This implies that the number of mutants of approximately normal fitness, not attached to an incumbent of approximately normal fitness, is also o(n). Now those mutants of approximately normal fitness that are attached to an incumbent of approximately normal fitness have fitness in the range (1±τ)[(1− )F(t|s)+ F(t|t)]. The incumbents that they are attached to have fitness in the range (1±τ)[(1− )F(s|s)+ F(s|t)]. Since s is an ESS of F, we know (1− )F(s|s)+ F(s|t) > (1− )F(t|s)+ F(t|t), thus if we choose τ small enough, we can ensure that all but o(n) mutants of normal fitness have a neighboring incumbent of higher fitness. Finally by Lemma 5.1, we know there are at most o(n) mutants of abnormal fitness. So even if all of them are more fit than their respective incumbent neighbors, we have shown all but o(n) of the mutants have an incumbent neighbor of higher fitness. We now state and prove the lemma used in the proof above. Lemma 5.1. For almost every graph Gn,p with (1 − )n incumbents, all but 24 log n δ2p incumbents have fitness in the range (1±δ)[(1− )F(s|s)+ F(s|t)], where p = Ω(1/nc ) and , δ and c are constants satisfying 0 < < 1, 0 < δ < 1/6, 0 ≤ c < 1. Similarly, under the same assumptions, all but 24 log n δ2p mutants have fitness in the range (1 ± δ)[(1 − )F(t|s) + F(t|t)]. Proof. We define the mutant degree of a vertex to be the number of mutant neighbors of that vertex, and incumbent degree analogously. Observe that the only way for an incumbent to have fitness far from its expected value of (1− )F(s|s)+ F(s|t) is if it has a fraction of mutant neighbors either much higher or much lower than . Theorem 2.14 of [5] gives us a bound on the number of such incumbents. It states that the number of incumbents with mutant degree outside the range (1 ± δ)p|M| is at most 12 log n δ2p . By the same theorem, the number of incumbents with incumbent degree outside the range (1 ± δ)p|I| is at most 12 log n δ2p . From the linearity of fitness as a function of the fraction of mutant or incumbent neighbors, one can show that for those incumbents with mutant and incumbent degree in the expected range, their fitness is within a constant factor of (1 − )F(s|s) + F(s|t), where that constant goes to 1 as n tends to infinity and δ tends to 0. The proof for the mutant case is analogous. We note that if in the statement of Theorem 5.1 we let c = 0, then p = 1. This, in turn, makes G = {Kn}∞ n=0, where Kn is a clique of n vertices. Then for any Kn all of the incumbents will have identical fitness and all of the mutants will have identical fitness. Furthermore, since s was an ESS for G, the incumbent fitness will be higher than the mutant fitness. Finally, one can show that as n → ∞, the incumbent fitness converges to (1 − )F(s|s) + F(s|t), and the mutant fitness converges to (1 − )F(t|s) + F(t|t). In other words, s must be a classical ESS, providing a converse to Theorem 5.1. We rigorously present this argument in Section A.1. 5.2 Adversarial Graphs, Random Mutations We now move on to our second main result. Here we show that if the graph family, rather than being chosen randomly, is arbitrary subject to a minimum degree requirement, and the mutation sets are randomly chosen, classical ESS are again preserved. A modified notion of ESS allows us to considerably weaken the degree requirement to a minimum edge density requirement. Theorem 5.2. Let G = {Gn = (Vn, En)}∞ n=0 be an infinite family of graphs in which for all v ∈ Vn, deg(v) = Ω(nγ ) (for any constant γ > 0). Let F be any 2-player, symmetric game, and suppose s is a classical ESS of F. Let t be any mutant strategy, and let the mutant family M = {Mn}∞ n=0 be chosen randomly by labeling each vertex a mutant with constant probability , where t > > 0. Then with probability 1, s is an ESS with respect to F, G and M. 203 Proof. Let t = s be the mutant strategy and let X be the event that every incumbent has fitness within the range (1 ± τ)[(1 − )F(s|s) + F(s|t)], for some constant τ > 0 to be specified later. Similarly, let Y be the event that every mutant has fitness within the range (1 ± τ)[(1 − )F(t|s) + F(t|t)]. Since Pr(X ∩ Y ) = 1 − Pr(¬X ∪ ¬Y ), we proceed by showing Pr(¬X ∪ ¬Y ) = o(1). ¬X is the event that there exists an incumbent with fitness outside the range (1±τ)[(1− )F(s|s)+ F(s|t)]. If degM (v) denotes the number of mutant neighbors of v, similarly, degI (v) denotes the number of incumbent neighbors of v, then an incumbent i has fitness degI (i) deg(i) F(s|s)+ degM (i) deg(i) F(s|t). Since F(s|s) and F(s|t) are fixed quantities, the only variation in an incumbents fitness can come from variation in the terms degI (i) deg(i) and degM (i) deg(i) . One can use the Chernoff bound followed by the union bound to show that for any incumbent i, Pr(F(i) /∈ (1 ± τ)[(1 − )F(s|s) + F(s|t)]) < 4 exp „ − deg(i)τ2 3 « . Next one can use the union bound again to bound the probability of the event ¬X, Pr(¬X) ≤ 4n exp „ − diτ2 3 « where di = mini∈V \M deg(i), 0 < ≤ 1/2. An analogous argument can be made to show Pr(¬Y ) < 4n exp(− dj τ2 3 ), where dj = minj∈M deg(j) and 0 < ≤ 1/2. Thus, by the union bound, Pr(¬X ∪ ¬Y ) < 8n exp „ − dτ2 3 « where d = minv∈V deg(v), 0 < ≤ 1/2. Since deg(v) = Ω(nγ ), for all v ∈ V , and , τ and γ are all constants greater than 0, lim n→∞ 8n exp ( dτ2/3) = 0, so Pr(¬X∪¬Y ) = o(1). Thus, we can choose τ small enough such that (1 + τ)[(1 − )F(t|s) + F(t|t)] < (1 − τ)[(1 − )F(s|s)+ F(s|t)], and then choose n large enough such that with probability 1 − o(1), every incumbent will have fitness in the range (1±τ)[(1− )F(s|s)+F(s|t)], and every mutant will have fitness in the range (1 ± τ)[(1 − )F(t|s) + F(t|t)]. So with high probability, every incumbent will have a higher fitness than every mutant. By arguments similar to those following the proof of Theorem 5.1, if we let G = {Kn}∞ n=0, each incumbent will have the same fitness and each mutant will have the same fitness. Furthermore, since s is an ESS for G, the incumbent fitness must be higher than the mutant fitness. Here again, one has to show show that as n → ∞, the incumbent fitness converges to (1 − )F(s|s) + F(s|t), and the mutant fitness converges to (1 − )F(t|s) + F(t|t). Observe that the exact fraction mutants of Vn is now a random variable. So to prove this convergence we use an argument similar to one that is used to prove that sequence of random variables that converges in probability also converges in distribution (details omitted). This in turn establishes that s must be a classical ESS, and we thus obtain a converse to Theorem 5.2. This argument is made rigorous in Section A.2. The assumption on the degree of each vertex of Theorem 5.2 is rather strong. The following theorem relaxes this requirement and only necessitates that every graph have n1+γ edges, for some constant γ > 0, in which case it shows there will alway be at least 1 mutant with an incumbent neighbor of higher fitness. A strategy that is an ESS in this weakened sense will essentially rule out stable, static sets of mutant invasions, but not more complex invasions. An example of more complex invasions are mutant sets that survive, but only by perpetually migrating through the graph under some natural evolutionary dynamics, akin to gliders in the well-known Game of Life [1]. Theorem 5.3. Let F be any game, and let s be a classical ESS of F, and let t = s be a mutant strategy. For any graph family G = {Gn = (Vn, En)}∞ n=0 in which |En| ≥ n1+γ (for any constant γ > 0), and any mutant family M = {Mn}∞ n=0 which is determined by labeling each vertex a mutant with probability , where t > > 0, the probability that there exists a mutant with an incumbent neighbor of higher fitness approaches 1 as n → ∞. Proof. (Sketch) The main idea behind the proof is to show that with high probability, over only the choice of mutants, there will be an incumbent-mutant edge in which both vertices have high degree. If their degree is high enough, we can show that close to an fraction of their neighbors are mutants, and thus their fitnesses are very close to what we expect them to be in the classical case. Since s is an ESS, the fitness of the incumbent will be higher than the mutant. We call an edge (i, j) ∈ En a g(n)-barbell if deg(i) ≥ g(n) and deg(j) ≥ g(n). Suppose Gn has at most h(n) edges that are g(n)-barbells. This means there are at least |En| − h(n) edges in which at least one vertex has degree at most g(n). We call these vertices light vertices. Let (n) be the number of light vertices in Gn. Observe that |En|−h(n) ≤ (n)g(n). This is because each light vertex is incident on at most g(n) edges. This gives us that |En| ≤ h(n) + (n)g(n) ≤ h(n) + ng(n). So if we choose h(n) and g(n) such that h(n) + ng(n) = o(n1+γ ), then |En| = o(n1+γ ). This contradicts the assumption that |En| = Ω(n1+γ ). Thus, subject to the above constraint on h(n) and g(n), Gn must contain at least h(n) edges that are g(n)-barbells. Now let Hn denote the subgraph induced by the barbell edges of Gn. Note that regardless of the structure of Gn, there is no reason that Hn should be connected. Thus, let m be the number of connected components of Hn, and let c1, c2, . . . , cm be the number of vertices in each of these connected components. Note that since Hn is an edge-induced subgraph we have ck ≥ 2 for all components k. Let us choose the mutant set by first flipping the vertices in Hn only. We now show that the probability, with respect to the random mutant set, that none of the components of Hn have an incumbent-mutant edge is exponentially small in n. Let An be the event that every component of Hn contains only mutants or only incumbents. Then algebraic manipulations can establish that Pr[An] = Πm k=1( ck + (1 − )ck ) ≤ (1 − )(1− β2 2 ) Pm k=1 ck 204 where β is a constant. Thus for sufficiently small the bound decreases exponentially with Pm k=1 ck. Furthermore, sincePm k=1 `ck 2 ´ ≥ h(n) (with equality achieved by making each component a clique), one can show that Pm k=1 ck ≥ p h(n). Thus, as long as h(n) → ∞ with n, the probability that all components are uniformly labeled will go to 0. Now assuming that there exists a non-uniformly labeled component, by construction that component contains an edge (i, j) where i is an incumbent and j is a mutant, that is a g(n)-barbell. We also assume that the h(n) vertices already labeled have been done so arbitrarily, but that the remaining g(n) − h(n) vertices neighboring i and j are labeled mutants independently with probability . Then via a standard Chernoff bound argument, one can show that with high probability, the fraction of mutants neighboring i and the fraction of mutants neighboring j is in the range (1 ± τ)(g(n)−h(n)) g(n) . Similarly, one can show that the fraction of incumbents neighboring i and the fraction of mutants neighboring j is in the range 1 − (1 ± τ)(g(n)−h(n)) g(n) . Since s is an ESS, there exists a ζ > 0 such that (1 − )F(s|s) + F(s|t) = (1 − )F(t|s) + F(t|t) + ζ. If we choose g(n) = nγ , and h(n) = o(g(n)), we can choose n large enough and τ small enough to force F(i) > F(j), as desired. 6. LIMITATIONS OF STRONGER MODELS In this section we show that if one tried to strengthen the model described in Section 3 in two natural ways, one would not be able to prove results as strong as Theorems 5.1 and 5.2, which hold for every 2-player, symmetric game. 6.1 Stronger Contraction for the Mutant Set In Section 3 we alluded to the fact that we made certain design decisions in arriving at Definitions 3.1, 3.2 and 3.3. One such decision was to require that all but o(n) mutants have incumbent neighbors of higher fitness. Instead, we could have required that all mutants have an incumbent neighbor of higher fitness. The two theorems in this subsection show that if one were to strengthen our notion of contraction for the mutant set, given by Definition 3.1, in this way, it would be impossible to prove theorems analogous to Theorems 5.1 and 5.3. Recall that Definition 3.1 gave the notion of contraction for a linear sized subset of mutants. In what follows, we will say an edge (i, j) contracts if i is an incumbent, j is a mutant, and F(i) > F(j). Also, recall that Theorem 5.1 stated that if s is a classical ESS, then it is an ESS for random graphs with adversarial mutations. Next, we prove that if we instead required every incumbent-mutant edge to contract, this need not be the case. Theorem 6.1. Let F be a 2-player, symmetric game that has a classical ESS s for which there exists a mutant strategy t = s with F(t|t) > F(s|s) and F(t|t) > F(s|t). Let G = {Gn}∞ n=0 be an infinite family of random graphs drawn according to Gn,p, where p = Ω(1/nc ) for any constant 0 ≤ c < 1. Then with probability approaching 1 as n → ∞, there exists a mutant family M = {Mn}∞ n=0, where tn > |Mn| > n and t, > 0, in which there is an edge that does not contract. Proof. (Sketch) With probability approaching 1 as n → ∞, there exists a vertex j where deg(j) is arbitrarily close to n. So label j mutant, label one of its neighbors incumbent, denoted i, and label the rest of j"s neighborhood mutant. Also, label all of i"s neighbors incumbent, with the exception of j and j"s neighbors (which were already labeled mutant). In this setting, one can show that F(j) will be arbitrarily close to F(t|t) and F(i) will be a convex combination of F(s|s) and F(s|t), which are both strictly less than F(t|t). Theorem 5.3 stated that if s is a classical ESS, then for graphs where |En| ≥ n1+γ , for some γ > 0, and where each organism is labeled a mutant with probability , one edge must contract. Below we show that, for certain graphs and certain games, there will always exist one edge that will not contract. Theorem 6.2. Let F be a 2-player, symmetric game that has a classical ESS s, such that there exists a mutant strategy t = s where F(t|s) > F(s|t). There exists an infinite family of graphs {Gn = (Vn, En)}∞ n=0, where |En| = Θ(n2 ), such that for a mutant family M = {Mn}∞ n=0, which is determined by labeling each vertex a mutant with probability > 0, the probability there exists an edge in En that does not contract approaches 1 as n → ∞. Proof. (Sketch) Construct Gn as follows. Pick n/4 vertices u1, u2, . . . , un/4 and add edges such that they from a clique. Then, for each ui, i ∈ [n/4] add edges (ui, vi), (vi, wi) and (wi, xi). With probability 1 as n → ∞, there exists an i such that ui and wi are mutants and vi and xi are incumbents. Observe that F(vi) = F(xi) = F(s|t) and F(wi) = F(t|s). 6.2 Stronger Contraction for Individuals The model of Section 3 requires that for an edge (i, j) to contract, the fitness of i must be greater than the fitness of j. One way to strengthen this notion of contraction would be to require that the maximum fitness incumbent in the neighborhood of j be more fit than the maximum fitness mutant in the neighborhood of j. This models the idea that each organism is trying to take over each place in its neighborhood, but only the most fit organism in the neighborhood of a vertex gets the privilege of taking it. If we assume that we adopt this notion of contraction for individual mutants, and require that all incumbent-mutant edges contract, we will next show that Theorems 6.1 and 6.2 still hold, and thus it is still impossible to get results such as Theorems 5.1 and 5.3 which hold for every 2-player, symmetric game. In the proof of Theorem 6.1 we proved that F(i) is strictly less than F(j). Observe that maximum fitness mutant in the neighborhood of j must have fitness at least F(j). Also observe that there is only 1 incumbent in the neighborhood of j, namely i. So under this stronger notion of contraction, the edge (i, j) will not contract. Similarly, in the proof of Theorem 6.2, observe that the only mutant in the neighborhood of wi is wi itself, which has fitness F(t|s). Furthermore, the only incumbents in the neighborhood of wi are vi and xi, both of which have fitness F(s|t). By assumption, F(t|s) > F(s|t), thus, under this stronger notion of contraction, neither of the incumbentmutant edges, (vi, wi) and (xi, wi), will contract. 7. REFERENCES [1] Elwyn R. Berlekamp, John Horton Conway, and Richard K. Guy. Winning Ways for Your 205 Mathematical Plays, volume 4. AK Peters, Ltd, March 2004. [2] Jonas Bj¨ornerstedt and Karl H. Schlag. On the evolution of imitative behavior. Discussion Paper B-378, University of Bonn, 1996. [3] L. E. Blume. The statistical mechanics of strategic interaction. Games and Economic Behavior, 5:387-424, 1993. [4] L. E. Blume. The statistical mechanics of best-response strategy revision. Games and Economic Behavior, 11(2):111-145, November 1995. [5] B. Bollob´as. Random Graphs. Cambridge University Press, 2001. [6] Michael Suk-Young Chwe. Communication and coordination in social networks. Review of Economic Studies, 67:1-16, 2000. [7] Glenn Ellison. Learning, local interaction, and coordination. Econometrica, 61(5):1047-1071, Sept. 1993. [8] I. Eshel, L. Samuelson, and A. Shaked. Altruists, egoists, and hooligans in a local interaction model. The American Economic Review, 88(1), 1998. [9] Geoffrey R. Grimmett and David R. Stirzaker. Probability and Random Processes. Oxford University Press, 3rd edition, 2001. [10] M. Jackson. A survey of models of network formation: Stability and efficiency. In Group Formation in Economics; Networks, Clubs and Coalitions. Cambridge University Press, 2004. [11] S. Kakade, M. Kearns, J. Langford, and L. Ortiz. Correlated equilibria in graphical games. ACM Conference on Electronic Commerce, 2003. [12] S. Kakade, M. Kearns, L. Ortiz, R. Pemantle, and S. Suri. Economic properties of social networks. Neural Information Processing Systems, 2004. [13] M. Kearns, M. Littman, and S. Singh. Graphical models for game theory. Conference on Uncertainty in Artificial Intelligence, pages 253-260, 2001. [14] E. Lieberman, C. Hauert, and M. A. Nowak. Evolutionary dynamics on graphs. Nature, 433:312-316, 2005. [15] S. Morris. Contagion. Review of Economic Studies, 67(1):57-78, 2000. [16] Karl H. Schlag. Why imitate and if so, how? Journal of Economic Theory, 78:130-156, 1998. [17] J. M. Smith. Evolution and the Theory of Games. Cambridge University Press, 1982. [18] William L. Vickery. How to cheat against a simple mixed strategy ESS. Journal of Theoretical Biology, 127:133-139, 1987. [19] J¨orgen W. Weibull. Evolutionary Game Theory. The MIT Press, 1995. APPENDIX A. GRAPHICAL AND CLASSICAL ESS In this section we explore the conditions under which a graphical ESS is also a classical ESS. To do so, we state and prove two theorems which provide converses to each of the major theorems in Section 3. A.1 Random Graphs, Adversarial Mutations Theorem 5.2 states that if s is a classical ESS and G = {Gn,p}, where p = Ω(1/nc ) and 0 ≤ c < 1, then with probability 1 as n → ∞, s is an ESS with respect to G. Here we show that if s is an ESS with respect to G, then s is a classical ESS. In order to prove this theorem, we do not need the full generality of s being an ESS for G when p = Ω(1/nc ) where 0 ≤ c < 1. All we need is s to be an ESS for G when p = 1. In this case there are no more probabilistic events in the theorem statement. Also, since p = 1 each graph in G is a clique, so if one incumbent has a higher fitness than one mutant, then all incumbents have higher fitness than all mutants. This gives rise to the following theorem. Theorem A.1. Let F be any 2-player, symmetric game, and suppose s is a strategy for F and t = s is a mutant strategy. Let G = {Kn}∞ n=0. If, as n → ∞, for any t-linear family of mutants M = {Mn}∞ n=0, there exists an incumbent i and a mutant j such that F(i) > F(j), then s is a classical ESS of F. The proof of this theorem analyzes the limiting behavior of the mutant population as the size of the cliques in G tends to infinity. It also shows how the definition of ESS given in Section 5 recovers the classical definition of ESS. Proof. Since each graph in G is a clique, every incumbent will have the same number of incumbent and mutant neighbors, and every mutant will have the same number of incumbent and mutant neighbors. Thus, all incumbents will have identical fitness and all mutants will have identical fitness. Next, one can construct an t-linear mutant family M, where the fraction of mutants converges to for any , where t > > 0. So for n large enough, the number of mutants in Kn will be arbitrarily close to n. Thus, any mutant subset of size n will result in all incumbents having fitness (1 − n n−1 )F(s|s) + n n−1 F(s|t), and all mutants having fitness (1 − n−1 n−1 )F(t|s) + n−1 n−1 F(t|t). Furthermore, by assumption the incumbent fitness must be higher than the mutant fitness. This implies, lim n→∞ „ (1 − n n − 1 )F(s|s) + n n − 1 F(s|t) > (1 − n − 1 n − 1 )F(t|s) + n − 1 n − 1 F(t|t) « = 1. This implies, (1− )F(s|s)+ F(s|t) > (1− )F(t|s)+ F(t|t), for all , where t > > 0. A.2 Adversarial Graphs, Random Mutations Theorem 5.2 states that if s is a classical ESS for a 2player, symmetric game F, where G is chosen adversarially subject to the constraint that the degree of each vertex is Ω(nγ ) (for any constant γ > 0), and mutants are chosen with probability , then s is an ESS with respect to F, G, and M. Here we show that if s is an ESS with respect to F, G, and M then s is a classical ESS. All we will need to prove this is that s is an ESS with respect to G = {Kn}∞ n=0, that is when each vertex has degree n − 1. As in Theorem A.1, since the graphs are cliques, if one incumbent has higher fitness than one mutant, then all incumbents have higher fitness than all mutants. Thus, the theorem below is also a converse to Theorem 5.3. (Recall that Theorem 5.3 uses a weaker notion of contraction that 206 requires only one incumbent to have higher fitness than one mutant.) Theorem A.2. Let F be any 2-player symmetric game, and suppose s is an incumbent strategy for F and t = s is a mutant strategy. Let G = {Kn}∞ n=0. If with probability 1 as n → ∞, s is an ESS for G and a mutant family M = {Mn}∞ n=0, which is determined by labeling each vertex a mutant with probability , where t > > 0, then s is a classical ESS of F. This proof also analyzes the limiting behavior of the mutant population as the size of the cliques in G tends to infinity. Since the mutants are chosen randomly we will use an argument similar to the proof that a sequence of random variables that converges in probability, also converge in distribution. In this case the sequence of random variables will be actual fraction of mutants in each Kn. Proof. Fix any value of , where n > > 0, and construct each Mn by labeling a vertex a mutant with probability . By the same argument as in the proof of Theorem A.1, if the actual number of mutants in Kn is denoted by nn, any mutant subset of size nn will result in all incumbents having fitness (1 − nn n−1 )F(s|s) + nn n−1 F(s|t), and in all mutants having fitness (1 − nn−1 n−1 )F(t|s) + nn−1 n−1 F(t|t). This implies lim n→∞ Pr(s is an ESS for Gn w.r.t. nn mutants) = 1 ⇒ lim n→∞ Pr „ (1 − nn n − 1 )F(s|s) + nn n − 1 F(s|t) > (1 − nn − 1 n − 1 )F(t|s) + nn − 1 n − 1 F(t|t) « = 1 ⇔ lim n→∞ Pr „ n > F(t|s) − F(s|s) F(s|t) − F(s|s) − F(t|t) + F(t|s) + F(s|s) − F(t|t) n « = 1 (3) By two simple applications of the Chernoff bound and an application of the union bound, one can show the sequence of random variables { n}∞ n=0 converges to in probability. Next, if we let Xn = − n, X = − , b = −F(s|s) + F(t|t), and a = − F (t|s)−F (s|s) F (s|t)−F (s|s)−F (t|t)+F (t|s) , by Theorem A.3 below, we get that limn→∞ Pr(Xn < a + b/n) = Pr(X < a). Combining this with equation 3, Pr( > −a) = 1. The proof of the following theorem is very similar to the proof that a sequence of random variables that converges in probability, also converge in distribution. A good explanation of this can be found in [9], which is the basis for the argument below. Theorem A.3. If {Xn}∞ n=0 is a sequence of random variables that converge in probability to the random variable X, and a and b are constants, then limn→∞ Pr(Xn < a+b/n) = Pr(X < a). Proof. By Lemma A.1 (see below) we have the following two inequalities, Pr(X < a + b/n − τ) ≤ Pr(Xn < a + b/n) + Pr(|X − Xn| > τ), Pr(Xn < a + b/n) ≤ Pr(X < a + b/n + τ) + Pr(|X − Xn| > τ). Combining these gives, Pr(X < a + b/n − τ) − Pr(|X − Xn| > τ) ≤ Pr(Xn < a + b/n) ≤ Pr(X < a + b/n + τ) + Pr(|X − Xn| > τ). There exists an n0 such that for all n > n0, |b/n| < τ, so the following statement holds for all n > n0. Pr(X < a − 2τ) − Pr(|X − Xn| > τ) ≤ Pr(Xn < a + b/n) ≤ Pr(X < a + 2τ) + Pr(|X − Xn| > τ). Take the limn→∞ of both sides of both inequalities, and since Xn converges in probability to X, Pr(X < a − 2τ) ≤ lim n→∞ Pr(Xn < a + b/n) (4) ≤ Pr(X < a + 2τ). (5) Recall that X is a continuous random variable representing the fraction of mutants in an infinite sized graph. So if we let FX (a) = Pr(X < a), we see that FX (a) is a cumulative distribution function of a continuous random variable, and is therefore continuous from the right. So lim τ↓0 FX (a − τ) = lim τ↓0 FX (a + τ) = FX (a). Thus if we take the limτ↓0 of inequalities 4 and 5 we get Pr(X < a) = lim n→∞ Pr(Xn < a + b/n). The following lemma is quite useful, as it expresses the cumulative distribution of one random variable Y , in terms of the cumulative distribution of another random variable X and the difference between X and Y . Lemma A.1. If X and Y are random variables, c ∈ and τ > 0, then Pr(Y < c) ≤ Pr(X < c + τ) + Pr(|Y − X| > τ). Proof. Pr(Y < c) = Pr(Y < c, X < c + τ) + Pr(Y < c, X ≥ c + τ) ≤ Pr(Y < c | X < c + τ) Pr(X < c + τ) + Pr(|Y − X| > τ) ≤ Pr(X < c + τ) + Pr(|Y − X| > τ) 207
network nash equilibrium power of randomization evolutionary game theory undirected graph evolutionary stable strategy mutation set graph topology relationship of topology game theory
randomization power pairwise interaction edge density condition natural strengthening geographical restriction equilibrium outcome topology relationship graph-theoretic model