Chapter 5: Mutation-selection equilibrium in games with multiple strategies 91 self interaction here, since it does not make a difference in the large N limit. The total payoff of the whole population is F = XTf = N(1 + 6xTAx). We assume weak selection throughout this paper, by which we mean that (SN cc 1. The need for such weak selection (as opposed to 6 cc 1) shall become clear at the end of this section. The dynamics of the system is given by the frequency dependent Moran process. In each time step a randomly chosen individual is replaced by a copy of an individual chosen with probability proportional to its payoff. The offspring inherits the parent's strategy with probability 1 — u, or adopts a random strategy with probability u > 0. We shall show below that the condition for strategy k to be more abundant than the average 1/n is equivalent to having a positive average change of its frequency during a single update step. Hence we start deriving this latter quantity. In state X, the average number of offspring (fitness) of a k-player due to selection is Wk = 1 — 1/N+ fk/F. We also included the parent among the offspring, which explains the leading 1 on the right hand side. The term —1/N describes its random death, while the term fk/F stands for the proliferation proportional to payoff. For 6 —) 0, the fitness can be written as wk = 1 +45N-1 [(Ax)k — xr Ax[ + O(6ZN-1), In one update step, the frequency of k-players changes on average due to selection by aar i = xkwk — xk = 8AxT[1 + O(6)], (5.6) where the first derivative with respect to 6 is Axil) = N-1 xk[(Ax)k — xr Ax]. (5.7) (5.5) The state of the system, X, changes over time due to selection and mutation. In the stationary state of the Moran process we find the system in state X with probability /95(X). This stationary probability distribution is the eigenvector with the largest eigenvalue of the EFTA00748958

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 92 stochastic transition matrix of the system [162]. The elements of the transition matrix depend on 6 only through f = 1 + O(6). Note that there is no N dependence in the correction term, since both A and x are independent of N. Consequently, the stationary probabilities are continuous at 6 = 0, and we can write them as Po(X) = Pa.o(X)11+O(6)) for any state X. Hence by averaging Arskel in the stationary state, in the leading order in 6 we obtain (Ax?')o E E Axrpo(x) = 8 EAxr)ps=0(x) x [1+ O(8)]. (5.8) Thus, we can describe the stationary state of the system for small 6 by using the stationary distribution in the absence of selection, 6 = 0. Since the correction term is independent of N, the above formula remains valid even in the large population size limit. Using expression (5.7) for Axil), the average change due to selection in the leading order can be written as (aarl)s = 61V-1 (Xkl(AX)k XTAXD = 6N-1 (Eaki(skxj) — E aij(xkxixj)), (5.9) where (.) denotes the average in the neutral stationary state (6 = 0). So far we have only considered selection. By taking into account mutation as well, the expected total change of frequency in state X during one update step can be written as U 1 A r tkot = A r akel(1 ( - 2k) N n (5.10) The first term on the right hand side describes the change in the absence of mutation, which happens with probability 1 — u. The second term stands for the change due to mutation, which happens with probability u. In this latter case the frequency 24 increases by 1/nN due to the introduction of a random type, and decreases by xk/N due to random death. In the stationary state the average total change of the frequency is zero, (Ax109,5 = 0, that is selection and mutation are in balance. Hence by averaging (5.10) we obtain the abundance EFTA00748959

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 93 (average frequency) in the stationary state expressed by the average change due to selection as 1 1 — u (xk).5 = + N (AxEkle Xs • (5.11) We emphasize that this relationship is valid at any intensity of selection, although we are going to use it only in the weak selection limit. From (5.11) it follows that the condition (x4,5 > 1/n is in fact equivalent to (aixThe > 0 . (5.12) That is, for strategy k to be more abundant than the average, the change due to selection must be positive in the stationary state. Hence, as we claimed, instead of computing the mean frequency, we can now concentrate on the average change (5.9) during a single update step. To evaluate (5.9) we need to calculate averages of the form (xkx5) and (xkxixj). Since in the neutral stationary state all players are equivalent, exchanging indexes does not affect the averages. For example (xixi) = (x3x3), and (xix2x2) = (xix3x3). By taking into account these symmetries, only six different averages appear in (5.9) (5.13) EFTA00748960

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 94 for allk0i0j0k. Equation (5.9) then takes the form Ne-l(Oaskel) = s (2121)nick + (x1x2) E aki (212121)akk i,i0k (x1x2x2) > (aki+ aii + am) — (x122x3)E aij • i,iok kothok Note that (xix2x3) is not defined for n = 2, but in that case the last sum in (5.14) is zero anyway. Hence the following derivation is valid even for n = 2. By removing the restrictions from the summations in (5.14), we can rearrange this expression into NS-1(L4et),5 = akk((2121) — (x1x2) — (212120 + 3(212222) — 2(212223)) + (x1x2) Eaki+uxix2x3)—(xix2x2))E(aki+aii+ ask) — (x1x2x3)E au • Let us now interpret these average quantities. We draw j players at random from the population in the neutral stationary state, and define si as the probability that all of them have the same strategy. We have (21) = n-1 because under neutrality a player has 1/n chance of having strategy one out of 71 possibilities. Moreover, we have (2121) = s2n-I, because the first player has strategy one with probability 1/n and the second player uses the same strategy with probability s2. Similarly (212121) = 53n-1 holds. The remaining averages that appear in (5.15) can be written as (5.14) (5.15) (2122) = ((1 - > 21)22) = (21) - (2121) - (n - 2)(2122) 2<i<n (212222) = ((1 - E rox2x2)= (2121) — (212121) — (rt — 2)(212222) 2<i<n (212223) = ((1 - > rox2x3)= ( 2 12 2) — 2(212222) — (n — 3)(212223) 2<i<n where we used the normalization condition Ei xi = 1, and the symmetry relations (5.13). EFTA00748961

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 95 Thus, we can express all the averages in (5.13) in terms of only two probabilities, s2 and s3 , = re , 82 (xis'? = —n — (x122) n(n — 1) 83 = (X1X2X2) S2 - SS n(n — 1) 1 — 382 + 2s3 (xix,2x8) n(n — 1)(n — 2) We note again that for n = 2 the last expression is ill defined, but it is not needed in that case. (5.16) Up to this point everything was calculated for finite N. Although further discussion for finite N is possible, it becomes quite unwieldy; hence for simplicity we consider only the large N limit from here on. In Appendix 5.5 we calculate the values of s2 and 53 for N » 1, which are given by (5.48) and (5.52), respectively. By substituting these expressions into (5.16) we arrive at (xi xi) = n(2 + 11)(n + (xix2) = + µ}nC (2421x1) = (n + µ)(2n + (5.17) (xix2x2) =1/(n + (x1x2x3) = it2C , where C = INn3(1 + µ)(2 + µ)]-1 and µ = Nu is the resealed mutation rate. With these correlations, (5.15) takes the form (Ae el)6 2 Co. — pn akk + µ(2 + µ)n E - µn 2 id EFTA00748962

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 96 where rearranging the terms leads to ( ; 6)6 — 2 (11. aki — %) + itnE(akk + aki cra — aa)• By defining 1 n , Lk = 2_,kakk+ aki — aik — n 1 Hk = n 2 kaki ii we finally arrive at our main result A soh. _ (Lk + PRO ( Xk nN (1 + A)(2 + A) (5.18) (5.19) This expression is valid in the limit of large population size N >> 1, for weak selection NO <1, with µ = Nu being constant. Condition (5.12) for strategy k to be more abundant than the average 1/n is simply Lk + µHk > 0 as we already announced in (5.3). In the low mutation limit (µ —. 0) the condition for abundance becomes Lk > 0, while in the high mutation limit (µ —• co) it is 14 > 0. As a consequence of (5.11), strategy k is more abundant than strategy j if Lk +Affk >L1+AHi. Note that any finite mutation probability corresponds to the high mutation rate limit —) co for our N co limit. By substituting (5.19) into (5.11) we obtain the abundances (average frequencies) in the weak selection stationary state Lk -I- N'11,Hk (X06 = [1+ 6N(1 /) (1 + Nu)( + Nu)] (5.20) This expression becomes exact in the N co, NO —) 0 limit, if Nu = µ is kept constant. It becomes clear at this point, that although we only used 0 « 1 to derive (5.19), we actually need ON <1 to have frequencies close to 1/n in (5.20). EFTA00748963

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 97 5.2.1 Special case: Two strategies For only two strategies (n = 2) the general formula (5.19) leads to Su (aaiel).5 = 8(1 + Nu) (an + ahz — a21 — az2)• (5.21) The peculiarity of the two strategy case is that the condition for higher abundance (mean frequency) (5.12) of strategy one an + alz — azt — azz > 0 (5.22) does not depend on the mutation probability u. It has been shown in 13] that very similar conditions hold for finite population size. With self interaction we obtain the same result, but when self interaction is excluded, the condition becomes (au + alz — a21 — az2)N — 2a11 2azz > 0 (5.23) This condition does not depend on the mutation probability u either. Moreover, the above conditions are also valid for arbitrary strength of selection for a general class of models, in particular for the Moran model with exponential payoff functions or for the Pairwise Comparison process [3]. Note that this law is well known for several models in the low mutation rate limit 165, 110]. 5.2.2 Low mutation rates There is an intimate relationship between our conditions for high abundance and fixation probabilities for low mutation ratesµ 1. In this limit, most of the time all players follow the same strategy, and rarely a single mutant takes over the entire homogeneous population (fixates). During fixation only two types of players are present. The fixation probability pia is the probability that a single i-player overtakes a population of j-players. EFTA00748964

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 98 Hence we have effectively 71 states of pure strategies, where a state of pure strategy j changes to a state of pure strategy i at rate µpia/n. Let us first consider n = 2 strategy games, where we label the two strategies as k and i. In the stationary state there are rare transitions between pure k-player and pure i-player states, and (xk)Pik = (xi)Pki with (xk) + (xi) = 1. Hence we can write (xk) = [1 + 2(Pki — Pik)] (5.24) since all fixation probabilities are 1/N in the leading order of 6. On the other hand, the abundance (5.20) for two strategies and ow mutations becomes (xk} (x = 2 k 2 ( 1 + _NaLk) (5.25) Consequently, we can express 6./..k as 2 (akk + aki aik a11) = Ph — Pik- (5.26) This equality can also be derived independently from the exact expression of the fixation probability [110] Pki = [1 + 6N ,akk 2aki — elk — 264 (5.27) For n strategies, by using (5.1) and (5.26), we can express Lk with pairwise fixation probabilities as Lk = (2/6n) EE Pki — The condition Lk > 0 for strategy k to be more abundant than 1/n can be written as EPki > E Pik (5.28) This condition can be interpreted as follows: strategy k is more abundant than 1/n in the low mutation rate limit if the average fixation probability of a single k-player into other pure strategy states is larger than the average fixation probability of other strategies into a pure strategy k population. For these averages we take all strategies with the same weights. EFTA00748965

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 99 5.3 Examples Here we provide three applications of our results for three strategy games. First in 5.3.1 we study the effect of Loners on Cooperators and Defectors. Then in 5.3.2 we show how mutation alone can make a strategy more abundant. Finally in 5.3.3 we study the repeated Prisoner's Dilemma game. 5.3.1 Cooperators, Defectors, Loners To see the difference between our weak selection and a traditional game-theoretic approach, let us consider the following example. We start with a Prisoner Dilemma game between cooperators (C) and defectors (D), given by the payoff matrix C V C (10 1 ) (5.29) D 11 2 Clearly, defectors dominate cooperators, so we expect that defectors are more abundant in a stationary state. Indeed, from condition (5.22) we obtain an + — — a22 = —2 <0. (5.30) Thus strategy D is more abundant than C for any mutation rate. Surprisingly, the introduction of loners (C), which do not participate in the game [46], can dramatically change the balance between C and D. Consider the following game: C D L C 10 1 0 D 11 i 2 0 • (5.31) £ 0 0 0 EFTA00748966

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 100 Loners are dominated by cooperators and defectors. Elimination of the dominated strategy leads to a game between C and D, in which V is winning. Thus, standard game theoretic arguments predict that strategy V is the most abundant. However, these arguments fail for weak selection, where it is not enough to know that a strategy dominates another, but also how strong this dominance is. In pairwise interactions, the advantage of C over G is significantly larger than that of V over G as can be seen from the matrices: C C (10 0 0 0 ( 0 0 2 0 ) .0 (5.32) This advantage of C can overcompensate the disadvantage it has against D, therefore the abundance of C can be the highest. Indeed, the relevant quantities for low mutation rates are LD = 4 and Lc = —4. (5.33) Thus, both C and D have larger abundance than the neutral value 1/3. But since Le > LD, strategy C has the highest abundance. The introduction of loners causes the reversal of abundance between C and D when the mutation rates are small. In other words we can say the loners favor cooperators. For high mutation rates the relevant quantities are He = 1, HD = 5 —' and 114 = —! 3 3 (5.34) Hence, according to (5.3), both C and V have an abundance larger than 1/3 for any mutation rate. For high mutation rates, however, since He < HD, strategy V becomes the most abundant. In fact, C is the most abundant for p < µ" E 2, but it is V forµ > µ". EFTA00748967

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 101 10 8 Payoff Parameter A 6 4 32 > SS> 31> xj. Si S2 S3 ( 0 13) S2 0 A 8 S3 0 7 9 X2 > >%>x 3 xi > 22 > ) > 211 > I x,>%> 23 > 22 xi >x3alos›x2 22 > %>32>x, Xs > XI > $.$2. 22 2 ' 0.01 0.1 I 10 Mutation Rate µ x2 > x.s> rS>x,1 100 Fig. 5.1: Strategy abundance (mean frequency) in the game given by the payoff matrix (5.35). Colored lines show the critical conditions under which one of the three strategies exceeds an abundance of 1/3. For small mutation rates, S1 is favored over S3, but for large mutation rate, S3 is favored over Si. All three strategies have equal abundance at the intersection of all boundaries. 5.3.2 Reversing the ranking of strategies by mutation As a second example, we address the game S1 S2 33 Sl 1 0 13 52 0 A 8 (5.35) S3 0 7 9 where A is a free parameter. For A < 7, 32 is dominated by S3. Moreover, Si dominates S3, and SI and 52 are bistable. Thus, classical game theoretic analysis shows that for A < 7, all players should choose Si. It turns out that this state is also the only stable fixed point of the replicator equation for A < 7. EFTA00748968

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 102 However, the above reasoning does not apply for weak selection. The relevant quan- tities for low mutation rates are 6 3 A 2A 3 — 9 3 3 A = L2 = and L3 — (5.36) and for high mutation rates they are 4 — A Hn = 9 2A 9 — 14 10 9 — A — and H3 — (5.37) Thus, we expect thresholds where the abundance of a strategy crosses 1/3 at A = 3, A = 4.5, and A = 6 for small mutation rates and at A = 4, A = 7, and A = 10 for high mutation rates. For each mutation rate and each value of A, our conditions determine the order of strategies. Fig. 5.1 shows the change of these thresholds with the mutation rate. There are six possibilities for ordering of these three strategies. In each of these cases, there can be one or two strategies with an abundance larger than 1/3. Therefore, there are 12 ways for ordering the strategies relative to 1/3. In this concrete example, all of these 12 regions can be obtained by varying the parameter A and the mutation rate A. For example if we fix A = 4.6, just by changing the resealed mutation rate, we obtain six different orderings of the strategies relative to 1/3, as one can see in Fig. 5.1. In order to verify our results we performed simulations of the Moran model with the payoff matrix (5.35), at A = 4.6. In figure 5.2, we compare the simulated frequencies of strategies to the theoretical frequencies given by (5.20). The theory becomes exact in the N co, N8 0, and = Nu constant limit. As shown in figure 5.2, already at N = 30, and 6 = 0.003, which corresponds to NJ = 0.09, we find an excellent agreement with the theory. EFTA00748969

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 103 0.340 60 0.336 8 <.o 0.332 0.328 0.1 0.2 0.5 1.0 2.0 5.0 Mutation Rate µ 10.0 20.0 Fig. 5.2: Simulation results for strategy abundances as a function of the resealed mutation rate µ = Nu in the game of payoff matrix (5.35), at A = 4.6. The population size is N = 30 and the selection strength is 6 = 0.003, which means NS = 0.09. The solid lines are the theoretical curves given by (5.20), and the dotted line marks the average abundance 1/3. The intersections of the lines are located at the critical values given by (5.3) and (5.4). The highest possible value of the mutation rate at this system size is A = 30, which corresponds to mutation probability u = 1, where all densities are equal. EFTA00748970

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 104 5.3.3 Cooperators, Defectors, and Tit-for-Tat As a third example, we discuss the interaction of 'always cooperate' (ABC), `always defect' (AIID), and 'tit-for-tat' (TFT) strategies in the repeated Prisoner's Dilemma game 1111, 17]. Each pair of players plays In > 2 rounds. TFT follows its opponent strategy in the previous round, but cooperates in the first round. Acting as a cooperator costs c for a player, but one gets benefit b from playing with a cooperator. Hence, the payoff matrix is given by AIIC AHD ITT A11° (b — c)m —cm (b — c)m AIID bm 0 b • TFT (b — c)m —c (b — c)m For low mutation rates, the relevant quantities are LAIID 3 LAIIC = —2e3m —b(m —1) + c(3m +1) (5.38) (5.39) b(m — 1)— c(m +1) LTFT 3 • The most apparent consequence is that for low mutation rates cooperators never exceed the abundance of 1/3. This is not surprising, since ABC is a fairly dull strategy: the mean AHD and the cleverer TFT is expected to perform better. As we increase the benefit to cost ratio We, the order of abundance of these strategies change at several particular values. For 21 < 1-73-±1 only the abundance of AHD is larger than 1/3. For 2a±-1 c m-1, m-1 m-1 the abundance of both AIID and TFT is above 1/3, with AHD still dominating TFT. For becomes more abundant than AHD, for 6 > '3221±-1 the abundance of AIID m-i m1 drops below 1/3, and for be > 5,71 , it is even smaller than the abundance of AIIC. EFTA00748971

HAIID 9 b(m - 1) - c(m + HTFT- 9 Chapter 5: Mutation-selection equilibrium in games with multiple strategies 105 (a) Low mutation rates TFT ANC AIID (b) High mutation rates PJIC A„, 4 6 3m ;'. 6 5m+ I 2(m- 0 6 m+2 -1 MID Fig. 5.3: Strategy abundance in the interaction between AK, AHD, and TFT in the prob- ability simplex S3. Dark areas are inaccessible to the evolutionary dynamics. Red lines show thresholds where a strategy abundance crosses 1/3, the thresholds are given in terms of b/c. Blue lines depict thresholds where two strategy abundances are identical. (a) For small mutation rates, the abundance of Al1C is never above 1/3 and it is never greater than the abundance of ITT. (b) For high mutation rates, the abundance of Alle is above 1/3 in the yellow shaded area, but again it never exceeds the abundance of TFT. For high mutation rates, the relevant quantities are Om —1)— c(4m — 1) HAIIC 9 —2b(m — 1) + c(5m + 1) (5.40) Surprisingly, now the abundance of Alle can exceed 1/3 for high mutation rates. Again, as we increase the benefit to cost ratio b/c, the abundances change order at particular b/c values, which values are different for the high and low mutation rate limits. For high mutation rates, when be < ta-+-- m_1, only the abundance of AIID exceeds 1/3. For ta-±-".? < ac < also the abundance of TFT is larger than 1/3, but does not exceed the abundance of AIID. For 2S" < < b 2rm+_1), AIID is less abundant than TFT. At 27,t+1), the ta- abundance of AIID drops below 1/3 and it becomes identical to the abundance of MC at = j--3t—n Finally, for 0. > n •W even the abundance of ARC exceeds 1/3, but it ta-i• m- , EFTA00748972

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 106 always remains below the abundance of TFT. The relations between the strategies and these thresholds are depicted in Fig. 5.3. The most interesting region is > where the abundance of AIIC exceeds 1/3 (the yellow region in Fig 5.3b). This is not possible for low mutation rates. High mutation rates and the TFT strategy can facilitate AI1C to increase its abundance above average. 5.4 Outlook In this section we discuss possible extensions and limitations of our method. First in 5.4.1 we address the strong selection limit. Then in 5.4.2 we consider more general mutation rates. Finally in 5.4.3 two alternative dynamics are studied. 5.4.1 Strong selection Can we say something without the weak selection assumption? As we mentioned in Section 5.2.2, for only two strategies condition (5.19) is valid for any intensity of selection in a wide class of models [3]. We can also argue that our condition (5.2) is valid for very high mutation probabilities, namely for ti 1, for arbitrary strength of selection. In this case players pick random strategies most of the time, hence the frequencies of all strategies are close to 1/n. This implies that the payoff of a k-player is approximately fk = (1/n) a aki, while the total payoff of the whole population is F = (1/n)2 Ee l at7. Strategy k performs better than average when fk > F, which is indeed our general condition for large mutation rates (5.2). Since the system is almost neutral due to high mutation, we hardly need to assume anything about the dynamics. Note that u —) 1 implies a stronger mutation rate than µ oo, since the latter corresponds to any fixed mutation probability u in the N cc limit. The situation is more complex in the low mutation rate limit for arbitrary strength EFTA00748973

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 107 of selection. If the mutation rate is sufficiently small we can assume that there are at most two strategies present in the system at any given time [35]. Then we can use the fixation probabilities, or their large N asymptotic values [5, 155], and describe the system effectively as a Markov process on n homogeneous strategy states. This description, however, can lead to very different conditions for arbitrary selection and for weak selection. Note also that if two strategies j and k tend to coexist, all < aka and aft > akk, the time spent in the mixed strategy state is exponentially large in N 15]. Hence in this case, the effective Markov process description is only valid for extremely small mutation probabilities u « cu e, where A is a constant. 5.4.2 More general mutation rates Throughout this paper we have considered uniform mutations: each strategy mutates with the same probability u to a random strategy. In this section we extend our method to a more general class of mutation rates. For uniform mutation rates strategies have equal abundances in the absence of selection, and we have studied the effect of selection on this uniform distribution. Conversely, for non-uniform mutation rates strategies typically have different abundances already in the absence of selection. It can be still of interest to study whether selection increases or decreases these neutral abundances. In principle the pert ttr- bation theory presented in this paper can be repeated for general mutation probabilities, the discussion however becomes unwieldy. Here we present an easy generalization to a specific class of mutation rates. Imagine that each player mutates with probability u, but instead of uniformly adopting a new strat- egy, it adopts strategy j with probability pi > 0. We can approximate these probabilities (up to arbitrary precision) by rational numbers pi = mi/M, with Iv! = Ei m1, and all raj 1. Then instead of our n-strategy game, we consider an Al-strategy game, where EFTA00748974

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 108 each original strategy j is represented naj times. Instead of the n x rt payoff matrix, it is straightforward to construct the M x M payoff matrix, with which all our formulas (5.1), (5.2) or (5.3) automatically apply. 5.4.3 Alternative processes Although we have focused on the Moran model in this paper, the results are almost identical for the Wright-Fisher (W-F) process and for the Pairwise Comparison process. In the W-F model, each player of a new (non-overlapping) generation chooses a parent from the previous generation with probability (abbreviated as w.p.) proportional to the parent's payoff. The offspring inherits the parent's strategy w.p. 1 —u, or adopts a random strategy w.p. The expected number of offspring of a k-player in the next generation due to selection is 'Ok = N fkl F, in a given state. In the weak selection limit 6 —) 0 it becomes wk = 1 + 6[(Ax)k - xTAx]. (5.41) This is the same as the analog expression (5.5) for the Moran process, apart from the extra N factor. That N factor is due to the definition of time: time is measured in single player update steps in the Moran model, while in generations in the W-F model. For the neutral correlations, the only difference between the two models in the large N limit is that in the W-F model both linages can have mutations in each step. Hence all the neutral correlations .92 and 53 are the same as in the Moran model of appendix 5.5, provided we use µ = 2Nu. Consequently, (Aar ),5 becomes N times larger than for the Moran process (5.19), and 2Nu. Taking into account mutations as well, the expected total change of frequency in one EFTA00748975

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 109 generation is g-1 A 4 aat =ark A g ° (1 11) + u 1 — xk (5.42) similarly to (5.10). Hence the average frequency of k-players in the stationary state is 1 1 (xthrs — n + (48,x771).s (5.43) which is identical to (5.11) apart from an extra N factor. Since we also have an extra N factor in (Axns for the W-F process, these factors cancel out, and we obtain the same stationary density (5.20) as for the Moran process but with 2Nu instead of Nu (similarly to [4]). This also implies that the condition for greater abundance (5.3) becomes Lk +2ArteRk > 0. Conversely, the results are identical for the Moran and the Pairwise Comparison process. In this latter model we pick randomly a pair of players, say a type j and a type k. The j-player then adopts strategy k w.p. .F(fj — fk), otherwise the k-player adopts strategy j. Here .F(y) = 11 + St' is the Fermi function, and the fitnesses are defined as f = Ax. The above comparison of the pair of players takes place w.p. 1 — u. Instead, w.p. u one of them adopts a random strategy. Let us calculate directly the change of the frequency of k-players due to selection Axr1 in state X. The number of k-players changes if we pick a k-player and aj# k player, which happens w.p. 2242j. Then the frequency p c increases by 1/N w.p. — fk), and decreases by 1/N w.p. F(fk — fj). This leads to Arld = 2x Cj [F(h — l(fic — h)] which, in the leading order of small 6, becomes I 64 62k Ac = mi„ Exot - = rr uk - E xis jOk (5.44) (5.45) EFTA00748976

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 110 With the above definition of fitness we arrive at the same expression we obtained for the Moran process (5.6) and (5.7). Since without selection this model is equivalent to the Moran model, all neutral correlations s2 and 53 are also the same. Mutations in this model have the same effect as in the Moran model (5.10). Consequently all results we obtained for the Moran model are valid for the Pairwise Comparison process as well. 5.5 Discussion We have studied evolutionary game dynamics in well-mixed populations with n strate- gies. We derive simple linear conditions which hold for the limit of weak selection but for any mutation rate. These conditions specify whether a strategy is more or less abundant than 1/n in the mutation-selection equilibrium. In the absence of selection, the equilibrium abundance of each strategy is 1/n. An abundance greater than 1/n means that selection favors this strategy. An abundance less than 1/n means that selection opposes this strategy. We find that selection favors strategy k if Lk + NuHk 7 0, where Lk and Ilk are linear functions of the payoff values given by eqs (1) and (2). The population size is given by N and the mutation probability by u. Furthermore, if Lk + Artilik > L1 Nilifj then the equilibrium abundance of strategy k is greater than that of strategy j. In this case, selection favors strategy k over j. The traditional approach to study deterministic game dynamics in large populations is based on the replicator equation [55], which describes selection dynamics of the average frequencies of strategies. (Note the formal similarity between (5.7) and the replicator equa- tion). This method, however, neglects fluctuations around the averages. In this paper we have taken into account stochastic fluctuations, and derived exact results in the limit of weak selection. We find the average frequencies of strategies in the stationary state, and EFTA00748977

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 111 conditions for a strategy to be more abundant than another strategy. Our conditions are valid for arbitrary values of the mutation rates. For small mutation rates these conditions describe which strategy has higher fixation probability [110]. Throughout the paper we have considered large population size, N, in order to sim- plify the presentation. But in principle all calculations can be performed for any given pop- ulation size N and mutation probability u (see for example [4]). The mutation probability is a parameter between 0 and 1. In a social context, mutation can also mean `exploration': people explore the strategy space by experimenting with new strategies [153]. A high muta- tion probability seems to be appropriate for social evolutionary dynamics. Our conditions can be applied for the initial analysis of any evolutionary game that is specified by an n x n payoff matrix. Appendix. Probabilities s2 and s3 This section is valid for any number n > 1 of strategies. We calculate the probabilities 82 and 53 in the neutral (6 = 0) stationary state. First consider the simpler s2, that is the probability that two randomly chosen players have the same strategy. We shall use the Moran model and apply coalescent ideas [71, 72, 73, 164, 48, 4]. Coalescence means that different family lines collide in the past. A key fact behind this idea is that there is always a common ancestor of multiple individuals in finite populations. In the absence of mutations, any two players have the same strategy in the stationary state, because they both inherit their strategy from their common ancestor. In the presence of mutations, two players may have different strategies due to mutations after the branching of their ancestral lineage. Therefore, tracing the lineage of two players backward in time and finding the most recent common ancestor, from which two family lines branch, enable us to estimate the similarity EFTA00748978

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 112 of two players in strategies. Consider two different individuals and let us trace their lineages backward in time. In the neutral Moran process, two lineages coalesce in an elementary step of update (i.e. two players share the same parent) with probability 2/N2. Here and thereafter we assume that the population size is large, hence we can use a continuous time description, where the resealed time is T = t/(N2/2). In the resealed time, the trajectories of two players coalesce at rate 1. Following the trajectory of an individual back in time, we see that mutations happen at rate µ/2 = Nu/2 to each trajectory. The coalescence time r2 is described by the density function .f2(T2) = 8-72 . (5.46) Immediately after the coalescence of two players we have two players of the same strategy. What is the probability 52(r) that after a fixed time r they have again the same strategy? With probability (abbreviated as w.p.) cTM' none of them mutated, so they still have the same strategy. Otherwise at least one of them mutated, hence they have the same strategy w.p. 1/n. The sum of these two probabilities gives 1 — e- PT 82(r) = e- Pr + (5.47) Now we obtain the stationary probability s2 by integrating this expression with the coalescent time density of (5.46) as 00 n + 82 = J sz(r)Mildr — n(1 + µ) (5.48) Next we calculate the probability 53 that three randomly chosen players have the same strategy. Any two trajectories of three players coalesce at rate 1, hence there is a coalescence at rate 3. The coalescence of two out of the three trajectories then happens at EFTA00748979

Chapter 5: Mutation-selection equilibrium in games with multiple strategies 113 time Ty, described by the density function f3(73) = 3e 37. (5.49) The remaining two trajectories then coalesce at time Ty earlier, with density function (5.46). Before the first coalescence at time 73 backward, the two players have the same strategy w.p. s2, and of course they are different w.p. 1— s2, where s2 is given by (5.48). Hence just after this coalescence event we have either three identical players w.p. s2, or two identical and one different player otherwise. Now we shall see what happens in these two scenarios. If we have three identical players then they are also identical after time T w.p. s3(r) = 7 [I + 3(n — 1)e - s". + (rt — 1)(n — . (5.50) To derive this expression note that w.p. a l in none of the players have mutated, hence they have the same strategy. Then w.p. 3(1 — fr)e- in one of them has mutated, hence they are the same w.p. 1/n. Otherwise at least two of them mutated hence they are the same w.p. 1/n2. By collecting these terms one obtains (5.50). Similarly, if after the first coalescence only two players share the same strategy and one has a different strategy, the probability of all three having the same strategy after time TiS sr (7) = n- 2 [I. (n - - (n - 2)e- • (5.51) Now we can simply obtain s3 by first integrating over the coalescent time distribution (5.49) for the two different initial conditions, and then weighting them with the probabilities of the initial conditions, namely n2(1 + 14(2 + IL) 00 00 sr (o h (T)ch. _ (n + (2n + ii) (5.52) s3 = s2 s;(0/3(T)d7 + (I - 52) f EFTA00748980

Chapter 6 Mutation-selection equilibrium in games with mixed strategies 6.1 Introduction Evolutionary game dynamics is the study of frequency dependent selection (May- nard Smith & Price 1973, Maynard Smith 1982, Hofbauer & Sigmund 1988, Weibull 1995, Samuelson 1997, Cressman 2003). The fitness of individuals is not constant but depends on the composition of the population. Constant selection can be seen as adaptation on a constant fitness landscape, but for frequency dependent selection the fitness landscape changes as the population moves over it (Nowak & Sigmund 2004). The classical approach to evolutionary game dynamics is based on the replicator equation (Taylor Sc Jonker 1978, Hofbauer et at 1979, Zeeman 1980, Hofbauer & Sigmund 1988, 1998). The population is well-mixed and infinitely large. Any two individuals are equally likely to interact. The fitness of individuals is given by the expected payoff from all interactions. The dynamics are described by deterministic differential equations. 114 EFTA00748981

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 115 Evolutionary game theory represent the foundation for a mathematical approach to evolution. Evolutionary games occur whenever the reproductive success of individuals depends on interaction with other individuals, which is almost always the case. Therefore, evolutionary game theory permeates every area of biology including viral and bacterial evolution (Turner Sc Chao 1999, Kerr et al 2002), host parasite interactions (Anderson & May 1991, Nowak & May 1994), the evolution of metabolic pathways (Pfeiffer et al 2001), theoretical approaches to immunology (Nowak et al 1991, 1995), and the study of animal and human behavior (Parker 1974, Enquist & Leimar 1983, McNamara & Houston 1986, Milinski 1987, Fudenberg & Tirole 1991, Binmore 1994, Hammerstein Sc Selten 1994, Ohtsuki & Iwasa 2004, Nowak St Sigmund 2005). Understanding the evolution of animal communication and human language requires evolutionary game theory (Nowak & Krakauer 1999, Nowak et al 2002). The Lotka-Volterra equation, which is a fundamental concept in ecology describing the interaction of species in an ecosystem, is equivalent to the replicator equation of evolutionary game dynamics (Hofbauer Sc Sigmund 1998). Typically a game is formulated in terms of pure strategies, which can be stochastic or deterministic. A payoff matrix describes the outcome of an interaction between any two pure strategies. Sometimes these pure strategies are the only options available to the players. But in other situations it could be natural that players have the possibility to use 'mixed strategies'. A mixed strategy is a vector whose entries specify the probability for using each one of the pure strategies. A game with just pure strategies need not have a Nash equilibrium. But a game with pure and mixed strategies always has a Nash equilib- rium (Nash, 1950). Mixed strategies allow a certain kind of randomization which could be advantageous in certain games (Sklansky 2005). Consider a game with n pure strategies. The payoff values are given by the n x rt payoff matrix A = (%). This means that an individual using pure strategy i receives payoff EFTA00748982

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 116 au when interacting with an individual that uses pure strategy j. Let us now consider mixed strategies. A player can choose to play pure strategy i with probability pi. A mixed strategy is thus given by a stochastic vector p = (p1,... ,p„) with 0 ≤ < 1 and pi + + = 1. We denote the set of all such mixed strategies by Sn; this is a simplex in li.n. The unit vectors ei correspond to the pure strategies. The payoff of a mixed strategy p against a mixed strategy q is given by the function A(p, = pAqT. We focus on stochastic evolutionary dynamics in well-mixed populations of finite size (Schaffer 1988, Kandori et al 1993, Kandori & Rob 1995, Schreiber 2001, Nowak et al 2004, Taylor et al 2004, Wild and Taylor 2004, Traulsen et al 2005, Antal & Scheuring 2006, Imhof & Nowak 2006, Lessard & Ladret 2007). Evolutionary updating occurs according to the frequency dependent Moran process (Nowak et al, 2004; Taylor et al, 2004) or the frequency dependent Wright-Fisher process (Imhof & Nowak, 2006). Reproduction is proportional to fitness and subject to a mutation rate u. With probability 1 — u the offspring inherits the strategy of the parent. With probability u, the offspring chooses one of the mixed strategies uniformly at random. The rate at which mutations occur in the population is µ = Nu. A state of our system describes the strategy of each individual. Our state space is SZ. We look at the stationary distribution of the mutation-selection process and ask what are the average stationary frequencies (abundances) of each strategy (Antal et a 2009b, Antal et al 2009c, Tarnita et al 2009a, Tarnita et a 2009b). Then, we ask which strategies are favored, on average, by selection. We study the case of weak selection. For the frequency dependent Moran process, the effective payoff of an individual is given by f = 1+ 8. payoff. Here cS determines the intensity of selection. Weak selection means 8 -. 0. lb obtain results in the limit of weak selection, we use a perturbation theory method also employed in Antal et al 2009b, Antal et al 2009c and Tarnita et a 2009a. For the game dealing only with the it pure strategies in a finite well-mixed population, EFTA00748983

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 117 Antal et al 2009c obtained the following result. In the limit of weak selection, all strategies have approximately the same abundance, 1/n, in the stationary distribution of the mutation- selection process. There are only minor deviations from this uniform distribution. One can say that selection favors a strategy if its abundance exceeds 1/n. Selection opposes a strategy if its abundance is less than 1/n. It has been show that for low mutation probability 1/N), selection favors strategy k if 1 r n , Lk = — n L i(akk + aki — aik — au) > 0 1=1 For high mutation probability (u» 1/N), selection favors strategy k if (6.1) 1 n n Hk E E(a kj — NJ) > 0 (6.2) i=1 j=1 For arbitrary mutation probability, u, the general expression for selection to favor strategy kis Lk + µHk > 0 (6.3) where µ = Nu is the rate of mutation. Moreover, strategy k is more abundant than strategy j if and only if Lk + µHk > Lj + µHj (6.4) Finally, the abundance of strategy k is: 1 + IiHk = -n (1 + 0/(1 u) (1+ Lk 11)(2 + A) (6.5) All these results hold for large, but finite population size, N. They are shown in Antal et al 2009c. In this paper we analyze the same questions but for games with mixed strategies. By analogy with Antal et al. 2009c, we use global mutation rates. Hence, if a mutation occurs, then a mixed strategy is chosen at random from a uniform distribution over the EFTA00748984

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 118 simplex 5,,. For a mixed strategy p = (p1,...,p„) with 0 ≤ ≤ 1 and pi + + p„ = 1, let i p be the probability density function of a player using strategy p. Thus, for any set of strategies B C S„, the stationary frequency (abundance) of individuals that have strategies in B is fE i pdp. In the game of n pure strategies, one determines which strategy is favored by comparing its abundance to the average, 1/n. In the game with mixed strategies, the equivalent condition for a strategy to be favored is that its abundance (density) is greater than the mean, ip > 1. We establish the following results. For low mutation (ti GG 1/N), strategy p is favored by selection if and only if 4, = [A(p, p) + A(p, — A(q, p) — A(q, q)] dq > 0 (6.6) where is. dq = .f l ---q4-2 dq„_1...dq2dgi. Note that condition (6.6) gives a quadratic hypersurface in p. For high mutation (ti >> 1/N), the condition for strategy p to be favored by selection is HP = [A(p, — A(r, q)] dqdr > 0 (6.7) S. S. Note that (6.7) gives a hyperplane in p. For any mutation probability u, strategy p is favored by selection if and only if Lp µlip > 0 (6.8) where µ = Nu is the mutation rate. Moreover, strategy p is favored over strategy q if and only if Lp + µHp > L, +AC; (6.9) Finally, the abundance (density) of strategy p is: Lp + p = 1 + (SN (1 11)(1+ o)(2 + p.) (6.10) EFTA00748985

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 119 All these results hold for large, but finite population size, 1 GG N <G 1/u. They allow a characterization of games with mixed strategies, in the limit of weak selection and for global mutation. To gain some qualitative understanding of our results, let us first discuss the con- ditions for low and high mutation. When the mutation is low, all players use the same strategy, until a mutant strategy appears. This mutant strategy either takes over or dies out before any new mutant appears. Thus, for low mutation, only two strategies are in- volved in a takeover at a time. This explains why the low mutation condition is an average over all pairwise comparisons, A(p, + A(p, — A(q, — A(q, q). Conversely, for high mutation rates, the densities of all strategies are close to 1 all the time. Hence, the payoff of strategy p is fs. A(p, q)dq. Strategy p is favored if its payoff is greater than the average payoff of the population, which is fs. fs A (r, q)drdq. This difference is equivalent to (6.7). Note that the condition for high mutation rate holds for any intensity of selection, while the other conditions require weak selection. The rest of the paper is structured as follows. In Section 2 we derive the general conditions for strategy selection for any mutation rates. Games with two pure strategies are analyzed in Section 3, and the Hawk-Dove game is considered as an example. In section 5, we give a relaxed Prisoner's Dilemma as an example of a mixed game with 3 strategies. In Section 5 we present a few results for games with 71 pure strategies. Our findings are discussed in Section 6. 6.2 Mixed games with 2 strategies We consider a well-mixed population of N individuals. Each of them plays a mixed strategy, based on n pure strategies. The payoffs of the n pure strategies are given by the EFTA00748986

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 120 n x rt matrix A = (%). The payoff of a mixed strategy p = (ph ,p„) C Sn playing another mixed strategy q = C 5„ is given by the function A(p, q) = pAqr = E %Aga (6.11) id First, we discuss the n = 2 case and then turn to the general n case, which is completely analogous. When n = 2, a mixed strategy is given by p = (p,1 — p) E S2 where p is the probability to play strategy 1. The simplex 52 is a line segment of length 1. The left end, corresponds to p = 0 which is the pure strategy 2 and the right end corresponds to p = 1 which is the pure strategy 1. We partition the [0,1] interval into segments of length 1/m, as shown in Fig. 6.1, and allow only m + 1 types of mixed strategies. This means that strategy k = [klm,(m — k)/m], plays the pure strategy 1 with probability klm, and pure strategy 2 with probability (m — k)/m. We are interested in the stationary abundance of these strategies. Now, we have turned our continuous problem into a discrete one with m + 1 pure strategies, where we can use (6.1) and (6.2) to write 1 ntia Lk = m+ A(k,k) + floc)) - A(i,k) - A0,0 i=0 m m Hk = 1 > Aoc,n_ A(i,j) (nt + 1)2 1=0 5=0 and use (6.5) to obtain the frequency of strategy k. Taking the limit m —• co, the sums in (6.5) converge to the integrals (6.12) 4=j [A (p, p) + A (p, q) — A(q, p) — A(q, q)1 dg h hlP = 1 /1 [A(p,q) - A(q, r)1 dgdr o o (6.13) with p = j/m, and we obtain the abundance (6.10). Thus, the condition that the abundance of p is greater than 1 is equivalent to (6.8), as claimed. EFTA00748987

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 121 1/m (1.0) (0,1) (1-1/m, Wm) OSIIm Fig. 6.1: Partition of the interval [0,1] into segments of length 1/m. For general n, completely analogously to the n = 2 case, we first partition each coor- dinate of the simplex S„ into m equal parts, and use the corresponding discrete strategies. In Fig. 6.2, we show a partition of the simplex S3 by triangles. We can use the the pure strategy formulas (6.1), (6.2), (6.5) for this problem, and then take the m -. oo limit to obtain (6.6), (6.7), and (6.10). Hence we conclude as before that the condition for strategy p to be favored by selection is indeed (6.8). (0,0,1) • AVA OO♦ AVAVAVA ♦VO♦VAVA AT 11/m AVAVAVAVAVAVA AVAVAVAVAVAVAVA AVAVAVAVAVAVAVAVA AVAVAVAVAVAVAVAVAVA avAVAVAVAV•vAvAVAVA AVAVAVAV•V•VAVAVAVAVAVA (1.0,0) (0,1,0) Fig. 6.2: Covering of the simplex S3 by triangles of side length 1/m. EFTA00748988

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 122 6.3 Mixed games with two pure strategies Consider the game between two strategies A and B. The payoff matrix is given by A B Ara b) B c d In addition to the two pure strategies, we have mixed strategies p = (p,1—p) where p is the probability to play strategy A and 1 — p is the probability to play strategy B. The payoff of strategy p against strategy q is given by (6.11): (6.14) A(p, q) = apg + bp(1— g) + c(1 — p)q + d(1 — p)(1 — (6.15) Then condition (6.6) that strategy p is favored by selection, in the limit of low mutation becomes 1 Lp = — — b — c + d)(p + + 2(b — d)] dg = p2(a — b — c+ d)+2p(b — d)— al (a +2b — c — 2d) > 0 For p = (0,1), which is the pure strategy B, we obtain: (6.16) a+2b<c+2d (6.17) This condition is equivalent to PA C 1/N, where PA is the fixation probability of an A mutant in a population of B individuals (Nowak et al 2004a, Ohtsuki et al 2007, Imhof et al 2006, Lessard and Ladret 2007). The above condition can thus be interpreted as follows: in a 2 x 2 game with mixed strategies, pure strategy B is favored if pure strategy A is not an advantageous mutant in a pure B population, pA<11N. By symmetry, for p = (1,0), which is the pure strategy A, (6.16) becomes 2a + b > 2c + d. This condition is equivalent to pa < 1/N. Thus, in a 2 x 2 game with mixed strategies, A is favored if B is not an advantageous mutant, pEr C 1/N. EFTA00748989

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 123 Now we can ask when strategy A is better than strategy B. For this we need to compare LA to La; we conclude that A is favored over B if and only if a + b > c+ d. This is the usual risk-dominance condition of strategy A over strategy B (Kandori et al 1993, Nowak et al 2006, Antal et al 2009a). Thus, adding the mixed strategies does not change the ranking of the two pure strategies. If a + b > c + d then A is more abundant than B in the stationary distribution of the mutation-selection process with or without mixed strategies. This result will be generalized for games with n pure strategies in Lemma 2. Next we analyze the case of high mutation. Condition (6.7) becomes flp = 4 —1(2p — 1)(a + b — c — d)> 0 (6.18) As before, the condition that selection favors p = (1,0), which is the pure strategy A is a+b>c+d (6.19) This is the usual condition for risk dominance of strategy A over strategy B. By symmetry, the condition that pure strategy B is favored by selection is a + b < c + d, which is the usual risk-dominance condition of B over A. Note that for high mutation, adding mixed strategies does not change the selection conditions for the pure strategies. This result will be generalized for games with 71 pure strategies in Lemma 3. Moreover, for high mutation rate, if a+b > c+d, then all strategies with p > 1/2 are favored. Thus, if A is risk dominant over B, all mixed strategies that play A with higher probability than B are favored. By synunetry, if B is risk-dominant over A, i.e. a + b < c+ d, then strategies which are more likely to play B (i.e. p < 1/2) are favored. In general, for any mutation rate it, the condition for strategy p = (p,1 — p) to be favored by selection can be deduced from (6.8) to be p2(a—b—c+d)+24—d+51(a+b—c—d)]i.(a+2b—c-2d)-51(a+b—c—d)> 0 (6.20) EFTA00748990

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 124 (s) Best Worst (b) Best 0 Worst Worst (e) Best • • PA • • PA Worst Worst (b) Best Worst (c) Best Worst (0) Best Fig. 6.3: The first column corresponds to the case a + d < b + c. The parabola is concave. The only possibilities are: (a) the tip of the parabola is to the left of the interval [0,1]; (b) the tip is inside but only the right root is inside as well; (c) the tip and both roots are inside; (d) the tip and the left root are inside; (e) the tip is to the right of the interval. The green segment shows which strategies are favored. The green dot marks the best strategy. The second column corresponds to the case a+d> b + c. The parabola is convex. This condition describes a parabola. The mixed strategy corresponding to the tip of the parabola is /5 = (p, - 23) where b—d+t(a+b—c—d) p a—b—c+d (6.21) We are interested in the part of this parabola supported by the interval [0,1]. Based on where p is situated relative to the interval [0, 1] as well as on the sign of the coefficient of EFTA00748991

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 125 p2 in (6.20), the relevant part of the parabola can have several shapes, as shown in Fig 6.3. 6.3.1 A resealed payoff matrix For a non-degenerate (a d) payoff matrix (6.14), a > d can always be achieved by renaming the strategies. Moreover, under weak selection adding an overall constant to all elements or multiplying all elements by the same positive number does not affect the dynamics; it only changes the intensity of selection 6. Hence we can define an equivalent payoff matrix (see also Antal et al 2009b) with only two parameters b — d c — a c, = s — a — d a — d (6.22) (6.23) This means that each specific game given by numerical values in (6.14) corresponds to a point in the (a, #) plane. A class of games then corresponds to a particular region in this plane. In Figure 6.3.1 we show a few common games in the (a,#) plane. For example all Prisoner's Dilemma games belong to the second quarter plane a < 0,0 > 0. In the Hawk Dove game we first have to flip the Hawk and the Dove strategies to obtain a matrix with a > d. Then the corresponding region is 0 < a < 1 and # > 0. Moreover, the simplified Hawk-Dove game (6.26), which is the subject of the next subsection, is given by a = bit and $ = 1 — bk. Hence, in the (a,#) plane, the simplified Hawk-Dove game is given by the line segment /3 = 1 — a, with 0 < a < 1. Now we present the same analysis as before for mixed strategies in 2 x 2 games using the simplified payoff matrix. For any finite mutation rate, µ, we have three different regions EFTA00748992

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 126 Prisoner's dilemma Snraw drift .0( Hawk-Dgye Stag hunt Harmony 1 Fig. 6.4: Schematic phase diagram in the (a,0) plane. The four regions bounded by black lines correspond to four different games. The dashed line corresponds to the simplified Hawk-Dove game (6.26). in the (a, 0) parameter space, as depicted in Fig. 6.5. The optimal strategy is pure A, pure B, for 0 < a and 0 < a p+4 for 0 > a and 0 > ft mixed A and B, for 0 < al=+4 and Q > p4 In the mixed case the optimal value of p is given by a 4_ ct— 13 P = oi-F0 4 a+0 (6.24) (6.25) In the small mutation rate limitµ -. 0, the mixed phase extends to the quarter-plane a > 0, > 0. For large mutation ratesµ —• co, however, the mixed phase disappears. 6.3.2 Example: Hawks and Doves As an example, we consider the Hawk-Dove game (Maynard-Smith 1982, Houston Mcishunara 1988, Houston Sc McNamara 1991, IvIesterton-Gibbons 1994, Killingback EFTA00748993

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 127 mixed pure B (a) mixed a.1 pure B (b) (c) Fig. 6.5: This phase diagram shows the type of the most abundant strategy in the (a,)3) plane for some finite mutation rate µ. It can be pure A, pure B, or a mixed stochastic strategy. The angle of the boundary of the mixed region opens up symmetrically to 90 degree for µ 0, and closes symmetrically to the line /3 = a for µ —) co. In this last case, the mixed region disappears. Doebeli 1996, Nakamaru & Sasaki 2003), which is given by the payoff matrix H D H b / D 0 The two strategies are hawk (H) and dove (D). While hawks escalate fights, doves retreat when the opponent escalates. The benefit of winning the fight is b. The cost of injury is c. We have 0 < b < c. If two hawks meet, then the fight will escalate. One hawk wins, while the other is injured. Since both hawks are equally strong, the probability of winning or losing is 1/2. Hence, the expected payoff for each of them is (b - c)/2. If a hawk meets a dove, the hawk wins and receives payoff b, while the dove retreats and receives payoff 0. If two doves meet, there is no injury, but one of them wins eventually. The expected payoff is b/2. Since b < c, neither strategy is a Nash equilibrium. If everyone else plays hawk, then it is better to play dove and vice versa. Hence, hawks and doves can coexist. At the stable equilibrium, the frequency of hawks is given by b/c. Next we consider mixed strategies that play hawk with probability p and dove with probability 1— p. The strategy space is given by the interval [0,1]. The pure strategies are (6.26) EFTA00748994

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 128 p = 0 (D) and p = 1 (H). The evolutionarily stable strategy (ESS) is given by the mixed strategy that plays hawk with probability ps. b/c. No other strategy can invade this ESS under deterministic evolutionary dynamics. We can now study the Hawk-Dove game with the methods developed in the previous section. Using (6.20), we can write the condition that the mixed strategy p = (p,1 — p) is favored —p2c p [2b (1) — ID] — (13 — — 12 (13 2) > ° (6.27) The first observation is that the ESS strategy p* = (12%1 — e) is always favored. We can see this by substituting p. into (6.27) and noting that it is always positive. However, pt is not always the best strategy. In (6.27) the leading coefficient is —c < 0; hence the parabola is concave, as in Fig. 6.3 (a.e). Thus, the best strategy is either the tip of the parabola or one of the two pure strategies. The tip of the parabola is given by = p* + 2 ) — 4 (6.28) For 0 we have p = b/c = p. which always belongs to the interval [0,1]. Forµ > 0 we can compare the tip of the parabola to the ESS strategy. We conclude that 13 > p* if and only if b/c > 1/2, while 13 < pt if and only if b/c < 1/2. Note that f. = pt if and only if either µ 0 (which is the low mutation case) or b/c = 1/2. Thus if the ESS leans more towards one pure strategy, increasing the mutation rate pushes the best strategy even closer towards that pure strategy. For low mutation, 0, the parabola looks like Fig. 6.3 (b), (c) or (d). The favored strategies always form a neighborhood around p*. If b/c < 1/3 then this neighborhood includes pure dove, p = 0. If 1/3 < b/c < 2/3 then this neighborhood includes neither pure dove nor pure hawk. If 2/3 < b/c then this neighborhood includes pure hawk, p = 1. The best strategy is always e. EFTA00748995

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 129 For high mutation, the condition for strategy p = (p,1 — p) to be favored is (2p — 1)(2b — c) > 0. Therefore, If b/c C 1/2 then the best strategy is pure dove, p = 0. If 1/2 < bit then the best strategy is pure hawk, p = 1. The mixed ESS, p*, is always favored but is never the best strategy. When mutation is neither low nor high, we have a mixture of the above to cases. All situations of Fig. 6.3 (a-e) are possible.The mixed ESS, p*, is always favored, but is never the best strategy. The tip of the parabola, 13, is given by (6.28) and is different from ps. (i) if b/c < µ/(2µ + 4), then 13 < 0, which means pure dove, p = 0, is the best strategy. (ii) if µ/(2µ + 4) < b/c < + 4)(2µ + 4), then 0 < p < 1. In this case, 13, is the best strategy and the favored strategies form a neighborhood around it. There are three cases: (i') either pure dove or (ii') pure hawk or (iii') neither of them are part of this neighborhood. (iii) if b/c > (µ + 4)/(2µ + 4), then ;I > 1, which means pure hawk, p = 1, is the best strategy. Note that lower b/c values favor doves, while higher b/c values favor hawks. This makes sense, because b/c is the ratio of the benefit gained from winning the fight over the cost of possible injury. If this ratio is small, then it is better not to escalate fights (which means to play dove). It is interesting to note that the mixed ESS of classical game theory, ps, is always one of the strategies that is favored by selection, but is never the best strategy for any positive mutation rateµ > 0. These results agree with the general picture of Section 6.3.1. Note that (after flipping the H and D strategies), the simplified Hawk-Dove game (6.26) corresponds to the segment $ = 1— a, with 0 < a C 1 on the plane of Fig. 6.4. Then the region where mixed strategies are favored is described by (6.24), and it can be seen on Figure G.S. EFTA00748996

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 130 6.4 A mixed 3-game: Cooperators, Defectors, Loners Consider a game with three pure strategies whose interactions are given by the fol- lowing matrix: C D L C b — c —c 0 ' A= D b 0 0 (6.29) L 0 0 0 / where b > c > 0. The game between cooperators and defectors is the usual simplified Prisoner's Dilemma. The third strategy is a loner strategy: loners do not play the game; hence, they pay no cost and receive no benefit. Let us first analyze these strategies using the result of Antal et al 2009c. Then the conditions for C, D and L respectively to be selected for are Lc = (13 — 3c) > 0 (6.30) LD = g > 0 (6.31) LL = 3(—b+c)> 0 (6.32) Clearly, loners L are never selected for; C is selected for iff b/c > 3 and D is always selected for. Moreover, C is favored over D if and only if Lc > LD which is equivalent to b/c > 5. Finally, C is favored over L iff b/c > 2. So there is a parameter region where C is worse than L. In the mixed strategies setup, the payoff of strategy p = (ph,p2,1 — — p2) against strategy q = (qi, q2, 1 - - q2) is A(p, q) = ptAq = bqi (pi + p2) - cpi (qi + Q2) (6.33) EFTA00748997

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 131 Using (6.6) we conclude that, in the limit of low mutation and weak selection, strategy p is favored if 4, 24 = —1 (b(-3 + 12/4 +O2 +4p1(-1 +3p2)) + c(3 -12g+42- 4pi (1 +3p2))) > 0 (6.34) Thus, the conditions for a pure C = (1, 0,0), pure D = (0, 1, 0) or pure L = (0,0,1) to win are: Lc = +4(5b — 130) > 0 (6.35) LD = a(b + 7e) > 0 (6.36) LL = 2+4(-3b + 3c) > 0 (6.37) One can then immediately deduce the low mutation conditions for each of these strategies to be favored in general, or to be favored over each other. Since b > c > 0, it is clear that i t < 0 always; so the Loner strategy is never selected for. Moreover, C is selected if and only if b/c > 13/5 = 2.6. Note that this condition is weaker than in the case of pure strategies, when C is selected if b/c > 3. Hence, adding mixed strategies helps the cooperators. Clearly, D is always selected. Finally we can also conclude that C is favored over D if and only if L0 > Li) which is equivalent to b/c > 5. Note that this condition is the same as in the case of pure strategies. Moreover, one can show that for b/c > 5, cooperation is the best strategy overall (see Fig. 6.7). As before, we find that L is never selected. However, one surprising result is that unlike in the pure case, in the mixed case L is never the worst strategy. The worst strategy is either a mixture between cooperative and loner behavior or pure cooperation. The mixture is given by (p, 0,1 - p) where p = (b + c)/6(b — c) (see Fig. 6.6, 6.7). Note that since p > 0, the loner strategy L will never be the worst strategy. However, p could be greater EFTA00748998

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 132 than 1 which implies that the worst strategy could be cooperation C. This happens when b/c < 7/5 = 1.4 (see Fig. 6.8). As in the pure analysis, C is worse than L for b/c < 2. One question is which of the two strategies C or L is predominant in the worst mixed strategy, i.e. we want to know when the probability p = (b + — c) to play C is greater than 1/2. This is precisely when b/c c 2 which is the condition for C to be the worst strategy in the pure case. Fig. 6.6: Defection is the best strategy. C is selected for. Mixed between C and L is the worst. pi is the probability to cooperate. p2 is the probability to defect. (0,0) is L. In red we have our surface and in blue the plane 0. The same analysis can be done for high mutation. In the pure case, using the results EFTA00748999

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 133 Fig. 6.7: Cooperation is the best strategy. in Antal et al 2009c we obtain the conditions: He = 9 (b — 4c) Ho = ti (13 + 2c) HL = i(-2b + (6.38) (6.39) (6.40) (6.41) Thus, we can conclude that in the limit of high mutation, L is never selected, D is always selected and C is selected only if b/c > 4. Moreover, we can conclude that C is never better than D. Finally, C is better than L unless b/c < 2. Next, we allow all mixed strategies. Then the high mutation condition for strategy p to be selected is P = —1 (c(2 — 6p1) + b(-2 + 3pi + 3p2)) > 0 6 (6.42) EFTA00749000

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 134 p1 0.0 1.0 Fig. 6.8: Cooperation is the worst strategy. In particular, C, D or L are selected if and only if: HC = (b - 44c) > 0 (6.43) AD = a(b+2e) >0 (6.44) EL, = 3+6(-2b+240> 0 (6.45) (6.46) Note that these conditions are the same as the ones in the pure analysis, up to a scaling by a constant. Hence, the conclusions are as before: D is always the best strategy; C can be selected for if b/c > 4; L is never selected for. C could be worse than L for b/c < 2. Note that in the high mutation case the worst strategy is either L or C (unlike the low mutation case). Finally one can use the general formula for any mutation rate to obtain a linear EFTA00749001

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 135 combination of these behaviors. 6.5 Mixed games with n pure strategies In this section we present a few results which characterize the general behavior of pure strategies. In an n x n game with only pure strategies, the condition that strategy k is favored is given by (6.1). Lemma 1. In the limit of weak selection and low mutation in an n x 71 game with mixed strategies, the condition that pure strategy ek is favored is Lot — (n+1)! [E ((n + 1)akk + (n + 1)4; — + 1)aik — du) — E au] > 0 (6.47) The proof is by induction. From this lemma, it is immediate that the comparison conditions Li > Li and Le, > ifej are equivalent. Hence, we can make the following statement. Lemma 2. In the limit of weak selection and low mutation, the relative ranking of pure strategies in a game with mixed strategies is the same as that in a game with just the pure strategies. Hence, adding mixed strategies does not change the relative ranking of the pure strategies. Proof. A direct proof for this statement is immediate. To find the difference Le, —Lei, one simply needs to integrate: S„A(ei,e0 + A(ei,q) — A(q, ei) — A(ej, ej) — A(ei, + A(q, ej) dq (6.48) We note that: A(ei,ei) = nu, 11(ei,(1) = Ek qkaik and A(q,ei) = Ek qkakil where tie = 1 — — All these functions are linear and hence easily integrable over the simplex Se,. For example, we have k qi = 1/(n + 1)!. K EFTA00749002

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 136 Lemma 3. In the limit of weak selection and high mutation the conditions He > 0 and He, > 0 are equivalent and they can be written as 1 1 n e,' Laid > 0 (6.49) The proof is again immediate by induction. Thus, in the limit of weak selection and high mutation, the condition for a pure strategy i to be favored in a mixed game is the same as in the pure game. Note that this lemma is stronger than Lemma 2. In the high mutation case, the conditions that the pure strategies are favored are exactly the same for both the mixed and the pure game. In the low mutation case, only the relative behavior of the pure strategies is the same between the two cases. The actual conditions for selection are different between the mixed game and the pure game. For any mutation, the condition for a strategy to be favored is simply a linear com- bination between the low mutation and high mutation behaviors. Hence, combining the results in the lenunas 2 and 3, we conclude that: in the limit of weak selection, for any mutation rate, the relative ranking of the pure strategies is not affected by introducing mixed strategies. 6.6 Conclusion We have presented a method to study games with mixed strategies in finite sized populations under stochastic evolutionary dynamics. We assume that individuals reproduce at a rate that is proportional to the payoff earned in the game. Reproduction is subject to mutation. We characterize the average abundance of each mixed strategy in the mutation- selection equilibrium. Strategies that are favored by selection are more abundant than average. Strategies that are opposed by selection are less abundant than average. If strategy A is more abundant than strategy B in the mutation-selection equilibrium, then we say that EFTA00749003

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 137 A is favored over B. Our results allow a simple and straightforward characterization of games with mixed strategies. The crucial condition for low mutation rate (6.6) is based on averaging over all pairwise comparisons. The crucial condition for high mutation rate (6.7) is based on evaluating the fitness of each strategy at the point where all strategies are equally abundant. Intriguingly, the condition for any mutation rate is simply a linear combination of the conditions for low and high mutation rates. We have no intuitive explanation why this condition is linear in the mutation rates. Although our results provide interesting new insights into evolutionary game dynam- ics, our approach has limitations. (i) We can only consider the case of weak selection. This means the fitness of an individual is 1+6•payoff where ö is small. One way to interpret weak selection is to say that the game under consideration provides only a small contribution to overall fitness. Another way to explain weak selection is the following: when choosing to update their strategies, players make random choices that are weakly affected by payoff; this means players do not really know what is going on. Both of these aspects are in fact very realistic and will apply in many situations. Hence weak selection is an important case to be studied. (ii) We consider only global mutation. A new mutant is picked at random from a uniform distribution of the strategy space, which is given by the simplex S.. Such a mutation model is often used in population genetics; it is called `house of cards'. The location of the mutant in strategy space does not depend on the parent. (iii) We calcu- late the average abundance of each mixed strategy in the stationary distribution of the mutation-selection process, but we do not in fact calculate the stationary distribution over the entire state space. Our stochastic process has state space Sff: for each of the N players we must specify which strategy (in SO is being used. Instead of calculating the stationary distribution over S., we calculate the average abundance of each mixed strategy. With this EFTA00749004

Chapter 6: Mutation-selection equilibrium in games with mixed strategies 138 method though, we are able to decide whether a strategy is favored or not by selection in the stationary state. EFTA00749005

Bibliography [1] Alos-Ferrer, C., 2003. Finite population dynamics and mixed equilibria. Int. Game Theory Review 5, 263-290. [2] Anderson, R.M., and May, R.M., 1991. Infectious Diseases of Humans. Oxford Uni- versity Press, Oxford, UK. [3] Antal, T., Nowak, M. A., Traulsen, A, 2009a. Strategy abundance in 2x2 games for arbitrary mutation rates. J. Theor. Biol. 257, 340-344. [4] Antal T, Ohtsuki H, Wakeley .J, Taylor PD, Nowak MA, 2009b. Evolutionary game dynamics in phenotype space. PNAS, to appear. [5] Antal, T. and Scheming, I., 2006. Fixation of strategies for an evolutionary game in finite populations. Bull. Math. Biol., 68, 1923-1944. [6] Antal, T., Traulsen A., Ohtsuki, H., Tarnita, C.E., Nowak, M.A., 2009c. Mutation- selection equilibrium in games with multiple strategies. J. Theor. Biol., to appear. Altmann, .J. and Maschler, M., 1995. Repeated Games with Incomplete Informa- tion. Cambridge: MIT press. Axelrod, R., Hamilton, W.D., 1981. The evolution of cooperation. Science 211, 1390- 1396. [7] [8] [9] Binmore, K., 1994. Game Theory and the Social Contract. MIT Press, Cambridge, MA. [10] Binniore, K. 2007. Playing for Real: A Text on Game Theory. Oxford University Press. [11] Boerlijst, M.C., Hogeweg, P., 1991. Spiral wave structures in pre-biotic evolution: hypercycles stable against parasites. Physica D 48, 17-28. [12] Bollobas B., 1995. Random Graphs. Academic Press, New York. [13] Bonne, I., Pawlowitsch, C., 2008. One-third rules with equality: second-order evolu- tionary stability conditions in finite populations. To be published in J. Theor. Biol. 139 EFTA00749006

Bibliography 140 [14] Bonhoeffer, S. and Nowak, M. A., 1995. Mutation and the evolution of parasite virulence. Proc. Royal Soc. Lond. B, 258, 133-140. [15] Boyd, R., Richerson, P.J., 2005. Solving the Puzzle of Human Cooperation. In: Levin- son, S. (Ed.), Evolution and Culture. MIT Press, Cambridge, MA, pp. 105132. [16] Bshary, R., Grater, A., Willener, A., Leimar, O., 2008. Pairs of cooperating cleaner fish provide better service quality than singletons. Nature 455, 964-967. [17] Colman AM, 1995. Game Theory and Its Applications in the Social and Biological Sciences. Butterworth-Heinemann, Oxford, UK, Boston, MA. [18] Comins, H.N., Hamilton, W.D., May, R.M., 1980. Evolutionarily stable dispersal strategies. J. Theor. Biol. 82, 205-230. [19] Cressman, It., 1992. The stability concept of evolutionary game theory. Lecture Notes in Biomathematics, 94. [20] Cressman It, 2003. Evolutionary Dynamics and Extensive Form Games. MIT Press, Cambridge, MA, London, UK. [21] Dieckmann, U., Law, R., Metz, J.A.J., (Eds.), 2000. The Geometry of Ecological In- teractions: Simplifying Spatial Complexity. Cambridge University Press, Cambridge, UK. [22] Doebeli, M., Knowlton, N., 1998. The evolution of interspecific mutualisms. P. Natl. Acad. Sci. U.S.A. 95, 8676-8680. [23] Durrett, R., 1988. Lecture Notes on Particle Systems and Percolation. Wadsworth & Brooks/Cole Advanced Books & Software, Stamford, CT. [24] Durrett It, Levin SA, 1994. Stochastic spatial models: a user's guide to ecological applications. Philos. T. Roy. Soc. B, 343, 329-350. [25] Ellison, G., 1993. Learning, local interaction, and coordination. Econometrica 61, 1047-1071. [26] Enquist, M., Leimar, O., 1983. Evolution of fighting behaviour: decision rules and assessment of relative strength. J. Theor. Biol. 102, 387-410. [27] Ewens WJ, 2004. Mathematical population genetics. Theoretical introduction, vol. 1. (Springer, New York). [28] Ferriere, R., Michod, R.E., 1996. The evolution of cooperation in spatially heteroge- neous populations. Ant Nat. 147, 692-717. EFTA00749007

Bibliography 141 [29] Ficici, S. and Pollack J., 2000. Effects of finite populations on evolutionary stable strategies. In D. Whitley, D. Goldberg, E. Cantu-Paz, L. Spector, I. Parmee, and H.-G. Beyer, editors, Proceedings GECCO, pages 927-934, Morgan-Kaufmann, San Francisco. [30] Ficici, S.G., Pollack, J.B., 2000. Effects of finite populations on evolutionary stable strategies. In: Whitley. D., Goldberg, D., Cantu-Paz, E., Spector, L., Parmee, I., Beyer, H.G., (Eds.), Proceedings of the 2000 Genetic and Evolutionary Computation Conference. Morgan-Kaufmann, San Francisco, CA, pp. 927-934. [31] Fisher RA, 1930. The Genetical Theory of Natural Selection. (Oxford: Clarendon Press). [32] Fogel, G., Andrews, P., Fogel, D., 1998. On the instability of evolutionary stable strategies in small populations. Ecol. Model. 109, 283-294. [33] Frank, S.A., 1998. Foundations of Social Evolution. Princeton University Press, Princeton, NJ. [34] Fu, F., Wang, L., Nowak, M.A., Hauert C., 2008. Evolutionary Dynamics on Graphs: Efficent Method for Weak Selection. To be published. [35] Fudenberg, D. and Imhof, L. A., 2006. Imitation processes with small mutations. J. Econ. Theor., 131, 251-262. [36] Fudenberg, D., Tirole, J., 1991. Game Theory. MIT Press, Cambridge, MA. [37] Gandon, S., Rousset, F., 1999. The evolution of stepping stone dispersal rates. Proc. R. Soc. B 266, 2507-2513. [38] Gintis, H. 2000. Game Theory Evolving. Princeton University Press: Princeton, USA. [39] Grafen, A., 1985. A geometric view of relatedness. Oxford Surv. Evol. Biol. 2, 28-89. [40] Grafen, A., 2006. Optimization of inclusive fitness. .J. Theor. Biol. 238, 541-563. [41] Hamilton WD, 1964. The genetical evolution of social behavior. J. Theor. Biol., 7, 1-16. [42] Hamilton WD, May RM, 1977. Dispersal in stable habitats. Nature, 269, 578-581. [43] Hammerstein, P., Selten, R., 1994. Game theory and evolutionary biology. In Hand- book of Game Theory with Economic Applications, R.J. Aumann Sc S. Hart (ed.). [44] Harsanyi, J. C., Selten, R. 1988. A General Theory of Equilibrium Selection in Games. MIT Press: Cambridge MA. EFTA00749008

Bibliography 142 [45] Hassell MP, Comins HN, May RM, 1994. Species coexistence and self-organizing spa- tial dynamics. Nature, 370, 290-292. [46] Hauert, Ch., De Monte, S., Hofbauer .J., and Sigmund, K., 2002. Volunteering as Red Queen Mechanism for Cooperation in Public Goods Game. Science 296, 1129-1132. [47] Hauert C, Doebeli M, 2004. Spatial structure often inhibits the evolution of coopera- tion in the snowdrift game. Nature, 428, 643-646. [48] Haubold, B. and Wiehe, T., 2006. Introduction to Computational Biology: An evo- lutionary approach. Birkhauser. [49] Helbing, D., Yu, W. 2008. Migration as a mechanism to promote cooperation. Ad- vances in Complex Systems 11 641 - 652 [50] Her; A.V.M., 1994. Collective phenomena in spatially extended evolutionary games. J. Theor. Biol. 169, 65-87. [51] Hofbauer, J., 1999. The spatially dominant equilibrium of a game. Ann. Oper. Res. 89, 233-251. [52] Hofbauer, J., Schuster, P., Sigmund, K., 1979. A note on evolutionary stable strategies and game dynamics. J. Theor. Biol. 81, 609-612. [53] Hofbauer, J., Sigmund, K., 1988. The Theory of Evolution and Dynamical Systems. Cambridge University Press, Cambridge, UK. [54] Hofbauer, J., Sigmund, K., 1990. Adaptive dynamics and evolutionary stability. Appl. Math. Lett. 3, 75-79. [55] Hofbauer J, Sigmund K, 1998. Evolutionary Games and Population Dynamics, Cam- bridge Univ. Press, Cambridge, UK. [56] Hofbauer, J., Sigmund, K., 2003. Evolutionary game dynamics. B. Am. Math. Soc. 40, 479-519. [57] Hofbauer, J., Schuster, P., Sigmund, K., 1979. A note on evolutionary stable strategies and game dynamics. J. Theor. Biol. 81, 609-612. [58] Houston, A.I., McNamara, J.I41., 1988. Fighting for food: a dynamic version of the Hawk-Dove game. Evolutinary Ecology, 2, 1, 51-64. [59] Houston, A.I., McNamara, J.M., 1991. Evolutionarily stable strategies in the repeated hawk-dove game. Behavioral Ecology, 2, 3, 219-227. [60] Houston, A.I., McNamara, J.M., 1999. Models of Adaptive Behaviour: An Approach Based on State. Cambridge University Press, Cambridge, UK. EFTA00749009

Bibliography 143 [61] Hutson, V., Vickers, G.T., 1992. Travelling waves and dominance of ESSs. .J. Math. Biol. 30, 457-471. [62] Hutson, V., Vickers, G.T., 2002. Backward and forward traveling waves in evolution- ary games. Methods Appl. Anal. 9, 159-176. 117] Imhof, L. A., Fudenberg, D., and Nowak, M. A., 2005. Evolutionary cycles of coop- eration and defection. PNAS, 102, 1079710800. [63] Imhof LA, Nowak MA, 2006. Evolutionary game dynamics in a Wright-Fisher process. J. Math. Biol 52, 667-681. [64] Jansen VA, van Baalen M, 2006. Altruism through beard chromodynkunics. Nature, 440, 663-666. [65] Kandori, M., Mailath, G. J., Rob, R., 1993. Learning, mutation, and long run equi- libria in games. Econometrica, 61, 29-56. [66] Kandori, M. and Rob, R., 1995. Evolution of equilibria in the long run: A general theory and applications. J. Econ. Theor., 65, 383-414. [67] Kareiva P, 1987. Habitat fragmentation and the stability of predator-prey interactions. Nature, 326, 388-390. [68] Kerr B, Riley MA, Feldman MW, Bohannan BJ, 2002. Local dispersal promotes biodiversity in a real-life game of rock-paper-scissors. Nature, 418, 171-174. [69] Killingback T, Doebeli M, 1996. Spatial evolutionary game theory: Hawks and Doves revisited. Proc. R. Soc. B, 263, 1135-1144. [70] Kingman, J.F.C., 1976. Coherent random-walks arising in some genetic models. Proc. R. Soc. Lond. Ser. A, 351, 19-31. [71] Kingman, J. F. C., 1982a. The coalescent. Stochastic Processes and Their Applica- tions, 13, 235-248. [72] Kingman, J. F. C., 1982b. On the genealogy of large populations. J. Appl. Probability, 19A, 27-43. [73] Kingman, J. F. C., 2000. Origins of the coalescent. 1974-1982. Genetics, 156(4), 1461-1463. [74] Lehmann, L., Keller. L., Sumpter, D. J. T., 2007. The evolution of helping and harm- ing on graphs: the return of inclusive fitness effect. J. Evol. Biol. 20, 2284-2295. [75] Lessard, S., Ladret, V., 2007. The probability of a single mutant in an exchangeable selection model. J. Math. Biol. 54, 721-744. EFTA00749010

Bibliography 144 [76] Levin SA, Paine RT, 1974. Disturbance, patch formation, and community structure. Proc. Natl. Acad. Sci. U.S.A., 71, 2744-2747. [77] Levins It, 1969. Some demographic and genetic consequences of environmental het- erogeneity for biological control. Bull. Entomol. Soc. Am., 15, 237-240. [78] Lieberman E, Hauert C, Nowak MA, 2005. Evolutionary dynamics on graphs. Nature, 433, 312-316. [79] Lindgren, K., Nordahl, M.G., 1994. Evolutionary dynamics of spatial games. Physics D 75, 292-309. [80] MacArthur RH, Wilson EO, 1967. The Theory of Island Biogeography, Princeton Univ. Press, Princeton. [81] May, R. M., 1973. Stability and Complexity in Model Ecosystems. Princeton Univ. Press. [82] May RM, 2006. Network structure and the biology of populations. Trends. Ecol. Evol., 21, 394-399. [83] May, R.M., Leonard, W., 1975. Nonlinear aspects of competition between three species. SIAM J. Appl. Math. 29, 243-252. [84] May, R. M. and Nowak, M. A., 1995. Coinfection and the evolution of parasite virulence. Proc. Royal Soc. Lond. B, 261, 209-215. [85] Maynard Smith, J., 1974. The theory of games and the evolution of animal conflicts. J. Theor. Biol., 47, 209-221. [86] Maynard Smith J, 1982. Evolution and the Theory of Games, Cambridge Univ. Press, Cambridge, UK. [87] Maynard Smith, J., Price, G.R., 1973. The logic of animal conflict. Nature, 246, 15-18. [88] McNamara, J., Casson, C., Houston, A., 1999. Incorporating rules for responding into evolutionary games. Nature 401, 368-371. [89] McNamara, J.M., Houston, A.I., 1986. The common currency for behavioral decisions. American Naturalist, 1986. [90] Mesterton-Gibbons, M., 1994. The Hawk-Dove game revisited: Effects of continuous variation in resource-holding potential on the frequency of escalation. Evolutionary Ecology, 8, 3, 230-247. [91] Metz, J.A.J., Geritz, S.A.H., Meszena, G., Jacobs, F.J.A., van Heerwarden, .J.S., 1996. Adaptive dynamics, a geometrical study of the consequences of nearly faithful reproduction. In: van Strien, S.J., Verduyn Lunel, S.M., (Eds.), Stochastic and Spatial EFTA00749011

Bibliography 145 Structures of Dynamical Systems, K. Ned. Alcad. Van Wet. B 45, 183-231. North- Holland Publishing Company, Amsterdam, Holland. [92] Milinski, M., 1987. TIT FOR TAT in sticklebacks and the evolution of cooperation. Nature, 325, 433-435. [93] Moran, P.A.P., 1975. Wandering distributions and electrophoretic profile. Theor. Popul. Biol. 8, 318-330. [94] Nash, J.F., 1950. Equilibrium points in n-person games. PNAS 36, 48-49. [95] Nalcamaru M, Matsuda H, Iwasa Y, 1997. The evolution of cooperation in a lattice structured population. J. Theor. Biol., 184, 65-81. [96] Nalcamaru, M., Nogami, H., Iwasa, Y., 1998. Score dependent fertility model for the evolution of cooperation in a lattice. J. Theor. Bio1.194, 101-124. [97] Nalcamaru, M., Iwasa, Y., 2005. The evolution of altruism by costly punishment in lattice structured populations: score dependent viability versus score dependent fertility. Evol. Ecol. Res. 7, 853-870. [98] Nakamaru, M., Iwasa, Y., 2006. The coevolution of altruism and punishment: role of the selfish punisher... Theor. Biol. 240, 475-488. [99] Nalcamaru, M., Sasaki, A., 2003. Can transitive inference evolve in animals playing the hawk-dove game? .1. Theor. Biol., 222, 4, 461-470. [100] Nowak, M.A., 2006a. Evolutionary Dynamics. Harvard University Press. [101] Nowak MA, 2006b. Five rules for the evolution of cooperation. Science, 314, 1560- 1563. [102] Nowak, M. A., Anderson, R. 141., McLean, A. It., Wolfs, T., Coudsmit, J., and May, R. M., 1991. Antigenic diversity thresholds and the development of aids. Science, 254, 963-969. (103] Nowak, 141.A., Bonhoeffer, S., May, R.M., 1994. Spatial games and the maintenance of cooperation. P. Natl. Acad. Sci. U.S.A. 91, 4877-4881. [104] Nowak MA, May Ia1, 1992. Evolutionary games and spatial chaos. Nature, 359, 826- 829. [105] Nowak, M.A., May, R.M., 1993. The spatial dilemmas of evolution. Int. J. Bifurcat. Chaos 3, 35-78. [106] Nowak, M.A., May, R.M., 1994. Superinfection and the evolution of parasite virulence. Proc. R. Soc. B 255, 81-89. EFTA00749012

Bibliography 146 [107] Nowak, M.A., May, R.M., Phillips, R.E., Rowland-Jones, S., Lalloo, D.G., McAdam, S., Klenerman, P., Koppe, B., Sigmund, K., Bangham, C.R.M., McMichael, A.J., 1995. Antigenic oscillations and shifting inununodominance in HIV-1 infections. Na- ture 375, 606-611. [108] Nowak, M.A., Komarova, N.L., Niyogi, P., 2002. Computational and evolutionary aspects of language. Nature 417, 611-617. [109] Nowak, M.A., Krakauer, D.C., (1999). The evolution of language. P Natl Acad Sci USA 96: 8028-8033. [110] Nowak MA, A Sasaki, C Taylor, D Fudenberg, 2004. Emergence of cooperation and evolutionary stability in finite populations. Nature 428, 646-650. [111] Nowak, M. A. and Sigmund, K., 1989. Game-dynamical aspects of the prisoner's dilemma. Appl. Math. Comp. 30, 191-213. [112] Nowak, M., Sigmund, K., 1990. The evolution of stochastic strategies in the prisoner's dilemma. Acta Appl. Math. 20, 247-265. [113] Nowak MA, Sigmund K, 2004. Evolutionary dynamics of biological games. Science, 303, 793-799. 0.14] Nowak, M.A., Sigmund, K., 2005. Evolution of indirect reciprocity. Nature 427, 1291- 1298. (115] Ohtsuki H, Hauert C, Lieberman E, Nowak MA, 2006a. A simple nile for the evolution of cooperation on graphs and social networks. Nature, 441, 502-505. [116] Ohtsuki, H., Iwasa, Y., 2004. How should we define goodness? — reputation dynamics in indirect reciprocity. J. Theor. Biol. 231, 107-120. [117] Ohtsuki, H., Nowak, M.A., 2006b. Evolutionary games on cycles. Proc. R. Soc. B 273, 2249-2256. [118] Ohtsuki, H., Nowak, M.A., 2007. Direct reciprocity on graphs. J. Theor. Biol. 247, 462-470. [119] Ohtsuki H, Nowak MA, 2008. Evolutionary stability on graphs. J Theor Biol, 251: 698-707. [120] Ohtsuki, H., Pacheco, J., Nowak, M.A., 2007. Evolutionary graph theory: breaking the symmetry between interaction and replacement. J. Theor. Biol. 246, 681-694. [121] Pacheco, JM., Traulsen, A. Nowak, M.A., 2006. Active linking in evolutionary games. J. Theor. Biol. 243, 437-443. EFTA00749013

Bibliography 147 [122] Parker, G.A., 1974. Assessment strategy and the evolution of fighting behavior. J. Theor. Biol. [123] Pfeiffer, T., Schuster, S., Bonhoeffer, S., 2001. Cooperation and Competition in the Evolution of ATP-Producing Pathways. Science, 292, 5516, 504-507. [124] Queller, D.C., 1985. Kinship, reciprocity and synergism in the evolution of social behaviour: a synthetic model. Nature 318, 366-367. [125] Riley, J.G., 1979. Evolutionary equilibrium strategies. J. Theor. Biol. 76, 109-123. [126] Riolo RL, Cohen MD, Axelrod R, 2001. Evolution of cooperation without reciprocity. Nature, 418, 441-443. [127] Rousset, F., 2004. Genetic structure and selection in subdivided populations. Prince- ton University Press. [128] Rousset, F., Billiard, S., 2000. A theoretical basis for measures of kin selection in subdivided populations: finite populations and localized dispersal. J. Evol. Biol. 13, 814-825. (129] Samuelson, L., 1997. Evolutionary Games and Equilibrium Selection. MIT Press, Cambridge, MA. [130] Santos FC, Santos MD, Pacheco JM, 2008. Social diversity promotes the emergence of cooperation in public goods games. Nature, 454, 213-216. [131] Schaffer, M., 1988. Evolutionarily stable strategies for a finite population and variable contest size. J. Theor. Biol. 132, 469-478. [132] Schelling, T. C., 1980. The Strategy of Conflict. Harvard University Press. [133] Schreiber, S., 2001. Urn models, replicator processes, and random genetic drift. Siam J. Appl. Math., 61, 2148-2167. [134] Seger, J., 1981. Kinship and covariance. J. Theor. Biol. 91, 191-213. [135] Szabo, G., Antal, T., Szabo, P. & Droz, M. 2000 Spatial evolutionary prisoner's dilemma game with three strategies and external constraints. Phys. Rev. E 62, 1095- 1103. [136] Szabo, G., Fath, G., 2007. Evolutionary games on graphs. Phys. Rep. 446, 97-216. [137] Szabo G, Take C, 1998. Evolutionary prisoner's dilemma game on a square lattice. Phys. Rev. E, 58, 69-73. [138] Tajfel H, 1982. Social psychology of intergroup relations. Annu. Rev. Psychol., 33, 1-30. EFTA00749014

Bibliography 148 [139] Tarnita C.E., Antal, T., Ohtsuki H., Nowak, M.A., 2009a. Evolutionary dynamics in set structured populations. PNAS 2009. [140] Tarnita C.E., Ohtsuki, H., Antal, T., Fu, F., Nowak, M.A., 2009b. Strategy selection in structured populations. .1. Theor. Biol., 2009. [141] Taylor, C., Nowak, M.A., 2007. Transforming the dilemma. Evolution 61, 2281-2292. [142] Taylor, C., Fudenberg, D., Sasaki, A., Nowak, M.A., 2004. Evolutionary game dy- namics in finite populations. B. Math. Biol. 66, 1621-1644. [143] Taylor PD, 1988. An inclusive fitness model for dispersal of offspring. J them Biol, 130, 363-378. [144] Taylor, P.D., 1992a. Altruism in viscous populations—an inclusive fitness model. Evol. Ecol. 6, 352-353. (145] Taylor, P.D., 1992b. Inclusive fitness in a homogeneous environment. Proc. R. Soc. B 249, 299-302. [146] Taylor, P.D., Frank, S., 1996. How to make a kin selection argument. J. Theor. Biol. 180, 27-37. [147] Taylor, P.D., Jonker, L.B., 1978. Evolutionary stable strategies and game dynamics. Math. Biosci. 40, 145-156. [148] Taylor, P.D., Irwin, A., Day, T., 2000. Inclusive fitness in finite deme-structured and stepping-stone populations. Selection 1, 83-93. [149] Taylor PD, Day T, Wild G, 2007a. Evolution of cooperation in a finite homogeneous graph. Nature, 447, 469-472. 1150] Taylor, P.D., Day, T., Wild, G., 2007b. From inclusive fitness to fixation probability in homogeneous structured populations. .J. Theor. Biol. 249, 101-110. [151] Tilman D, Kareiva P eds., 1997. Spatial Ecology: The Role of Space in Population Dynamics and Interspecific Interactions, Princeton Univ. Press, Princeton. 1152] Traulsen A, Claussen JC, 2004. Similarity based cooperation and spatial segregation. Phys. Rev. E, 70, 046128. (153] Traulsen, A., Hauert, C., H. De Silva, Nowak, M. A. and Sigmund, K., 2009. Explo- ration dynamics in evolutionary games. PNAS 106, 709-712. [154] Traulsen, A., Nowak, M.A., 2006. Evolution of cooperation by multi-level selection. P. Natl. Acad. Sci. USA, 103, 10952-10955 EFTA00749015

Bibliography 149 [155] Traulsen, A., Nowak, M. A., Pacheco, J. M., 2006. Stochastic dynamics of invasion and fixation. Phys. Rev. E 74, 011909. [156] Traulsen A, Pacheco J M, Nowak M A, 2007. Pairwise comparison and selection temperature in evolutionary game dynamics. 3 them Biol 246, 522-529. [157] Traulsen, A., Shoresh, N., Nowak, M.A., 2008. Analytical results for individual and group selection of any intensity. B. Math. Biol. 70, 1410-1424. [158] Trivers, R.L., 1971. The evolution of reciprocal altruism. Q. Rev. Biol. 46, 35-57. [159] Turner, P.E., Chao, L., 1999. Prisoner's dilemma in an RNA virus. Nature 398, 441- 443. [160] Turner, P. E. and Chao, L., 2003. Escape from prisoner's dilemma in RNA phage 06. Am. Nat., 161, 497-505. [161] van Baalen, M., Rand, D.A., 1998. The unit of selection in viscous populations and the evolution of altruism... Theor. Biol. 193, 631-648. [162] van Kampen, N. G., 1997. Stochastic Processes in Physics and Chemistry, 2nd ed. North-Holland, Amsterdam. [163] von Neumann, J., Morgenstern, O., 1944. Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ. [164] Wakeley, J., 2008. Coalescent Theory: An Introduction. Roberts & Company Pub- lishers, Greenwood Village, Colorado. [165] Weibull, J.W., 1995. Evolutionary Game Theory. MIT Press, Cambridge, MA. [166] Wild, G., Taylor, P.D., 2004. Fitness and evolutionary stability in game theoretic models of finite populations. Proc. Roy. Soc. Lond. B, 271, 2345-2349. (167] Wild, G., Traulsen, A., 2007. The different limits of weak selection and the evolution- ary dynamics of finite populations. J. Theor. Biol. 247, 382-390. [168] Wright S, 1931. Evolution in mendelian populations. Genetics, 16, 97-159. [169] Yamagishi T, Jin N, Kiyonari T, 1999. Bounded generalized reciprocity. Adv. Group Process., 16, 161-197. [170] Yamamura, N., Higashi, M., Behera, N., Walcano, J., 2004. Evolution of mutualism through spatial effects. J. Theor. Biol. 226, 421-428. [171] Zeeman, E.C., 1980. Population dynamics from game theory. In: Nitecki, Z.H., Robin- son, R.C., (Eds.), Proceedings of an International Conference on Global Theory of Dynamical Systems. Lecture Notes in Mathematics, vol. 819. Springer, Berlin. EFTA00749016