Dynamic properties of evolutionary multi-player games in finite populations

Wu, Bin; Traulsen, Arne; Gokhale, Chaitanya S. Article Dynamic properties of evolutionary multi-player games in finite populations Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Wu, Bin; Traulsen, Arne; Gokhale, Chaitanya S. (2013) : Dynamic properties of evolutionary multi-player games in finite populations, Games, ISSN 2073-4336, MDPI, Basel, Vol. 4, Iss. 2, pp. 182-199, https://doi.org/10.3390/g4020182 This Version is available at: https://hdl.handle.net/10419/98536 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/3.0/ Games 2013,4, 182-199; doi:10.3390/g4020182 OPEN ACCESS games ISSN 2073-4336 www.mdpi.com/journal/games Article Dynamic Properties of Evolutionary Multi-player Games in Finite Populations Bin Wu, Arne Traulsen * and Chaitanya S. Gokhale Evolutionary Theory Group, Max-Planck-Institute for Evolutionary Biology, August-Thienemann-Straße 2, 24306 Pl¨ on, Germany *Author to whom correspondence should be addressed; E-Mail: [email protected]; Tel.: +49 4522 763 239; Fax: +49 4522 763 260. Received: 11 February 2013; in revised form: 11 April 2013 / Accepted: 22 April 2013 / Published: 6 May 2013 Abstract: William D. Hamilton famously stated that “human life is a many person game and not just a disjoined collection of two person games”. However, most of the theoretical results in evolutionary game theory have been developed for two player games. In spite of a multitude of examples ranging from humans to bacteria, multi-player games have received less attention than pairwise games due to their inherent complexity. Such complexities arise from the fact that group interactions cannot always be considered as a sum of multiple pairwise interactions. Mathematically, multi-player games provide a natural way to introduce non-linear, polynomial fitness functions into evolutionary game theory, whereas pairwise games lead to linear fitness functions. Similarly, studying finite populations is a natural way of introducing intrinsic stochasticity into population dynamics. While these topics have been dealt with individually, few have addressed the combination of finite populations and multi-player games so far. We are investigating the dynamical properties of evolutionary multi-player games in finite populations. Properties of the fixation probability and fixation time, which are relevant for rare mutations, are addressed in well mixed populations. For more frequent mutations, the average abundance is investigated in well mixed as well as in structured populations. While the fixation properties are generalizations of the results from two player scenarios, addressing the average abundance in multi-player games gives rise to novel outcomes not possible in pairwise games. Keywords: multi-player games; finite population; fixation probability; fixation time; average abundance Games 2013,4183 1. Introduction The analysis of stochastic evolutionary game dynamics has rapidly developed in the past decade [1–10]. Here, we are interested in two particular aspects: intrinsic stochastic effects induced by finite population size and nonlinearities in payoff induced by multi-player interaction. Finite population analysis in evolutionary game dynamics has the potential to challenge and extend the traditional predictions based on infinitely large populations [1,11]. For a game in an infinite large population, evolutionary outcomes are characterized by the equilibrium states of the system and their stability [12]. However, when we consider the evolutionary process in a finite population, it is important to investigate the stochastic properties of the system, such as fixation probability, fixation time and average abundance in mutation-selection equilibrium. In a multi-player game, an individual obtains its payoff from interactions with more than one co-player. Compared with pairwise games (or matrix games), this generalization depicts more complex scenarios relevant to biological and social situations [13–18]. For example, in the yeast Saccharomyces cerevisiae, strains with gene SUC2 secrete an enzyme called invertase, which catalyses the hydrolysis of sucrose into glucose and fructose. These can then be transported inside the cells of yeast [19]. The strains with gene suc2, however, do not secrete invertase. Instead, they just take in the products hydrolysed by the SUC2 strain. In this case, the SUC2 gene has been referred to as a cooperator, and the suc2 has been referred to as a defector. Due to the viscosity or the limited dispersal of the nutrients, the interactions often involve more than two cells, thus it can be referred as a multiple player game. While some authors have argued that the dynamics of the interaction of these two strains can then be captured by a snow drift game [20,21], it is not clear if this situation is a social dilemma at all, since the maximum population payoff occurs for a mixture of the two types [22]. In general, for multiple player games, the payoff is determined by the probability of a specific configuration of the players. This probability is a nonlinear function of the population composition and thus makes the fitness nonlinear. Therefore, multi-player games provide a natural framework for exploring nonlinear effects. For example, when there are only two strategies A and Bin a d-player game where orderings of players do not matter, the payoff structure in a multi-player game is a simple table, Opposing Aplayers d−1d−2. . . k . . . 0 A ad−1ad−2. . . ak. . . a0 B bd−1bd−2. . . bk. . . b0 ,(1) where akand bkrefer to the payoffs for a strategy Aand Bindividual. If we are interested in calculating the average payoff of a focal individual with a certain strategy, then we need to choose d−1other co-players to make up a d-player game. Out of the d−1other players, some can have strategy A while others have strategy B. The index krefers to the number of Aco-players in the group. In a finite population of size Nwith iindividuals of type A, the probability for a focal individual of type Ato Games 2013,4184 choose a co-player group that consists of k A players and d−1−k B players is given by a hypergeometric distribution. The probability that an Aplayer interacts with kother Aplayers is given by H(k, d;i, N) = i−1 kN−i d−1−k N−1 d−1,(2) which can be approximated by a binomial distribution when the population size Nis large. The hypergeometric sampling leads to the average payoffs, πA= d−1 X k=0 H(k, d;i, N)ak(3) πB= d−1 X k=0 H(k, d;i+ 1, N)bk. Since this is valid for the average payoffs, the relation between dand Nis not an issue, as long as d≤N. If we would consider only a single interaction instead, one has to ensure that every individual is taking part in an interaction [23]. Note that H(k, d;i, N)is a polynomial of degree d−1in i. The average payoff of each strategy is thus also a polynomial of degree d−1. For d= 2, that is a pairwise interaction, the payoffs are linear in the number of strategy Aplayers in the population. For a multi-player game, i.e.,d > 2, the payoffs are nonlinear, but remain polynomials. Such nonlinearities mimic the interaction pattern among individuals, like the public goods, for example, the invertase produced by the cooperator yeast in the above example is a saturating function of cooperators’ concentration. Dynamical properties of such multi-player games in infinitely large populations have been previously addressed [24–26] and we focus on their finite population version. Both mutation and selection are fundamental in evolutionary theory. Mutations have the potential to generate distinct genotypes and phenotypes while selection acts upon those diverse phenotypes. The Moran process with mutations is employed to mimic this evolutionary process. In addition, intrinsic random drift is present in this process [1,27]. An individual is chosen with a probability proportional to its fitness for birth and another randomly selected individual is chosen for death. Mutations can occur during birth with probability µ. For two strategies Aand B, this is a one-dimensional birth–death process with the transition probabilities T± ifrom i A individuals to i±1Aindividuals, T+ i=ifA ifA+ (N−i)fB N−i N(1 −µ) + N−i Nµ T− i=(N−i)fB ifA+ (N−i)fB i N(1 −µ) + i Nµ. (4) The probability to remain in the same state is 1−T+ j−T− j. Fitness has to be an increasing function of payoff [28]. We define the fitness of a strategy Sas fS= exp[wπS][29]. We follow the usual assumption that mutations only switch between the pre-existing strategies but do not generate an entirely novel strategy; for such a model we refer to [30–32]. The non-negative parameter wmeasures the intensity of selection [33]. For w1, selection is weak and the game has a very small effect on the fitness of the strategies, whereas for w1, selection is strong and only the fitter type reproduces and survives. The choice of fS= exp[wπS]has the convenient property to recover the usual results valid for Games 2013,4185 weak selection, and to allow for arbitrary limit. Besides, such an exponential fitness can sometimes also be biologically relevant [34,35]. When the probability of mutation is sufficiently small [4], the waiting time for a mutation to occur is much longer than the time required for the mutant type to fixate or go extinct [7,10]. To quantify the evolutionary fate of the mutant type, it is thus important to address the probability of fixation of a single mutant. Furthermore, if this happens, then how long does it take, i.e. what is the conditional fixation time? The fixation probability has been used to define evolutionary stability in finite population [1,36,37]. It has been proposed that a strategy is evolutionary stable in a finite population if in addition to the usual requirements of evolutionary stability, the fixation probability of an invading mutant is smaller than the neutral fixation probability. One of the most interesting results arising from this definition is the one-third rule. For a coordination game, a 2×2game with an unstable internal equilibrium, the fixation probability of a mutant strategy is larger than that in the neutral case (1/N) if the attraction basin of the wild type strategy in replicator dynamics is smaller than one third. This result has been proved to be robust for a wide class of evolutionary processes [28,36–38]. The one third rule has also been extended to multi-player games [39,40] and has been proven to be valid for all processes in the domain of Kingman’s coalescence even in its generalized, multi-player form [41]. Yet, the one third rule as well as its extensions are only based on weak selection. It is not yet clear how the fixation probability changes with increasing selection intensity. Fixation times can be interesting to analyse, e.g., the fixation probability can tell us that a strategy can fix with a probability greater than neutral, but it can take longer for fixation to occur. This seemingly unintuitive property of the conditional fixation time has been termed as stochastic slowdown [42,43]. It was shown that a mutant with a slight frequency dependent advantage can take longer to fixation than a neutral mutant. How does the fixation time change with the number of players under weak selection? Do we observe stochastic slowdown for multi-player games as well? If so, is this effect enhanced or inhibited with the increase of the number of players involved in the game? While multi-player games naturally convey nonlinearity to the evolutionary dynamics, weak selection reduces the differences in the fitnesses of the strategies bringing the dynamics close to neutrality. What is the interplay between these two effects? For intermediate mutation probabilities, mutations can occur while the previous mutant still has an intermediate abundance in the population. In this case, considering extinction or fixation does not make sense as mutations keep the population polymorphic. The system can be characterized by the abundances of the strategies in the long run. These average abundances can give a measure of how favored a strategy is in the selection mutation equilibrium. For 2×2games, for a given population structure and evolutionary dynamics with mutation, a single parameter condition is obtained to determine which strategy is more abundant than in the neutral case under weak selection [44]. For general n×ngames, a two-parameter condition is obtained [45]. These parameters do not depend on the number of strategies or the payoff matrix, but only on the particular process under study. But how many such parameters are necessary for multi-player games? Motivated by these questions, we investigate the fixation probability, the conditional fixation time and average abundance in multi-player games. For the fixation probability, we concentrate on how the Games 2013,4186 fixation probability changes with increasing selection intensity. For the conditional fixation time, we address the so-called stochastic slowdown effect [42,43]. For the average abundance, we generalize the so-called σrule [45]. 2. Fixation For sufficiently small mutation probabilities, the time of fixation or extinction is much shorter than the average time between two consecutive mutants. In this case, the transition probabilities are given by Equation (4) with zero mutation probability, µ= 0. 2.1. Fixation Probability If there are iindividuals of type Ain a population of size Ninitially, the probability that the whole population will eventually consist only of Aindividuals is given by [46,47], ρA i= 1 + Pi−1 k=1 Qk l=1 T− l T+ l 1 + PN−1 k=1 Qk l=1 T− l T+ l ,(5) where in our case the ratio of transition probabilities is T− l T+ l =fB fA =e−w∆π(l),(6) with ∆π(l) = πA−πB. The concept of evolutionary stability in finite populations by using the fixation probability was proposed in [1]. A condition for evaluating the stability of strategy Ain a finite population is ρB 1(w)<1/N. For small selection intensity, this condition leads to the one third rule, which has been derived to capture evolutionary stability. For strong selection intensity, this concept is consistent with the conventional evolutionary stability [37]. Yet, few authors have considered intermediate selection intensity. Here we are addressing the shape of the fixation probability through the whole range of the selection intensity (w > 0). In particular, we are addressing how many maxima and minima there are at most for a d-player game. Theorem 1. For a d-player, two strategy game and for the Moran process with the exponential fitness mapping, the fixation probability as a function of the selection intensity can only be monotonically increasing or decreasing, or have a single maximum. Proof. By Equation (5), the fixation probability of a mutant taking over the whole population is ρA 1(w) = 1 1 + PN−1 k=1 e−w(Pk i=1 ∆πi).(7) Games 2013,4187 Thus, the number of the maxima and minima of ρA 1(w)is determined by the number of the positive roots of the equation ρ0A 1(w) = 0. This derivative can be written as ρ0A 1(w) = ρA 1(w)2 N−1 X k=1 k X i=1 ∆πi!e−w(Pk i=1 ∆πi) | {z } P(w) .(8) Now, ρ0 1(w)=0is equivalent to P(w)=0due to the fact that ρA 1(w)>0for all w < ∞. We take the derivative of P(w)with respect to w, P0(w) = − N−1 X k=1 k X i=1 ∆πi!2 e−w(Pk i=1 ∆πi).(9) P0(w)is never positive. It is zero if the payoff difference fulfills Pk i=1 ∆πi= 0 for all 1≤k≤N−1 and negative in all other cases. In other words, P(w)is always non-increasing. Hence the equation P(w)=0, or, equivalently, ρ0A 1(w)=0, has at most one solution. This implies that the fixation probability as a function of selection intensity can be either monotonically increasing or decreasing or have a single extremum. However, it turns out that ρA 1(w)cannot have a minimum, since this assumption leads to a contradiction: If there exists a two player game such that ρA 1(w)has a minimum, then it is necessary that both ρ0A 1(0) <0and limw→∞ ρA 1(w) = 1 hold (Figure 1top right). Yet, if limw→∞ ρA 1(w)=1, by Equation (7), we have Pk i=1 ∆πi>0for all 1≤k≤N−1. Then, from Equation (8), we have at w= 0,ρ0A 1(0) = ρA 1(0)2PN−1 k=1 Pk i=1 ∆πi>0. This is a contradiction to ρ0A 1(0) <0. Thus, the fixation probability as a function of selection intensity can only increase or decrease monotonically or have a single maximum. Note that this result holds also for any two player games and proves that the extremum discussed in [1] can only be a maximum. Corollary. For a two strategy d-player game, if there is w∗>0such that ρA 1(w∗)>1/N, then the set of the selection intensities that makes ρ1(w)>1/N is an interval. Employing the corollary, given two selection intensities w1and w2(w1> w2), if ρA 1(w1)> ρA 1(w2)> 1/N, then ρA 1(w)>1/N for all intensities of selection wfulfilling w1< w < w2. For frequency independent fitness, the fixation probability of a mutant is φ(r) = (1 −(1/r))/(1 −(1/r)N−1), where r > 0is the relative fitness of the mutant strategy compared with the wild strategy. In population genetics, s=r−1is often termed as selection intensity [48]. Notice that φ(r)is an increasing function of r, the set such that φ(r)>1/N is (1,+∞), an interval. Therefore in terms of the selection intensity s, it is still an interval. For the frequency dependent case, such as the most simple 2×2games, it has been shown that there can be one hump in the fixation probability with the selection intensity via numerical methods [1]. This also suggests that the set {w > 0|ρA 1(w)>1/N}is also an interval. This corollary shows that this is universal for general multi-player games. Games 2013,4188 Figure 1. Illustrations of possible shapes of the fixation probability as a function of the selection intensity. Based on Theorem 1, we illustrate the qualitative shape of the fixation probability as a function of the selection intensity, given that the strong and weak selection scenarios are known. Under weak selection, the fixation probability of strategy Acan be less than neutral (top row) or greater than neutral (bottom row). Simultaneously, in the limit of strong selection, the fixation probability can approach zero (left column) or unity (right column). We show that the top right case, i.e., the fixation probability being less than neutrality under weak selection and approaching unity for strong selection, is not possible (Theorem 1). This means that an unfavorable strategy under strong selection can be selected for under weak selection (bottom left), but a favorable strategy under strong selection will never be unfavorable for any intensity of selection (top right). ⇢A 1(w)<1/N 0 1 2 3 4 5 -5 0 5 10 0 1 2 3 4 5 0.0 0.5 1.0 1.5 2.0 0 1 2 3 4 5 0.80 0.85 0.90 0.95 1.00 1.05 1.10 1.15 1.20 lim w!1⇢A 1(w)=0 lim w!1⇢A 1(w)=1 ⇢A 1(w)>1/N 0.0 1.0 monotonically decreasing monotonically increasing Case not possible! one maximum one minimum 1/N 1/N 1/N Fixation Probability Fixation Probability ⇢A 1(w)<1/N ⇢A 1(w)>1/N Selection Intensity w Weak Strong Selection Intensity w Weak Strong 2.2. Fixation Time Under the assumption of small mutation probabilities, the time until a single mutant Areaches fixation (conditional fixation time) can be written as [7,47,49], τA 1= N−1 X p=1 p X l=1 ρA l T+ l p Y m=l+1 T− m T+ m .(10) For the conditional fixation time in the neutral case, τA 1|w=0, we have ρA l=l/N,T+ l= l(N−l)/N2, and T− m/T+ m= 1. Inserting these expressions into Equation (10) results in τA 1|w=0 = PN−1 p=1 Pp l=1 N/(N−l). With the identity PN−1 p=1 Pp l=1 =PN−1 l=1 PN−1 p=l[50], we obtain τA 1|w=0 = N(N−1) [51,52]. For weak selection, we can formally write down the series expansion of the conditional fixation time to the first order, Games 2013,4189 τA 1≈[τA 1]w=0 +w∂ ∂wτA 1w=0 ,(11) where the constant term is the neutral term calculated above. It has been shown that the conditional fixation time of a single mutant of either type is the same, τA 1=τB N−1[7,53,54]. This identity holds for any birth–death process, and is thus valid for any two strategy games and for any selection intensity. Since τA 1and τB N−1are identical up to any order in w, we obtain ∂ ∂wτA 1w=0 =∂ ∂wτB N−1w=0 .(12) By Equation (10), the first order term in Equation (11) reads ∂ ∂w τA 1=P|α|=1 PN−1 p=1 Pp l=1 hα,(13) hα=∂α1 ∂wα1 1 T+ l∂α2 ∂wα2φl∂α3 ∂wα3 p Q m=l+1 T− m T+ m,(14) with the multi-index α= (α1, α2, α3),|α|=α1+α2+α3with αi≥0. For each above α,hαis linear in the payoff entries. In other words, hαis in the form of Pd−1 k=0 Gα kak+Pd−1 k=0 Fα kbk, where Gα kand Fα kdo not depend on the payoff entries. Therefore, by Equation (13), the first order expansion of the conditional fixation time is of the form Pd−1 k=0 Gkak+Pd−1 k=0 Fkbk, where Gkand Fkare only dependent on the population size Nand the group size of the game d, while they have no relationship with the payoff entries. By the symmetry property, Equation (12), the first order expansion of the fixation time is invariant under the payoff matrix transformation A↔B. In other words, the conditional fixation time of a single strategy Aindividual in the game given by Equation (1) is identical with that of a single strategy Bindividual in a game with the transformed payoff matrix Opposing Bplayers d−1d−2. . . k . . . 0 B b0b1. . . bk. . . bd−1 A a0a1. . . ak. . . ad−1 (15) Thus, we have d−1 X k=0 Gkak+ d−1 X k=0 Fkbk= d−1 X k=0 Gkbd−1−k+ d−1 X k=0 Fkad−1−k(16) for arbitrary akand bk. This expression holds for any game, but the Gkand Fkare independent of the game. Thus, we can calculate them for an arbitrary special case. In particular, for the game with payoffs ai=δi0and bi= 0, where δij is the Kronecker delta, Equation (16) yields G0=Fd−1. Similarly, we obtain Gk=Fd−1−k,0≤k≤d−1.(17) Games 2013,4196 21. Gore, J.; Youk, H.; van Oudenaarden, A. Snowdrift game dynamics and facultative cheating in yeast. Nature 2009,459, 253-256. 22. MacLean, G.; Fuentes-Hernandez, A.; Greig, D.; Hurst, L.D.; Gudelj, I. A mixture of “cheats” and “co-operators” can enable maximal group benefit. PLoS Biology 2010,8, e1000486. 23. Woelfing, B.; Traulsen, A. Stochastic sampling of interaction partners versus deterministic payoff assignment. J. Theor. Biol. 2009,257, 689-695. 24. Broom, M.; Cannings, C.; Vickers, G. Multi-player matrix games. B. Math. Biol. 1997, 59, 931-952. 25. Bukowski, M.; Miekisz, J. Evolutionary and asymptotic stability in symmetric multi-player games. Int. J. Game Theory 2004,33, 41-54. 26. Han, T.A.; Traulsen, A.; Gokhale, C.S. On equilibrium properties of evolutionary multi-player games with random payoff matrices. Theor. Popul. Biol. 2012,81, 264-72. 27. Moran, P.A.P. Random processes in genetics. Proc. Cambridge Philos. Soc. 1958,54, 60-71. 28. Wu, B.; Altrock, P.M.; Wang, L.; Traulsen, A. Universality of weak selection. Phys. Rev. E 2010,82, 046106. 29. Traulsen, A.; Shoresh, N.; Nowak, M.A. Analytical results for individual and group selection of any intensity. B. Math. Biol. 2008,70, 1410-1424. 30. Huang, W.; Traulsen, A. Fixation probabilities of random mutants under frequency dependent selection. J. Theor. Biol. 2010,263, 262-268. 31. Huang, W.; Haubold, B.; Hauert, C.; Traulsen, A. Emergence of stable polymorphism driven by evolutionary games between mutants. Nature Commun. 2012,3, 919. 32. Huang, W.; Werner, B.; Traulsen, A. The impact of random frequency-dependent mutations on the average population fitness. BMC Evol. Biol. 2012,12, 160. 33. Traulsen, A.; Pacheco, J.M.; Nowak, M.A. Pairwise comparison and selection temperature in evolutionary game dynamics. J. Theor. Biol. 2007,246, 522-529. 34. B¨ urger, R. The Mathematical Theory of Selection, Recombination, and Mutation; John Wiley and Sons: Chichester, UK, 2000. 35. Wu, B.; Gokhale, C.S.; Van Veelen, M.; Wang, L.; Traulsen, A. Interpretations arising from Wrightian and Malthusian fitness under strong frequency dependent selection. Ecol. Evol. 2013, doi: 10.1002/ece3.500. 36. Imhof, L.A.; Nowak, M.A. Evolutionary game dynamics in a Wright-Fisher process. J. Math. Biol. 2006,52, 667-681. 37. Traulsen, A.; Pacheco, J.M.; Imhof, L.A. Stochasticity and evolutionary stability. Phys. Rev. E 2006,74, 021905. 38. Lessard, S.; Ladret, V. The probability of fixation of a single mutant in an exchangeable selection model. J. Math. Biol. 2007,54, 721-744. 39. Kurokawa, S.; Ihara, Y. Emergence of cooperation in public goods games. Proc. R. Soc. B 2009, 276, 1379-1384. 40. Gokhale, C.S.; Traulsen, A. Evolutionary games in the multiverse. Proc. Natl. Acad. Sci. USA 2010,107, 5500-5504. Games 2013,4197 41. Lessard, S. On the robustness of the extension of the one-third law of evolution to the multi-player game. Dynam. Games Appl. 2011,1, 408-418. 42. Altrock, P.M.; Gokhale, C.S.; Traulsen, A. Stochastic slowdown in evolutionary processes. Phys. Rev. E 2010,82, 011925. 43. Altrock, P.M.; Traulsen, A.; Galla, T. The mechanics of stochastic slowdown in evolutionary games. J. Theor. Biol. 2012,311, 94-106. 44. Tarnita, C.E.; Ohtsuki, H.; Antal, T.; Fu, F.; Nowak, M.A. Strategy selection in structured populations. J. Theor. Biol. 2009,259, 570-581. 45. Tarnita, C.E.; Wage, N.; Nowak, M.A. Multiple strategies in structured populations. Proc. Natl. Acad. Sci. USA 2011,108, 2334-2337. 46. Karlin, S.; Taylor, H.M.A. A First Course in Stochastic Processes, 2nd edition ed.; Academic: London, UK, 1975. 47. Traulsen, A.; Hauert, C. Stochastic evolutionary game dynamics. In Reviews of Nonlinear Dynamics and Complexity; Schuster, H.G., Ed.; Wiley-VCH: Weinheim, Germany, 2009; Vol. II, pp. 25-61. 48. Kimura, M. On the probability of fixation of mutant genes in a population. Genetics 1962, 47, 713-719. 49. Kampen, N.G.v. Stochastic Processes in Physics and Chemistry, 2nd ed.; Elsevier: Amsterdam, Netherlands, 1997. 50. Graham, R.L.; Knuth, D.E.; Patashnik, O. Concrete Mathematics, 2nd ed.; Addison-Wesley: Reading, MA, USA, 1994. 51. Ewens, W.J. Mathematical Population Genetics. I. Theoretical Introduction; Springer: New York, NY, USA, 2004. 52. Altrock, P.M.; Traulsen, A. Fixation times in evolutionary games under weak selection. New J. Phys. 2009,11, 013012. 53. Maruyama, T.; Kimura, M. A note on the speed of gene frequency changes in reverse direction in a finite population. Evolution 1974,28, 161-163. 54. Taylor, C.; Iwasa, Y.; Nowak, M.A. A symmetry of fixation times in evolutionary dynamics. J. Theor. Biol. 2006,243, 245-251. 55. Nathanson, C.G.; Tarnita, C.E.; Nowak, M.A. Calculating evolutionary dynamics in structured populations. PLoS Comput. Biol. 2009,5, e1000615. 56. Tang, C.; Li, X.; Cao, L.; Zhan, J. The σlaw of evolutionary dynamics in community-structured population. J. Theor. Biol. 2012,306, 1-6. 57. Antal, T.; Traulsen, A.; Ohtsuki, H.; Tarnita, C.E.; Nowak, M.A. Mutation-selection equilibrium in games with multiple strategies. J. Theor. Biol. 2009,258, 614-622. 58. Gokhale, C.S.; Traulsen, A. Strategy abundance in evolutionary many-player games with multiple strategies. J. Theor. Biol. 2011,238, 180-191. 59. Van Veelen, M.; Nowak, M.A. Multi-player games on the cycle. J. Theor. Biol. 2012,292, 116128. 60. Szab´ o, G.; Hauert, C. Phase transitions and volunteering in spatial public goods games. Phys. Rev. Lett. 2002,89, 118101. Games 2013,4198 61. Szab´ o, G.; F´ ath, G. Evolutionary games on graphs. Phys. Rep. 2007,446, 97-216. 62. Antal, T.; Nowak, M.A.; Traulsen, A. Strategy abundance in 2×2games for arbitrary mutation rates. J. Theor. Biol. 2009,257, 340-344. 63. Allen, B.; Tarnita, C.E. Measures of success in a class of evolutionary models with fixed population size and structure. J. Math. Biol. 2012. 64. Du, J.; Wu, B.; Wang, L. Evolutionary dynamics of multi-player games driven by aspiration. submitted 2013. 65. Eshel, I.; Motro, U. The three brothers’ problem: Kin selection with more than one potential helper. 1. The case of immediate help. Amer. Nat. 1988,132, 550-566. 66. Hauert, C.; Michor, F.; Nowak, M.A.; Doebeli, M. Synergy and discounting of cooperation in social dilemmas. J. Theor. Biol. 2006,239, 195-202. 67. Dionisio, F.; Gordo, I. The tragedy of the commons, the public goods dilemma, and the meaning of rivalry and excludability in evolutionary biology. Evol. Ecol. Res. 2006,8, 321-332. 68. Sigmund, K.; De Silva, H.; Traulsen, A.; Hauert, C. Social learning promotes institutions for governing the commons. Nature 2010,466, 861-863. 69. Gokhale, C.S.; Traulsen, A. Mutualism and evolutionary multiplayer games: revisiting the Red King. Proc. R. Soc. B 2012,279, 4611-4616. 70. Claussen, J.C.; Traulsen, A. Non-Gaussian fluctuations arising from finite populations: Exact results for the evolutionary Moran process. Phys. Rev. E 2005,71, 025101(R). 71. Kurokawa, S.S.; Ihara, Y. Evolution of social behavior in finite populations: A payoff transformation in general n-player games and its implications. Theor. Popul. Biol. 2013,84. 72. Wang, J.; Wu, B.; Ho, A.D.; Wang, L. Evolution of cooperation in multilevel public goods games with community structures. Eur. Phys. Lett. 2011,93, 58001. 73. Du, J.; Wu, B.; Wang, L. Evolution of global cooperation driven by risks. Phys. Rev. E 2012, 85. Appendix For the conditional fixation time given in Equation (11), the linear term in the weak selection expansion is given by ∂ ∂wτA 1w=0 = N−1 X j=1 j X l=1 1 T+ l ∂ρA l ∂w +ρA l ∂ ∂w 1 T+ lw=0 − N−1 X j=1 j X l=1 "ρA l T+ l j X m=l+1 ∆π(m)#w=0 .(32) The weak selection expansion of the fixation probability and the inverse of the positive transition probability read as, ∂ ∂wρA lw=0 =l N2 N−1 X p=1 p X i=1 ∆π(i)−1 N l−1 X p=1 p X i=1 ∆π(i),(33) ∂ ∂w 1 T+ lw=0 =−N l∆π(l).(34) Games 2013,4199 Using these two expressions, we can rewrite the conditional fixation time as, ∂ ∂wτA 1w=0 = N−1 X j=1 j X l=1 N2 l(N−l) l N2 N−1 X p=1 p X i=1 ∆π(i)!− N−1 X j=1 j X l=1 N2 l(N−l) 1 N l−1 X p=1 p X i=1 ∆π(i) | {z } ξ1 − N−1 X j=1 j X l=1 l N N l∆π(l) | {z } ξ2 − N−1 X j=1 j X l=1 l N N2 l(N−l) j X m=l+1 ∆π(m) | {z } ξ3 .(35) Based on the arguments and calculations provided previously in [28,52] we can simplify ξ1and ξ3for the special payoff structure comprising of ai=δik and bi= 0, such that ∆π(l) = H(k, d;k, N). The term ξ2has previously been calculated in [40]. For our special matrix it reads ξ2= N−1 X j=1 j X l=1 l−1 kN−l d−1−k N−1 d−1=N2(d−k)−N(k+ 1) d(d+ 1) .(36) Using the expression for the conditional fixation time as shown in Equation (18), for the above matrix we have, Gk=∂ ∂w τA 1w=0. Thus, putting together the simplified terms ξ1,ξ2and ξ3leads us to the complete expression for Gk, Gk=N N−1 X i=1 H(k, d;i, N) [i(HN−1−Hi−1−HN−i) + NHN−i] −(2 + NHN−1)N2(d−k)−N(k+ 1) d(d+ 1) .(37) c 2013 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/3.0/).