EFTA00748858.pdf

Evolutionary Dynamics in Structured Populations A dissertation presented by Corina Elena Tarnita to The Department of Mathematics in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the subject of Mathematics Harvard University Cambridge, Massachusetts June 2009 EFTA00748858 ®2009 - Corina Elena Tarnita All rights reserved. EFTA00748859 Thesis advisor Author Martin A. Nowak Corina Elena Tarnita Evolutionary Dynamics in Structured Populations Abstract Life is that which evolves. Evolutionary dynamics shape the living world around us. At the center of every evolutionary process is a population of reproducing individu- als. These individuals can be molecules, cells, viruses, multi-cellular organisms or humans with language, hopes and some rationality. The laws of evolution are formulated in terms of mathematical equations. Whenever the fitness of individuals depends on the relative abundance of various strategies or phenotypes in the population, then we are in the realm of evolutionary game theory. Evolutionary game theory is a fairly general approach that helps to understand the interaction of species in an ecosystem, the interaction between hosts and parasites, between viruses and cells, and also the spread of ideas and behaviors in the human population. Here we present recent results on stochastic dynamics in finite sized and structured populations. We derive fundamental laws that determine how natural selection chooses between competing strategies. Two of the results are concerned with the study of multiple strategies and continuous strategies in a well-mixed population. Next we introduce a new way to think of population structure: set-structured populations. Unlike previous structures, the sets are dynamical: the population structure itself is a consequence of evolutionary dynamics. I will present a general mathematical approach for studying any evolutionary game in this structure. Finally, I give a general result which characterizes two-strategy games in any structured population. iii EFTA00748860 Contents Title Page i Abstract iii Table of Contents iv Citations to Previously Published Work vi Acknowledgments vii Dedication x 1 Introduction and summary 1 2 Strategy selection in structured populations 8 2.1 Introduction 8 2.2 Model and results 13 2.3 Proof 15 2.3.1 Linearity 16 2.3.2 Existence of Sigma 18 2.4 Evolution of Cooperation 19 2.5 Examples 21 2.5.1 The well-mixed population 21 2.5.2 Graph structured populations 22 Cycle 22 Star 23 Regular graphs of degree k 24 Different interaction and replacement graphs 26 2.5.3 Gaines in phenotype space 27 2.5.4 Games on sets 29 2.6 Conclusion 30 3 Evolutionary dynamics in set-structured populations 41 4 Supplementary Information for Evolutionary Dynamics in Set Structured Populations 52 4.1 Evolution of cooperation on sets 53 4.2 Belonging to K sets 61 4.2.1 Probability that two individuals have the same strategy 62 iv EFTA00748861 Contents 4.2.2 Average number of sets two individuals have in common 62 4.2.3 Finding the critical ratio 63 4.3 Triggering cooperation 66 4.4 The minimum benefit-to-cost ratio 69 4.5 Finite population size 69 4.6 Numerical simulations 75 4.7 General Payoff Matrix 76 5 Mutation—selection equilibrium in games with multiple strategies 86 5.1 Introduction 86 5.2 Perturbation method 90 5.2.1 Special case: Two strategies 97 5.2.2 Low mutation rates 97 5.3 Examples 99 5.3.1 Cooperators, Defectors, Loners 99 5.3.2 Reversing the ranking of strategies by mutation 101 5.3.3 Cooperators, Defectors, and Tit-for-Tat 104 5.4 Outlook 106 5.4.1 Strong selection 106 5.4.2 More general mutation rates 107 5.4.3 Alternative processes 108 5.5 Discussion 110 6 Mutation-selection equilibrium in games with mixed strategies 114 6.1 Introduction 114 6.2 Mixed games with 2 strategies 119 6.3 Mixed games with two pure strategies 122 6.3.1 A resealed payoff matrix 125 6.3.2 Example: Hawks and Doves 126 6.4 A mixed 3-game: Cooperators, Defectors, Loners 130 6.5 Mixed games with n pure strategies 135 6.6 Conclusion 136 Bibliography 139 EFTA00748862 Citations to Previously Published Work Chapter 1 is part of a review which will be published as: "Gaines, graphs and sets: dynamics and geometry of evolution", M.A. Nowak, C.E. Tarnita, T. Antal. Phil. Trans. Royal Soc., 2010. Chapters 2 and 3 is published as: "Evolutionary dynamics in set structured populations", C.E. Tarnita, T. Antal, H. Ohtsuki, M.A. Nowak. P. Natl. Acad. Sci., 2009. Chapter 4 is published as: "Strategy selection in structured populations", C.E. Tarnita, H. Ohtsuki, T. Antal, F. F i, M.A. Nowak. J. Theor. Biol., doi:10.1016/j.jtbi.2009.03.035, 2009. Chapter 5 is published as: "Mutation-selection equilibrium in games with multiple strategies", T. Antal, A. Traulsen, H. Ohtsuki, C.E. Tarnita, M.A., Nowak. J. Theor. Biol., doi:10.1016/j.jtbi.2009.02.010, 2009. Chapter 6 is submitted as: "Mutation-selection equilibrium in games with mixed strategies", C.E. Tarnita, T. Antal, M.A. Nowak. Submitted to J. Theor. Biol. "Mixed strategies in relaxed social dilemmas", C.E. Tarnita, T. Antal, M.A. Nowak. In preparation. vi EFTA00748863 Acknowledgments I am deeply indebted to my advisor Martin Nowak, for mentoring me with in- spiring enthusiasm and for kindling in me the desire to understand and explore the world. Passionate and brilliant, warm and generous, easygoing and genuine, Martin not only moti- vates me to do great work but shows me how a true scientist should be. I was fortunate to have not only a wonderful advisor, but also a great co-advisor. Tibor Antal helped me make the transition from pure to applied math, showed me how to think in terms of physicists' approximations and, most importantly, taught me to balance my feelings of urgency with patience and persistence. I am also grateful to Karl Sigmund and Cliff Taubes for agreeing to serve on my thesis committee and for providing constructive advice on this work. I would like to thank my collaborators for teaching me so much and for making ev- ery project a very pleasant and rewarding experience: Hisashi Ohtsuki who enthusiastically introduced me to some of the mathematics behind evolutionary dynamics; Yoh Iwasa and Reinhard Buerger, great population geneticists, whom I am lucky to have met and learnt from; Dave Rand and Anna Dreber, amazing resources in experimental economies, psychol- ogy and social behavior; JB Michel, an expert on language and cultural evolution; Feng Fu who quietly does the best simulations one can ask for; Thomas Pfeiffer who covers every other scientific aspect, from prediction markets to reliability of research; Michael Manapat, my high stakes gambler, mathematician officemate, living proof that a scientist can be cool; Radu Berinde who so patiently listened to me explaining my structured populations theo- ries and always provided great insights — eventually lie decided that if he were to describe me in one sentence, it would have to be: "so imagine there are these people who belong to different sets..." I probably wouldn't be doing math right now if it hadn't been for the many wonderful people who taught me so much: Daniels Tarnita, my mathematician mother who educated me in the belief that mathematics can explain the world and set an example of vii EFTA00748864 Acknowledgments viii perseverance and perfectionism; my math teachers Iuliana Coravu and Nicolae Tahiti who taught me to combine passion with discipline; my friends Stefan Hornet and Andrei Jorza who generously taught me a lot of math during my years of college and PhD. I am thankful to my wonderful Harvard math professors and in particular to my first advisor, Joe Harris for making math look simple, elegant and accessible. I am infinitely grateful to Joe for his support and advice and for trusting in my abilities. I am greatly indebted to Shing-Tung Yau, Cliff Taubes and Shlomo Sternberg for their constant encouragement. My work would not have been possible without a beautiful and nurturing envi- ronment as the one at the Program for Evolutionary Dynamics. I am thankful to Jeffrey Epstein for making PED possible and for allowing me to participate in his tireless pursuit of knowledge. And I am indebted to everyone for making PED a wonderful place and for teaching me so much about their great areas of research. Finally, I would like to thank the Chief Administrative Officer, May Huang and her staff, Jordan Bice and Amy Ashbacher, for taking care of the daily functioning of PED — without them, PED would not exist. Along the same lines, I would like to thank their Math department counterparts, Irene Minder, Svetlana Alpert and Susan Gilbert for great advice and for always promptly coming up with solutions. During my years at Harvard, I have been fortunate to have the support of many friends: Bob Doyle - the freshman adviser who has been advising me for 7 years, always with a kind smile and a wise word; Elizabeth Nathans, the former Dean of Freshmen who took it upon herself to make my transition to Harvard life as painless as possible; Chef Raymond Ost from Sandrine's restaurant who provided the secret ingredient and the right spices; my many Romanian friends who made it possible to preserve some of the traditions that I would otherwise greatly miss. In particular, I want to thank Emma Voinescu, my caring friend who has always been there for me. EFTA00748865 Acknowledgments ix Finally, I want to thank my family for their unconditional love and support, for their selflessness in encouraging me to follow my dreams, no matter how far away they may take me, and for making me what I am today. I want to thank my grandparents, Elena and Dumitru Tarnita, for giving me the best possible childhood, for dedicating themselves to me with a love and devotion that will warm my heart for a lifetime. I want to thank my wonderful sister, Roxana, my best friend but also my harshest critic. If I am thankful to my mother, Daniela, for educating me in the spirit that mathematics is the most important thing, I want to thank my father, Dan, a medical doctor, for tirelessly showing me that there are many other fascinating things in life. In this thesis, I am attempting to show that mathematics can explain some of them. EFTA00748866 To my parents x EFTA00748867 Chapter 1 Introduction and summary An evolving population consists of reproducing individuals, which are information carriers. When they reproduce, they pass on their information. New mutants arise, if this process is subject to mistakes. Natural selection emerges if mutants reproduce at different rates and compete for limiting resources. Therefore, the basic ingredients of evolutionary dynamics are very simple. The two most important media for carrying forward the information of the evo- lutionary processes on earth are biological polymers (such as DNA and RNA) and human language. The first give rise to genetic evolution, the second to cultural evolution. The mathematical approaches that we discuss below can be interpreted within either of these two domains. There is also a non-linguistic cultural evolution: we can imitate behavioral patterns without talking about them. Evolutionary game theory was originally designed as a tool for studying animal behavior but has become a general approach that transcends almost every aspect of evo- lutionary biology. Evolutionary game dynamics include the competition of species in an ecosystem, the evolution of virulence in host-parasite interactions, the interaction between 1 EFTA00748868 Chapter 1: Introduction and summary 2 viruses and cells of the immune system, the competition between phages for bacterial cells, the evolution of metabolic pathways and evolution of human language. The dynamical interactions in any group of humans with bonding, economic ex- changes, learning from each other and exploration of new strategies represent evolutionary games. Classical game theory was invented as a mathematical tool for studying economic and strategic decisions of humans. Evolutionary game theory has added the framework of a population of players and the idea that the payoff is interpreted as fitness. These two concepts naturally lead to a dynamical approach. Traditional evolutionary game theory uses differential equations to describe deter- ministic dynamics in well-mixed and infinitely large populations. However, infinitely large, well-mixed populations and deterministic dynamics are idealizations and can only be seen as first approximations. Real populations have a finite number of individuals, and they are not well-mixed. Typically it is not the case that any two individuals interact equally likely. Instead the spatial distribution of the population makes interactions among neighbors more likely than interactions between distant individuals. The social network in human popula- tions cause friends to interact more often than strangers. These realizations led to spatial approaches to evolutionary game dynamics. Furthermore, evolutionary dynamics are not deterministic but intrinsically stochas- tic. If two mutants have exactly the same fitness, eventually one of them will take over the population, while the other one will become extinct. An advantageous mutant has a certain probability to win, but no certainty. Sometimes even deleterious mutants can prevail. In this thesis we analyze the stochastic dynamics in finite well-mixed and struc- tured populations. All our results are derived in the limit of weak selection, when the game considered has only a small effect on the overall fitness of individual strategies. The thesis is organized as follows. EFTA00748869 Chapter 1: Introduction and summary 3 In Chapter 2 we present the concept of `structural dominance' and introduce the structure coefficient a. We present a general result that holds for almost any 'natural' processes of evolutionary game dynamics in well mixed or structured populations. Consider two strategies, A and B, and the payoff matrix A B Ara b) B c d We show that for weak selection, the condition that A is more abundant than B in the stationary distribution of the mutation-selection process can be written as ea + b c+ crd. Hence, the crucial condition specifying which strategy is more abundant is a linear inequality in the payoff values, a, b, c, d. The structure coefficient, a, can depend on the population structure, the update rule, the population size and the mutation rates, but not on a, b, c, d. Evolutionary dynamics in structured populations can lead to a factors which exceed 1. The diagonal entries of the payoff matrix are then more emphasized relative to the off-diagonal values. This property facilitates the evolution of cooperation. The larger a is the easier it is for cooperators to outcompete defectors. We give a simple relationship between a and the critical benefit-to-cost ratio in a simplified Prisoner's Dilemma game. (War +1 a — (NW —1. This shows that for the purpose of establishing strategy dominance, in the limit of weak selection, it suffices to study one-parameter games. In Chapters 3 and 4 we discuss a new way to think of population structure, based on set memberships. We consider a population of N individuals distributed over AI sets. EFTA00748870 Chapter 1: Introduction and summary 4 To obtain analytical results, we also assume that each individual belongs to exactly K sets, where K ≤ Al. If two individuals belong to the same set, they interact; if they have more than one set in common, they interact several times. An interaction is given by the usual payoff matrix. The system evolves according to synchronous updating (Wright-Fisher process). There are discrete, non-overlapping generations. All individuals update at the same time. The population size is constant. Individuals reproduce proportional to their effective payoffs. An offspring inherits the sets of the parent with probability 1 — v or adopts a random configuration (including that of the parent) with probability v. Any particular configuration of set memberships is chosen with probability v/ (K). Similarly, the offspring inherits the strategy of the parent with probability 1—u; with probability u, he picks a random strategy. Thus, we have a strategy mutation rate, u, and a set mutation rate, v. In particular, we study the evolution of cooperation in such set structured populations. We find the condition for cooperators to be favored over defectors, for large population size and low strategy mutation, to be: b K Al v2 +3v +3 c > Al — K (v + 2) + AI — K v(v +2) For general games, the resulting expression for a is complicated and depends on all param- eters, including the two mutation rates. The expression simplifies for large population size, where the main parameters are the two effective mutation rates p = 2Nu and v = 2Nv as well as Al and K. We find 1+v+p K(v2 +2v+vp)+111(3+2v+p) a — 3+ v+ p K(v2 +2v+va)+M(1+u) Note that sigma is a one humped function of the set mutation rate v. There is an optimum value of v, which maximizes sigma. EFTA00748871 Chapter 1: Introduction and summary 5 For low effective strategy mutation rate (µ —• 0) and effective set mutation rate v >> 1 we obtain the simplified expression of a 2M a = 1 + . Note that for large values of v, sigma decreases with v and increases with Itlf/K. For low effective strategy mutation rate and low effective set mutation rate v —) 0, we obtain the following simplified expression for a If a =1+ 2(1— 2m.) Note that, on the other hand, for low values of v, a increases with v. Hence, there will be an optimum set mutation rate. In Chapter 5 we discuss strategy selection in well-mixed populations. Unlike pre- vious studies which have been mainly concerned with 2 strategy games, we now characterize well-mixed populations with multiple strategies. Let us consider a game with n strategies. The payoff values are given by the n x n payoff matrix A = [a15]. This means that an individual using strategy i receives payoff when interacting with an individual that uses strategy j. Payoff translates into reproductive success. For each updating step, we pick one individual for death at random and one individual for birth proportional to fitness. The offspring of the second individual replaces the first. Hence, the total population size is strictly constant. Next we introduce mutation. With probability 1 — u the strategy of the parent is adopted; with probability u one of the n strategies is chosen at random. Let us introduce the parameter µ = Nu, which is the rate at which the entire population produces mutants. We say that selection favors strategy k, if the abundance of k is greater than the average abundance, 1/n, in the stationary distribution of the mutation-selection process. The following results are derived in Antal et al (2008b) and hold for weak selection and large population size. EFTA00748872 Chapter 1: Introduction and summary 6 For low mutation, µ —) 0, the population almost always consists of only a single strategy. This strategy is challenged by one invading strategy. The invader becomes extinct or takes over the population. Thus, the crucial quantities are the `pairwise dominance measures', + aii — — aji. Selection favors strategy It, if the average over all pairwise dominance measures is positive: 71 Lk = —E(akk aka — nth — au) > 0. For high mutation, µ —) co, the population contains each strategy at roughly the same frequency, 1/n. The average payoff of strategy k is ak = E akiln, while the average payoff of all strategies is a = E j ailn. Strategy it is favored by selection, if its average payoff exceeds that of the population, ak > a. This condition can be written as II 22 = E Daki — aij) > O. 9=1j=1 We note that this condition holds for large mutation rate and any intensity of selection. Interestingly, for any mutation rate, strategy it is favored by selection, if a simple linear combination of (4) and (5) holds: Lk + > 0. In the stationary distribution, strategy k is more abundant than strategy j if Lk + alik > Lj + uHj. The above conditions are useful to quantify strategy selection in general 71 x n games in well- mixed populations. They hold for weak selection, large population size, but any mutation rate. In Chapter 6 we discuss continuous strategies in well-mixed populations. The process is the same as for Chapter 5. However, now we allow mixed strategies. A mixed strategy is given by a stochastic vector p = ...,p,,) with 0 5 pi < 1 and pi +...+p„ = 1. EFTA00748873 Chapter 1: Introduction and summary 7 We denote the set of all such mixed strategies by Sri; this is a simplex in 11.n. The unit vectors e, correspond to the pure strategies. The payoff of a mixed strategy p against a mixed strategy q is given by the function A(p,q) = pAqT. The matrix A is the payoff matrix between the pure strategies, as in Chapter 5. Moreover, we have global mutation rates. Hence, if a mutation occurs, then a mixed strategy is chosen at random from a uniform distribution over the simplex Sr,. We show that for low mutation (ti <G 1/N), strategy p is favored by selection if and only if LP= [A(p, + A(p, — A(q, p) — A (q, (0] dq. The integral on Sr, is given by fs. dq = fol-91 dq,t_i dq2do. For high mutation (u» 1/N), the condition that strategy p is favored by selection is Hp = [A(p, — A(r, q)] dqdr. Sn Sn For any mutation probability u, strategy p is favored by selection if and only if Lp + /dip > 0 where µ = Nu is the mutation rate. Moreover, strategy p is favored over strategy q if and only if Lp + µHp > L, + All these results hold for large, but finite population size, N. They allow a characterization of games with mixed strategies, in the limit of weak selection and global mutation. EFTA00748874 Chapter 2 Strategy selection in structured populations 2.1 Introduction Came theory was invented by John von Neuman and Oskar Morgenstern (1944) to study strategic and economic decisions of humans (Fudenberg Sc Tirole 1991, Binmore 1994, Weibull 1995, Samuelson 1997, Binmore 2007). Evolutionary game theory was introduced by John Maynard Smith in order to explore the evolution of animal behavior (Maynard Smith Si Price 1973, Maynard Smith 1982, Houston & McNamara 1999, McNamara et al 1999, Bshary et al 2008). In the meanwhile, evolutionary game theory has been used in many areas of biology including ecology (May & Leonard 1975, Doebeli & Knowlton 1998), host-parasite interactions (Turner & Chao 1999, Nowak Sc May 1994), bacterial population dynamics (Kerr et al 2002), immunological dynamics (Nowak et al 1995), the evolution of human language (Nowak et al 2002) and the evolution of social behavior of humans ('rivers 1971, Axelrod & Hamilton 1981, Boyd & Richerson 2005, Nowak Sc Sigmund 2005). 8 EFTA00748875 Chapter 2: Strategy selection in structured populations 9 Evolutionary game theory is the necessary tool of analysis whenever the success of one strategy depends on the frequency of strategies in the population. Therefore, evolutionary game theory is a general approach to evolutionary dynamics with constant selection being a special case (Nowak St Sigmund 2004). In evolutionary game theory there is always a population of players. The interac- tions of the game lead to payoffs, which are interpreted as reproductive success. Individuals who receive a higher payoff leave more offspring. Thereby, successful strategies outcompete less successful ones. Reproduction can be genetic or cultural. The traditional approach to evolutionary game theory is based on the replicator equation (Taylor & .Jonker 1978, Hofbauer et al 1979, Zeeman 1980, Hofbauer & Sigmund 1988,1998, 2003, Cressman 2003), which examines deterministic dynamics in infinitely large, well-mixed populations. Many of our intuitions about evolutionary dynamics come from this approach (Hofbauer Sc Sigmund 1988). For example, a stable equilibrium of the replicator equation is a Nash equilibrium of the underlying game. Another approach to evolutionary game theory is given by adaptive dynamics (Nowak & Sigmund 1990, Hofbauer & Sigmund 1990, Metz et al 1996, Dieckman et al 2000) which also assumes infinitely large population size. However if we want to understand evolutionary game dynamics in finite-sized populations, we need a stochastic approach (Riley 1979, Schaffer 1988, Fogel et al 1998, Ficici & Pollack 2000, Alos-Ferrer 2003). A crucial quantity is the fixation probability of strategies; this is the probability that a newly introduced mutant, using a different strategy, takes over the population (Nowak et al 2004, Taylor et al 2004, Imhof Sc Nowak 2006, Nowak 2006a, Traulsen et al 2006, Lessard Sc Ladret 2007, Bomze & Pawlowitsch 2008). In this new approach, the Nash equilibrium condition no longer implies evolutionary stability. There has also been much interest in studying evolutionary games in spatial set- EFTA00748876 Chapter 2: Strategy selection in structured populations 10 tings (Nowak & May 1992, 1993, Ellison 1993, Herz 1994, Lindgren & Nordahl 1994, Ferriere Michod 1996, Killingback & Doebeli 1996, Nalcamaru et al 1997, 1998, Nalcamaru & Iwasa 2005, 2006, van Baalen & Rand 1998, Yamamura et al 2004, Helbing & Wu 2008). Here most interactions occur among nearest neighbors. The typical geometry for spatial games are regular lattices (Nowak et al 1994, Hauert & Doebeli 2004, Szab6 & T5ke 1998, Szab6 et al. 2000), but evolutionary game dynamics have also been studied in continuous space (Hutson & Vickers 1992, 2002, Hofbauer 1999). Evolutionary graph theory is an extension of spatial games to more general popu- lation structures and social networks (Lieberman et al 2005, Ohtsuki et al 2006a,b, Pacheco et al 2006, Szabo & Fath 2007, Taylor et al 2007a, Santos at al 2008, RI et al 2008). The members of the population occupy the vertices of a graph. The edges determine who interacts with whom. Different update rules can lead to very different outcomes of the evolutionary process, which emphasizes the general idea that population structure greatly affects evolutionary dynamics. For example, death-birth updating on graphs allows the evolution of cooperation, if the benefit-to-cost ratio exceeds the average degree of the graph b/c > k (Ohtsuki et al 2006). Birth-death updating on graphs does not favor evolution of cooperation. A replicator equation with a transformed payoff matrix can describe de- terministic evolutionary dynamics on regular graphs (Ohtsuki & Nowak 2006b). There is also a modified condition for what it means to be a Nash equilibrium for games on graphs (Ohtsuki & Nowak 2008). Spatial models have also a long history of investigation in the study of ecosystems and ecological interactions (Levin & Paine 1974, Durrett 1988, Hassel et al 1991, Durrett & Levin 1994). There is also a literature on the dispersal behavior of animals (Hamilton & May 1977, Comins et al 1980, Gandon & Rousset 1999). Boerlijst & Hogeweg (1991) studied spatial models in prebiotic evolution. Evolution in structured populations can also EFTA00748877 Chapter 2: Strategy selection in structured populations 11 be studied with the methods of inclusive fitness theory (Seger 1981, Grafen 1985, 2006, Queller 1985, Taylor 1992b, Taylor & Frank 1996, Frank 1998, Rousset & Billiard 2000, Rousset 2004, Taylor et al 2000, 2007b). In this paper, we explore the interaction between two strategies, A and B, given by the payoff matrix A B Ara b) B c d (2.1) We consider a mutation-selection process in a population of fixed size N. Whenever an individual reproduces, the offspring adopts the parent's strategy with probability 1 — u and adopts a random strategy with probability it. We say that strategy A is selected over strategy B, if it is more abundant in the stationary distribution of the mutation-selection process. We call this concept `strategy selection'. In the limit of low mutation (v. —) 0), the stationary distribution is non-zero only for populations that are either all-A or all-B. The system spends only an infinitesimal small fraction of time in the mixed states. In this case, the question of strategy selection reduces to the comparison of the fixation probabilities, PA and Pn (Nowak et al 2004). Here, PA is the probability that a single A mutant introduced in a population of N — 1 many B players generates a lineage of offspring that takes over the entire population. In contrast, the probability that the A lineage becomes extinct is 1 — pA. Vice versa, Pa denotes the probability that a single B mutant introduced in a population of N —1 many A players generates a lineage that takes over the entire population. The fixation probabilities measure global selection over the entire range of relative abundances. The condition for A to be favored over B in the limit of low mutation is PA > PR. (2.2) EFTA00748878 Chapter 2: Strategy selection in structured populations 12 For positive mutation rate (0 < u < 1), the stationary distribution includes both homogeneous and mixed states. In this case, strategy selection is determined by the in- equality (x) > 1/2. (2.3) Here x is the frequency of A individuals in the population. The angular brackets denote the average taken over all states of the system, weighted by the probability of finding the system in each state. In the limit of low mutation, (2.3) is equivalent to (2.2). In this paper we focus on structured populations and the limit of weak selection. We analyze (2.3) to deduce that the condition for strategy A to be favored over strategy B is equivalent to aa + b > + ad. (2.4) The parameter a depends on the population structure, the update rule and the mutation rate, but it does not depend on the payoff values a, b,c,d. Thus, in the limit of weak selection, strategy selection in structured populations is determined by a linear inequality. The effect of population structure can be summarized by a single parameter, a. Therefore, we call inequality (2.5) the `single-parameter condition'. Note that a =1 corresponds to the standard condition for risk-dominance (Harsanyi Selten 1988). If a > 1 then the diagonal entries of the payoff matrix, a and d, are more important than the off-diagonal entries, b and c. In this case, the population structure can favor the evolution of cooperation in the Prisoner's Dilemma game, which is defined by c > a > d > b. If a > 1 then the population structure can favor the Pareto-efficient strategy over the risk-dominant strategy in a coordination game. A coordination game is defined by a > c and b < d. Strategy A is Pareto efficient if a > d. Strategy B is risk-dominant if a + b < c + d. If a < 1 then the population structure can favor the evolution of spite. EFTA00748879 Chapter 2: Strategy selection in structured populations 13 The paper is structured as follows. In Section 2 we present the model, the main result and the necessary assumptions. In Section 3 we give the proof of the single-parameter condition, which holds for weak selection and any mutation rate. In Section 4 we show the relationship between a and the critical benefit-to-cost ratio for the evolution of cooperation. An interesting consequence is that for the purpose of calculating a it suffices to study games that have simplified payoff matrices. Several specific consequences are then discussed. In Section 5 we present several examples of evolutionary dynamics in structured populations that lead to a single-parameter condition. These examples include games in the well-mixed population, games on regular and heterogeneous graphs, games on replacement and inter- action graphs, games in phenotype space and games on sets. Section 6 is a summary of our findings. 2.2 Model and results We consider stochastic evolutionary dynamics (with mutation and selection) in a structured population of finite size, N. Individuals adopt either strategy A or B. Individuals obtain a payoff by interacting with other individuals according to the underlying population structure. For example, the population structure could imply that interactions occur only between neighbors on a graph (Ohtsuki et al 2006), inhabitants of the same island or individ- uals that share certain phenotypic properties (Antal et al 2008). Based on these interactions, an average (or total) payoff is calculated according to the payoff matrix (2.1). We assume that the payoff is linear in a, b, c, d, with no constant terms. For instance, the total payoff of an A individual is [a x (number of A-interactants) + b x (number of B-interactants)]. The effective payoff of an individual is given by 1 + w • Payoff. The parameter w denotes the intensity of selection. The limit of weak selection is given by w -. 0. EFTA00748880 Chapter 2: Strategy selection in structured populations 14 Reproduction is subject to mutation. With probability u the offspring adopts a random strategy (which is either A or B). With probability 1 — u the offspring adopts the parent's strategy. For u = 0 there is no mutation, only selection. For u = 1 there is no selection, only mutation. If 0 < u < 1 then there is mutation and selection. A state S of the population assigns to each player a strategy (A or B) and a 'location' (in space, phenotype space etc). A state must include all information that can affect the payoffs of players. For our proof, we assume a finite state space. We study a Markey process on this state space. We denote by 1j1 the transition probability from state Si to state Si. These transition probabilities depend on the update rule and on the effective payoffs of individuals. Since the effective payoff is of the form 1 + to • Payoff and the payoff is linear in a, b, c, d, it follows that the transition probabilities are functions Pii(wa, wb,wc, wd). We show that Theorem 1. Consider a population structure and an update rule such that 0) the transition probabilities are infinitely differentiable at w = 0 (ii) the update rule is symmetric for the two strategies and (iii) in the game given by the matrix (g 01), strategy A is not disfavored. Then, in the limit of weak selection, the condition that strategy A is favored over strategy B is a one parameter condition: aa+b>c+ad (2.5) where a depends on the model and the dynamics (population structure, update rule, the mutation rates) but not on the entries of the payoff matrix, a, b, c, d. EFTA00748881 Chapter 2: Strategy selection in structured populations 15 Let us now discuss the three natural assumptions. Assumption (1). The transition probabilities are infinitely differentiable at w = 0. We require the transition probabilities Pii(wa, wb, wc, wd) to have Taylor expansions at w = 0. Examples of update rules that satisfy Assumption (i) include: the death birth (DB) and birth-death (BD) updating on graphs (Ohtsuki et al 2006), the syn- chronous updating based on the Wright-Fisher process (Antal et al 2008, Tarnita et al 2009) and the pairwise comparison (PC) process (Traulsen et al 2007). Assumption (ii). The update rule is symmetric for the two strategies. The update rule differentiates between A and B only based on payoff. Relabeling the two strategies and correspondingly swapping the entries of the payoff matrix must yield symmetric dynamics. This assumption is entirely natural. It means that the difference between A and B is fully captured by the payoff matrix, while the population structure and update rule do not introduce any additional difference between A and B. Assumption In the game given by the matrix (g 01), strategy A is not disfavored. We will show in the proof that the first two assumptions are sufficient to obtain a single-parameter condition. We need the third assumption simply to determine the direction of the inequality in this condition. Thus, if (iii) is satisfied, then the condition that A is favored over B has the form (2.5). Otherwise, it has the form aa+b c c+ad. 2.3 Proof In the first part of the proof we will show that for update rules that satisfy our assumption (i) in Section 2, the condition for strategy A to be favored over strategy B is EFTA00748882 Chapter 2: Strategy selection in structured populations 16 linear in a, b, c, d with no constant terms. More precisely, it can be written as kja + Ic2b > k3c + 14d. (2.6) Here 14, k2, k3, k1 are real numbers, which can depend on the population structure, the update rule, the mutation rate and the population size, but not on the payoff values a, b, c, d. In the second part of the proof we will show that for update rules that also satisfy our symmetry assumption (ii) in Section 2, this linearity leads to the existence of a a. Furthermore, using assumption (iii) we show that the condition that A is favored over B becomes cra+b>c+cd. (2.7) 2.3.1 Linearity As we already mentioned, we study a Markey process on the state space and we are concerned with the stationary probabilities of this process. A more detailed discussion of these stationary probabilities can be found in Appendix B. In a state S, let xs denote the frequency of A individuals in the population. Then the frequency of B individuals is 1 — xs. We are interested in the average frequency of A individuals, the average being taken over all possible states weighted by the stationary probability that the system is in those states. Let us denote this average frequency by (x). Thus (x) = xsirs. (2.8) S where rs is the probability that the system is in state S. The condition for strategy A to be favored over strategy B is that the average frequency of A is greater than 1/2 (2.9) This is equivalent to saying that, on average, A individuals are more than 50%. EFTA00748883 Chapter 2: Strategy selection in structured populations 17 We analyze this condition in the limit of weak selection to -. 0. The frequency xs of A individuals in state S does not depend on the game; hence, it does not depend on to. However, the probability irs that the system is in state S does depend on to. For update rules satisfying assumption (0, we show in Appendix B that irs is infinitely differentiable as a function of to. Thus, we can write its Taylor expansion at to = 0 ( irs = irs0) +wrrg~l + O(w2). (2.10) The (0) superscript refers to the neutral state w = 0 and 4 ) = thrs/dw evaluated at to = 0. The notation O(w2) denotes terms of order w2 or higher. They are negligible for w —) 0. Hence, we can write the Taylor expansion of the average frequency of A (x) E xsirr + w E xs741) + (9(w2). (2.11) Since rr is the probability that the neutral process (i.e. when w = 0) is in state 51, the first sum is simply the average number of A individuals at neutrality. This is 1/2 for update rules that satisfy Assumption (ii) because in the neutral process, A and B individuals are only differentiated by labels. Thus, in the limit of weak selection, the condition (2.9) that A is favored over B becomes E xs,r(si) > 0. (2.12) S As we already mentioned, the frequency xs of A individuals in state S does not depend on the game. However, 4 ) does depend on the game. We will show in Appendix B that xsa) is linear in a, b, c, d with no constant terms. Hence, from (2.12) we deduce that our condition for strategy A to be favored over strategy B is linear in a, b, c, d and is of the form (2.6). EFTA00748884 Chapter 2: Strategy selection in structured populations 18 2.3.2 Existence of Sigma We have thus shown that for structures satisfying assumption (i), the condition for strategy A to be favored over strategy B has the form (2.6): kia + k2b > k3c + k4d. For structures which moreover satisfy our symmetry condition (assumption (ii)), we obtain the symmetric relation by simply relabeling the two strategies. Thus, strategy B is favored over strategy A if and only if kid + k2e > k3b + kg/. (2.13) Since both strategies can not be favored at the same time, strategy A must be favored if and only if k4a + k3b > k2c + kid. (2.14) Since both conditions (2.6) and (2.14) are if and only if conditions that A is favored over B, they must be equivalent. Thus, it must be that (2.14) is a scalar multiple of (2.6), so there must exist some A > 0 such that /4 = Aki = A2k4 and k3 = Ake = A2k3. Hence, we conclude that A = 1 and that ki = = k and k2 = k3 = k'. So the condition that A is favored over B becomes ka > kd. (2.15) Note that this condition depends only on the parameter a = k/k'. Thus, in gen- eral, the condition that A is favored over B can be written as a single-parameter condition. However, one must exercise caution in dividing by le because its sign can change the direc- tion of the inequality. This is where we need assumption Assumption (iii) holds if and only if k' > 0 and then we can rewrite (2.15) as ea+b>e+crd. (2.16) If (iii) doesn't hold, then k' < 0 and hence (2.15) becomes as + b < c + ad. EFTA00748885 Chapter 2: Strategy selection in structured populations 19 Note that a could also be infinite (if k' = 0) and then the condition that A is favored over B reduces to a > d. If a = 0 then the condition is simply b > c. 2.4 Evolution of Cooperation In this section we find a relationship between the critical benefit-to-cost ratio for the evolution of cooperation (Nowak 2006b) and the parameter a. In a simplified version of the Prisoner's Dilemma game a cooperator, C, pays a cost, c, for another individual to receive a benefit, b. We have b > c > 0. Defectors, D, distribute no benefits and pay no costs. We obtain the payoff matrix C C b — c D b D 0 (2.17) For structures for which condition (2.5) holds, we can apply it for payoff matrix (2.17) to obtain cr(b — c) — c > b. (2.18) For a > 1 this condition means that cooperators are more abundant than defectors whenever the benefit-to-cost ratio b/c is larger than the critical value (b\* a + 1 kcj Alternatively, a can be expressed by the critical (bier ratio as (bier + 1 a — (b/c)* — (2.19) (2.20) Here we have a > 1. Note that even without the assumption b > c > 0, the same a is obtained from (2.18), only some care is required to find the correct signs. EFTA00748886 Chapter 2: Strategy selection in structured populations 20 Thus, for any population structure and update rule for which condition (2.5) holds, if the critical benefit-to-cost ratio is known, we can immediately obtain a and vice versa. For example, for DB updating on regular graphs of degree k we know that (Nor = k (Ohtsuki et al 2006). Using equation (2.20), this implies a = (k + 1)fik — 1) which is in agreement with equation (2.27). This demonstrates the practical advantage of relationship (2.20). In order to derive o for the general game (2.1), it suffices to study the specific game (2.17) and to derive the critical benefit-cost ratio, (bie)". Then (2.20) gives us the answer. Thus Corollary 1. In the limit of weak selection, for all structures for which strategy dominance is given by a single parameter condition (2.5), for the purpose of studying strategy domi- nance, it suffices to analyze one-parameter games (eg. the simplified Prisoner's Dilemma). The practical advantage comes from the fact that it is sometimes easier to study the specific game (2.17) than to study the general game (2.1). Specifically, using (2.17) often spares the calculation of probabilities that three randomly chosen players share the same strategy (for example, coefficient ti in Antal et al, 2008). Wild and Traulsen (2007) argue that the general payoff matrix (2.1) allows the study of synergistic effects between players in the weak selection limit, as opposed to the simplified matrix (2.17) where such effects are not present. Here we demonstrated that these synergistic effects do not matter if we are only interested in the question whether A is more abundant than B in the stationary distribution of the mutation-selection process. Of course, our observation does not suggest that the analysis of general games, given by (2.1), can be completely replaced by the analysis of simpler games, given by (2.17). Questions concerning which strategies are Nash equilibria, which are evolutionarily stable or when we have coexistence or bi-stability can only be answered by studying the general matrix. For such analyses see Ohtsuki & Nowak (2006, 2008) or Taylor & Nowak (2007). EFTA00748887 Chapter 2: Strategy selection in structured populations 21 Note also that instead of the simplified Prisoner's Dilemma payoff matrix, we can also consider other types of simplified payoff matrices in order to calculate a. Two examples are ( 10 06 2.5 Examples or r1c 0 ) (2.21) Let us consider a game between two strategies A and B that is given by the payoff matrix (2.1). We study a variety of different population structures and always observe that for weak selection the condition for A to be favored over B can be written in the form on + b> c + ad. For each example we give the value of a. The derivations of these results have been given in papers which we cite. For the star we present a new calculation. These observations have led to the conjecture that for weak selection the effect of population structure on strategy selection can `always' be summarized by a single parameter, a. Moreover, for some of the examples, we use the Corollary to find the parameter a for structures where only the Prisoner's Dilemma has been studied. Such structures include: the regular graph of degree k and the different interaction and replacement graphs when the population size is not much larger than the degree, as well as the phenotype space. 2.5.1 The well-mixed population As first example we consider the frequency dependent Moran process in a well mixed population of size N (Nowak et al 2004, Taylor et al 2004, Nowak 2006a) (Fig.la). In the language of evolutionary graph theory, a well-mixed population corresponds to a complete graph with identical weights. Each individual interacts with all other N — 1 individuals equally likely and obtains an average (or total) payoff. For both DB and BD EFTA00748888 Chapter 2: Strategy selection in structured populations 22 updating we find for weak selection and any mutation rate N — 2 a N (2.22) Hence, for any finite well-mixed population we have a < 1. In the limit N co, we obtain a = 1, which yields the standard condition of risk-dominance, a + b > c + d. For a wide class of update rules — including pairwise comparison (Traulsen et al 2007) - it can be shown that (2.22) holds for any intensity of selection and for any mutation rate (Antal et al 2009). The a given by (2.22) can also be found in Handed et al (1993), who study a process that is stochastic in the generation of mutants, but deterministic in following the gradient of selection. 2.5.2 Graph structured populations In such models, the players occupy the vertices of a graph, which is assumed to be fixed. The edges denote links between individuals in terms of game dynamical interac- tion and biological reproduction. Individuals play a game only with their neighbors and an average (or total) payoff is calculated. In this section we consider death-birth (DB) updating and birth-death (BD) updating. In DB updating, at any one time step, a random individual is chosen to die, and the neighbors compete for the empty spot, proportional to their effective payoffs. In BD updating, at any one time step, an individual is chosen to reproduce proportional to effective payoff; his offspring replaces randomly one of the neighbors (Ohtsuki et al 2006). Cycle Let us imagine N individuals that are aligned in a one dimensional array. Each individual is connected to its two neighbors, and the ends are joined up (Fig. lb). The cycle EFTA00748889 Chapter 2: Strategy selection in structured populations 23 is a regular graph of degree k = 2. Games on cycles have been studied by many authors including Ellison (1993), Nalcamaru et al (1997), Ohtsuki et al (2006) and Ohtsuki & Nowak (2006a). The following result can be found in Ohtsuki Sc Nowak (2006a) and holds for weak selection. For DB updating and low mutation Cu —) 0) we have 3N — 8 a— (2.23) Note that a is an increasing function of the population size, N, and converges to a = 3 for large N. We have also performed simulations for DB on a cycle with non-vanishing mutation (Fig. 2a). We confirm (2.23) and also find that a depends on the mutation rate, u. For BD updating we have N — 2 N (2.24) Hence, for BD updating on a cycle we obtain the same a-factor as for the well-mixed population, which corresponds to a complete graph. The cycle and the complete graph are on the extreme ends of the spectrum of population structures. Among all regular graphs, the cycle has the smallest degree and the complete graph has the largest degree, for a given population size. We conjecture that the a-factor given by (2.24) holds for weak selection on any regular graph. We have also performed simulations for BD on a cycle with non-vanishing mutation (Fig.3a). They confirm (2.24). Star The star is another graph structure, which can be calculated exactly. There are N individuals. One individual occupies the center of the star and the remaining N — 1 EFTA00748890 Chapter 2: Strategy selection in structured populations 24 individuals populate the periphery (Fig.1c). The center is connected to all other individuals and, therefore, has degree k = N — 1. Each individual in the periphery is only connected to the center and, therefore, has degree k = 1. The average degree of the star is given by k = 2(N - 1)/N. For large population size, N, the star and the cycle have the same average degree. Yet the population dynamics are very different. The calculation for the star for both BD and DB updating is shown in Appendix A. For DB updating on a star we find a = 1. (2.25) This result holds for weak selection and for any population size N > 3 and any mutation rate u. Simulations for the star are in agreement with this result (Fig.2b). For BD updating on a star we find N3 — 4N2 + 8N - 8 a- N3 - 2N2 + 8 (2.26) This result holds in the limit of low mutation, u 0. Note also that in the limit of N large we have a = 1. Simulations confirm our result (Fig.3b). Regular graphs of degree k Let us now consider the case where the individuals of a population of size N occupy the vertices of a regular graph of degree k > 2. Each individual is connected to exactly k other individuals (Fig. 1d). For DB updating on this structure, Ohtsuki et al (2006) obtain (see equation 24 in their online material) k +1 cr - k — 1 (2.27) EFTA00748891 Chapter 2: Strategy selection in structured populations 25 This result holds for weak selection, low mutation and large population size, N >> k. The parameter a depends on the degree of the graph and is always larger than one. For large values of k, a converges to one. The limit of large k agrees with the result for the complete graph, which corresponds to a well-mixed population. For BD updating on a regular graph of degree k cc N, in the limit of weak selection and low mutation, Ohtsuki et al (2006) find a = 1. (2.28) Hence, for any degree k, we have the simple condition of risk-dominance. Population struc- ture does not seem to affect strategy selection under BD updating for weak selection and large population size. Our proof of the linear inequality is not restricted to homogeneous graphs. Random graphs (Bollobas 1995) also satisfy our assumptions, and therefore we expect the single parameter condition to hold. We have performed computer simulations for a random graph with N = 10 and average degree k = 2. We find a linear condition with a = 1.636 for DB updating and a = 0.559 for BD updating (see Fig.2d, 3d). For a regular graph of degree k, the calculation of Ohtsuki et al (2006) is only applicable if the population size is much larger than the degree of the graph, N >> k. For general population size N however, we can obtain the a parameter using our corollary and the results of Taylor et al (2007a) and Lehmann et al (2007). They obtained a critical benefit-to-cost ratio of (bier = — 2)/(N/k — 2). Using the relationship (2.20), we obtain a — (k + 1)N — 4k (k — 1)N (2.29) EFTA00748892 Chapter 2: Strategy selection in structured populations 26 As a consistency check, taking N —• co in (2.29) leads to (2.27). Moreover, setting k = 2 in (2.29) leads to (2.23), and setting k = N — 1 in (2.29) agrees with (2.22), as expected. Computer simulations for a regular graph with k = 3 and N = 6, for mutation rate ae = 0.1 suggest that a = 0.937. The corresponding prediction of (2.29) for low mutation is a = 1. Thus we conclude that a depends on the mutation rate u (Fig.2c). For the BD updating on a regular graph with general population size N, we can similarly obtain the relevant a from the result of Taylor et al (2007a). For the Prisoner's Dilemma they find a critical benefit-to-cost ratio of (b/c)* = —1/(N — 1). Hence, using relationship (2.20) we obtain — 2 a — NN (2.30) Note that the results In Taylor et al (2007a) hold for any homogeneous graph that satisfies certain symmetry conditions (`bi-transitivity'). Hence, for BD updating on a wide class of graphs, the condition for strategy dominance is the same as the risk-dominance condition in a well-mixed population. Computer simulations for a regular graph with k = 3 and N = 6, for mutation rate u = 0.1 suggest that a = 0.601. The corresponding prediction of (2.29) for low mutation is a = 0.666. Thus we conclude that a depends on the mutation rate u (Fig.3c). Different interaction and replacement graphs Individuals could have different neighborhoods for the game dynamical interaction and for the evolutionary updating. In this case, we place the individuals of the population on the edges of two different graphs (Ohtsuki et al 2007). The interaction graph determines who meets whom for playing the game. The replacement graph determines who learns from EFTA00748893 Chapter 2: Strategy selection in structured populations 27 whom (or who competes with whom) for updating of strategies. The vertices of the two graphs are identical; the edges can be different (Fig. le). Suppose both graphs are regular. The interaction graph has degree h. The re- placement graph has degree g. The two graphs define an overlap graph, which contains all those edges that the interaction and replacement graph have in common. Let us assume that this overlap graph is regular and has degree 1. We always have I < min{ h,g}. The following results hold for weak selection and large population size (Ohtsuki et al 2007): For DB updating we find: gh + a — (2.31) gh — For BD updating we find a = 1. (2.32) Again BD updating does not lead to an outcome that differs from well-mixed populations. For different replacement and interaction graphs with general population size, N, we can obtain a via the critical benefit-to-cost ratio in the Prisoner's Dilemma game (2.17). Using the result of Taylor et al. (2007), we obtain (bier = (N — 2)/(Nligh — 2). Hence, we have a (gh + ON — 4gh (gh — ON As a consistency check, g=h=f =k reproduces (2.29). 2.5.3 Games in phenotype space (2.33) Antal et al (2008) proposed a model for the evolution of cooperation based on phenotypic similarity. In addition to the usual strategies A and B, each player also has a phenotype. The phenotype is given by an integer or, in other words, each player is EFTA00748894 Chapter 2: Strategy selection in structured populations 28 positioned in a one dimensional discrete phenotype space (Fig.lf). Individuals interact only with those who share the same phenotype. The population size is constant and given by N. Evolutionary dynamics can be calculated for DB updating or synchronous updating (in a Wright-Fisher type process). There is an independent mutation probability for the strategy of players, u, and for the phenotype of players, v. When an individual reproduces, its offspring has the same phenotype with probability 1 — 2v and mutates to either one of the two neighboring phenotypes with equal probability v. During the dynamics, the whole population stays in a finite cluster, and wanders together in the infinite phenotype space (Moran 1975, Kingman 1976). The resulting expression for a is derived using the corollary. It is complicated and depends on all parameters, including the two mutation rates, u and v. The expression simplifies for large population sizes, where the main parameters are the scaled mutation rates µ = Nu, v = Nv for BD updating (orµ = 2Nu, v = 2Nv for synchronous updating). It turns out that a is a monotone decreasing function of µ, and a monotone increasing function of v. Hence cooperation is favored (larger a) for smaller strategy mutation rate and larger phenotypic mutation rate. In the optimal case for cooperation, µ —) 0, sigma becomes only a function of the phenotypic mutation rate 1 + 4v (+ + 12v) a — 2 + 4v 3+4v (2.34) The largest possible value of sigma is obtained for very large phenotypic mutation rate v —) co, where cr=l+V5. (2.35) This is the largest possible sigma for games in a one-dimensional phenotype space. Note that this example has seemingly an infinite state space, which is not some- thing we address in our proof, but a subtle trick turns the state space into a finite one. A EFTA00748895 Chapter 2: Strategy selection in structured populations 29 detailed description can be found in Antal et al (2008). 2.5.4 Games on sets Tarnita et al (2009) propose a model based on set memberships (Fig.1g). They consider a population of N individuals distributed over Al sets. lb obtain analytical results, we also assume that each individual belongs to exactly K sets, where K < Al. If two individuals belong to the same set, they interact; if they have more than one set in common, they interact several times. An interaction is an evolutionary game given by (2.1). The system evolves according to synchronous updating (Wright-Fisher process). There are discrete, non-verlapping generations. All individuals update at the same time. The population size is constant. Individuals reproduce proportional to their effective payoffs. An offspring inherits the sets of the parent with probability 1 — v or adopts a random configuration (including that of the parent) with probability v. Any particular configuration of set memberships is chosen with probability vg.htif.). Similarly, the offspring inherits the strategy of the parent with probability 1—u; with probability it, he picks a random strategy. Thu.s, we have a strategy mutation rate, it, and a set mutation rate, v. The resulting expression for a is complicated and depends on all parameters, in- cluding the two mutation rates. The expression simplifies for large population size, where the main parameters are the two effective mutation rates µ = 2Nu and v = 2Nv as well as Al and K. We find = 1+ v + K(ti2 +2v+ up) + M(3 + 2v + µ) 3+v+µ K(v2 +2v-kust)+M(1+A) (2.36) Note that sigma is a one humped function of the set mutation rate v. There is an optimum value of v, which maximizes sigma. For low effective strategy mutation rate (µ 0) and effective set mutation rate EFTA00748896 Chapter 2: Strategy selection in structured populations 30 v 1 we obtain the simplified expression of a 2 M a=1+=1. (2.37) Note that for large values of xi, sigma decreases with v and increases with M/K. For low effective strategy mutation rate and low effective set mutation rate v —. 0, we obtained the following simplified expression for a K a= 1 + v3-(1 — I) (2.38) Note that, on the other hand, for low values of v, a increases with v. Hence, there will be an optimum set mutation rate. 2.6 Conclusion We have studied evolutionary game dynamics in structured populations. We have investigated the interaction between two strategies, A and B, given by the payoff matrix A B A (a b) B c d We have shown that the condition for A to be more abundant than B in the stationary distribution of the mutation-selection process can be written as a simple linear inequality (2.39) cra+b>c+ad. (2.40) This condition holds for all population structures that fulfill three natural assumptions, for any mutation rate, but for weak selection. The parameter a captures the effect of population structure on `strategy selection'. We say that `strategy A is selected over strategy B' if it is more abundant in the stationary distribution of the mutation-selection process. It is EFTA00748897 Chapter 2: Strategy selection in structured populations 31 important to note that a does not capture all aspects of evolutionary dynamics in structured populations, but only those that determine strategy selection. The single parameter, a, quantifies the degree to which individuals using the same strategy are more likely (a > 1) or less likely (a < 1) to interact than individuals using different strategies. Therefore a describes the degree of positive or negative assortment among players who use the same strategy (for the purpose of analyzing strategy selection). Note that our theory does not imply that a must be positive; negative values of a are possible in principle, although for all of the examples presented in this paper we have a > 0. The value of a can depend on the population structure, the update rule, the population size, the mutation rate, but it does not depend on the entries of the payoff matrix. For each particular problem the specific value of a must be calculated. Here we have shown that there always exists a simple linear inequality with a single parameter, a, given that some very natural assumptions hold. Appendix A : Calculations for the star A.1. DB updating We consider a star structured population of size N. A hub is the node lying in the center that is connected to the other N — 1 nodes, each of which is called a leaf. Each leaf is connected only to the hub. We consider the two strategies, A and B. A state of the population is fully described by the number of A-players in the hub and the number of A-players in the leaves. Thus, for the star with N nodes we have 2N states which we will denote by (0, i) and (1, i), where i = 0, N —1 is the number of A players on the leaves. (0, i) means that there is a EFTA00748898 Chapter 2: Strategy selection in structured populations 32 B in the hub; (1,i) means that there is an A in the hub. DB updating on a star satisfies our assumptions (i) and (ii). It can be shown (as we do in general in Appendix B) that for the star, ,41) is linear in a, b, c, d. Thus, we know that a single parameter condition must be satisfied for the star. However, it is hard to calculate directly what 741) is for all states S. We use the symmetry of the star to deduce the a for any mutation and weak selection. Then, for DB updating we can write the following transition probabilities: P(0), 0 —) (0, i — 1)) = Tri — P(0,0 —) Ai +1)) — uN N-1 (2.41) P( (0, 0 —) (1, = + (1 — a) N(N 1) + wN — — 1 N —1 (b d)) P ((O, —) (0,i)) = (1 — u)N 1 (1+ (1+ wr i_ i (d b))) P((1,i) —) (1,i — 1)) = urii — P((1,i) —) (1,i +1)) — N N-1 Pom (0,0) = w + (1 u) N(N i — 1)V wN — 1(e a)) N — — 1 I P((1,i) (1,1)) = (1— /Orli (1+ 1 1 1 l+w N—i 1 (a c))) — N So all these transition probabilities don't depend on a, b, c, d independently, but in fact on b — d and a — a Thus, irs, the probabilities of finding the system in each state, also depend only on a — c and b — d, and not on a, b, c, d independently. Hence, we conclude that our expression (2.12) which gives the sigma condition depends on a — c and b — d linearly. Thus, it must be of the form: (2.42) (a — c)g(N, u) + — d)h(N,u)> 0 (2.43) where g and h are functions of the parameters N and u. EFTA00748899 Chapter 2: Strategy selection in structured populations 33 However, this has to be precisely the sigma relation for the star (since it is derived from (2.12)), and hence must be identical to aa+b> c+od (and here we know that a > 0). This implies that the coefficients of a and —d must be equal (and respectively those of b and —c). Hence we conclude that g(N,u) = mN,u) and hence a = 1, for any population size N and any mutation rate u. A.2. BD updating Let xid be the probability that A fixates in the population given initial state is (i, j). Also, let plj, gip and di be the transition probabilities as in the diagram below. 4,o 1- ; P; X0,j-1 -e- 2 0,j X0,j-1-1 xi,o 2 1,1-1 (4118; x j -1- 2 1,1+1 v 1-11-s; We normalize these probabilities as follows: _ Pi qi 11 111 = + j, 02i j _ if/ - p'j + 2 3 2 1,N-1 .9 • 3 Si = 2 3 (2.44) Now we have the following diagram. We have pi + q1 =1 and rj + sj = 1 there. X0,j-1 X0,j x1,0 2 1,1-1 2 0,1+1 x1,1+1 rj 21,N-1 EFTA00748900 Chapter 2: Strategy selection in structured populations 34 Direct calculation shows = 41 / [r ib / J=. efi li=i (2.45) N-2 arr -1 N-2 Pi Er M + xio = ro/ 42 (II —) (1 —) 2=1 i=i ri i= 1 r, [ For BD updating, we obtain iV — 1 2" — + N2 — 2N + 2 1 21,0 — + °(w) (2.46) N2 — 2N + 2 where (N — 1)x0 N,1 + x1,0 1 A2b — A3e — .3/4 d)+ O(w2 ), Pa= + wzoia (N - 1)2 Z - 6N2(N2 - 2N + 2) Al = N3 - 3N2 + 5N - 6, A2 = 2N3 - 6N2 + 7N + 6, (2.47) A3 = N3 - 7N + 18, A4 = 2N3 - 9N2 + 19N - 18 The result suggests that a leaf is (N — 1) times more advantageous than the hub. As before we obtain the a-factor as = A1 + A4 N3 — 4N2 + 8N - 8 (2.48) a A2 + A3 N3 - 2N2 + 8 Appendix B: Continuity and Linearity for irs In this Appendix we will show that the probability irs that the system is in state S is continuous at w = 0, infinitely differentiable and moreover that 4 1) is linear in a, b, c, d. We show this for processes satisfying our assumptions. This part of the proof works not only for constant death or constant birth updates, but for any update rules that do not introduce any functions that do not have Taylor expansions at w = 0. EFTA00748901 Chapter 2: Strategy selection in structured populations 35 Note that given the effective payoff function 1+ w • payoff, we introduce w together with a, b, c and d. Thus, our transition probabilities from state Si to state Si will be functions Pii(wa,wb, wc,wd). So, unless we differentiate with respect to w or evaluate at w = const, whenever we have a degree k term in w, it must be accompanied by a degree k term in a, b, c or d and vice versa. Moreover, w can not be accompanied by a constant term, i.e. a term that does not contain a, b, c or d. The probability rs that the system is in state S also depends on w. For our structures and update rules we will now show that rs is continuous and differentiable at = 0. In order to find irs, we need the transition probabilities Pii to go from state Si to state Si. Then the vector of probabilities r(S) is an eigenvector corresponding to eigenvalue 1 of the stochastic matrix P. The matrix P is primitive, i.e. there exists some integer k such that Pk 7 0. This is because we study a selection-mutation process and hence our system has no absorbing subset of states. Since the matrix P is stochastic and primitive, the Perron-Frobenius theorem ensures that 1 is its largest eigenvalue, that it is a simple eigenvalue and that to it, there corresponds an eigenvector with positive entries summing up to 1. This is precisely our vector of probabilities. To find this eigenvector we perform Gaussian elimination (aka row echelon reduc- tion) on the system Pv = v. Since 1 is a simple eigenvalue for P, the system we need to solve has only one degree of freedom; thus we can express the eigenvector in terms of the one free variable, which without loss of generality can be vn: vh = -vnhi, = -vnhi, • • • vn-1 = -vnhn-1 (2.49) The eigenvector that we are interested in is the vector with non-zero entries which sum up EFTA00748902 Chapter 2: Strategy selection in structured populations 36 to 1. For this vector we have 1 = v„(—hi — — hn_i + 1) (2.50) For our structures and update rules, the transition probabilities have Taylor ex- pansions around w = 0 and thus can be written as polynomials in w. As before, since any w is accompanied by a linear term in a, b, c, d, the coefficients of these polynomials have the same degree in a, b, c, d as the accompanying w. Because of the elementary nature of the row operations performed, the elements of the reduced matrix will be fractions of polynomials (i.e. rational functions of w). Thus, hi above are all rational functions of W. Therefore, from (4.89) we conclude that vn must also be a rational function of W. This implies that in our vector of probabilities, all the entries are rational functions . Thus rs is a fraction of polynomials in w which we write in irreducible form. The only way that this is not continuous at W = 0 is if the denominator is zero at W = 0. But in that case, lim,„_,0 aS = oo which is impossible since irs is a probability. Therefore, Ts is continuous at w = 0. Moreover, we can write bos + bisw + O(w2) irs — coS + eigw + O(w2) (2.51) We have obtained this form for ws by performing the following operations: Taylor ex- pansions of the transition probabilities and elementary row operations on these Taylor expansions. Hence, any w that was introduced from the beginning was accompanied by linear terms in a, b, c, d and no constants, and due to the elementary nature of the above operations, nothing changed. So boS and cos contain no a, b, c, d terms whereas bls and els contain only linear a, b, c, d and no degree zero terms. Differentiating rs once we obtain (i)/ biscos — hose's + O(w) irs kw/ — cis +O(w) (2.52) EFTA00748903 ITS Chapter 2: Strategy selection in structured populations 37 We want to show the linearity of 4 ) which is 4 )(0). Thus, we have (1) biscos — base's 4s (2.53) Since bog, cog contain no a, b, c, d and b1s, ciS are linear in a, b, c,d for all S and have no free constant terms, we conclude that 4 1) is linear in a, b, c,d and has no free constant term. EFTA00748904 (e) Chapter 2: Strategy selection in structured populations 38 • • • • • •~ (a) (b) siandefd 01431101t PhenotYPOSPaCe (d) (9) Figure 2.1: Various population structures for which a values are known. (a) For the well- mixed population we have a = (N — 2)/N for any mutation rate. (b) For the cycle we have o = (3N — 8)/N (DB) and a = (N — 2)/N (BD) for low mutation. (c) For DB on the star we have a = 1 for any mutation rate and any population size, N > 3. For BD on the star we have a = (N3 — 4N2 + 8N - 8)/(N3 - 2N2 + 8), for low mutation. (d) For regular graphs of degree k we have a = (k +1)1(k —1) (DB) and a =1 (BD) for low mutation and large population size. (e) If there are different interaction and replacement graphs, we have a = (gh+1)1(gh —1) (DB) and a = 1 (BD) for low mutation and large population size. The interaction graph, the replacement graph and the overlap graph between these two are all regular and have degrees, g, h and 1, respectively. (f) For `games in phenotype space' we find a = 1+ .4 (DB or synchronous) for a one dimensional phenotype space, low mutation rates and large population size. (g) For `games on sets' a is more complicated and is given by (2.36). All results hold for weak selection. EFTA00748905 Chapter 2: Strategy selection in structured populations 39 2.5 2.0 I-- 1.5 8 0.5 10 1.5 0.5 00 o Sinuletkos —liv RI -0.5 0.0 S 0.5 10 .1 o 0.0 S 05 1.0 25 1.0 0.5 1.0 0.0 S 0.5 1.0 Figure 2.2: Numerical simulations for DB updating confirm the linear inequality as + b > c + ad. We study the payoff matrix a = 1, b = 5, c = T, and d = 0 for —1 < S < 1 and 0 < T < 2. The red line is the equilibrium condition T = S + a. Below this line A is favored. (a) For a cycle with N = 5 and mutation rate, u = 0.2, we find a = 1.271. The theoretical result for low mutation is a = 1.4. Thus, a depends on the mutation rate. (b) For a star with N = 5 we find a = 1 for u = 0.1. (c) For a regular graph with k = 3 and N = 6 we find a = 0.937 for u = 0.1. The prediction of (2.29) for low mutation is a = 1. Here again a depends on the mutation rate. (d) For this random graph with N = 10 and average degree k = 2 we find a = 1.636 for u = 0.05. For all simulations we calculate total payoffs and use as intensity of selection to = 0.005. Each point is an average over 2 x 106 runs. EFTA00748906 Chapter 2: Strategy selection in structured populations 40 1.5 1.0 - 0.5 0.0 S 15 10 1. 0.5 0 0.0 -0 5 -0.5 0.0 S 0.5 a.0 0.5 1.0 1.0 1.5 1.0 b- cis Oo.o -0.5 1.5 1.0 F. S 05 0 00 0 Sinuleicas —Linos It -03 0.0 S 0.5 -1.0 -0.5 slops • 1.005=0.006 0.0 S 10 05 Figure 2.3: Numerical simulations for BD updating confirm the linear inequality as + b > c + ad. We study the payoff matrix a = 1, b = 5, c = T, and d = 0 for —1 < S < 1 and 0 < T < 2. The red line is the equilibrium condition T = S + a. Below this line A is favored. (a) For a cycle with N = 5 and mutation rate, u = 0.2, we find a = 0.447. The theoretical result for low mutation is a = 0.6. Thus, a depends on the mutation rate. (b) For a star with N = 5 we find a = 0.405 for u = 0.1. The theoretical result for low mutation is a = 0.686. This shows that a depends on the mutation rate. (c) For a regular graph with k = 3 and N = 6 we find a = 0.601 for u = 0.1. The theoretical prediction for low mutation is a = 0.666. Here again a depends on the mutation rate. (d) For this random graph with N = 10 and average degree k = 2 we find a = 0.559 for u = 0.05. For all simulations we calculate total payoffs and use as intensity of selection w = 0.005. Each point is an average over 2 x 106 runs. 1.0 EFTA00748907 Chapter 3 Evolutionary dynamics in set-structured populations Human society is organized into sets. We participate in activities or belong to institutions where we meet and interact with other people. Each person belongs to several sets. Such sets can be defined, for example, by working for a particular company, living in a specific location, going to certain restaurants or holding memberships at clubs. There can be sets within sets. For example, the students of the same university have different majors, take different classes and compete in different sports. These set memberships determine the structure of human society: they specify who meets whom, and they define the frequency and context of meetings between individuals. We take a keen interest in the activities of other people and contemplate whether their success is correlated with belonging to particular sets. It is therefore natural to assume that we do not only imitate the behavior of successful individuals, but also try to adopt their set memberships. Therefore, the cultural evolutionary dynamics of human society, which are based on imitation and learning, should include updating of strategic behavior and of 41 EFTA00748908 Chapter 3: Evolutionary dynamics in set-structured populations 42 set memberships. In the same way as successful strategies spawn imitators, successful sets attract more members. If we allow set associations to change, then the structure of the population itself is not static, but a consequence of evolutionary dynamics. There have been many attempts to study the effect of population structure on evolu- tionary and ecological dynamics. These approaches include spatial models in ecology [80], [77], [76], [67], [24], [45], [151], [82], viscous populations [41], spatial games [104], [69], [95], [137], [68], [47] and games on graphs (78], [115], [149], [130]. We see `evolutionary set theory' as a powerful new method to study evolutionary dynamics in structured populations in the context where the population structure itself is a consequence of the evolutionary process. Our primary objective is to provide a model for the cultural evolutionary dynamics of hu- man society, but our framework is applicable to genetic evolution of animal populations. For animals, sets can denote living at certain locations or foraging at particular places. Any one individual can belong to several sets. Offspring might inherit the set memberships of their parents. Our model could also be useful for studying dispersal behavior of animals 142], [143]. Let us consider a population of N individuals distributed over Al sets (Fig 2.1). Individuals interact with others who belong to the same set. If two individuals have several sets in common, they interact several times. Interactions lead to payoff from an evolutionary game. The payoff of the game is interpreted as fitness [86], [17], [55], [20], (113]. We can consider any evolutionary game, but at first we study the evolution of cooperation. There are two strategies: cooperators, C, and defectors, D. Cooperators pay a cost, c, for the other person to receive a benefit, b. Defectors pay no cost and provide no benefit. The resulting payoff matrix represents a simplified Prisoner's Dilemma. The crucial parameter is the benefit-to-cost ratio, b/c. In a well-mixed population, where any two individuals interact with equal likelihood, cooperators would be outcompeted by defectors. The key EFTA00748909 Chapter $: Evolutionary dynamics in set-structured populations 43 question is if dynamics on sets can induce a population structure that allows evolution of cooperation. Individuals update stochastically in discrete time steps. Payoff determines fitness. Successful individuals are more likely to be imitated by others. An imitator picks another individual at random, but proportional to payoff, and adopts his strategy and set asso- ciations. Thus, both the strategy and the set memberships are subject to evolutionary updating. Evolutionary set theory is a dynamical graph theory: who-interacts-with-whom changes during the evolutionary process (Fig 2.2). For mathematical convenience we con- sider evolutionary game dynamics in a Wright-Fisher process with constant population size [63]. A frequency dependent Moran process [110] or a pairwise comparison process [156], which is more realistic for imitation dynamics among humans, give very similar results, but some aspects of the calculations become more complicated. The inheritance of the set memberships occurs with mutation rate v: with proba- bility 1 — v the imitator adopts the parental set memberships, but with probability v a random sample of new sets is chosen. Strategies are inherited subject to a mutation rate, u. Therefore, we have two types of mutation rates: a set mutation rate, v, and a strategy mutation rate, u. In the context of cultural evolution, our mutation rates can also be seen as 'exploration rates': occasionally we explore new strategies and new sets. We study the mutation-selection balance of cooperators versus defectors in a popu- lation of size N distributed over Al sets. In the Supplementary Information (SI), we show that cooperators are more abundant than defectors (for weak selection and large population size) if blc > —h)/(g—h). The term z is the average number of sets two randomly chosen individuals have in common. For g we pick two random, distinct, individuals in each state; if they have the same strategy, we add their number of sets to the average, otherwise we add 0; g is the average of this average over the stationary distribution. For understanding EFTA00748910 Chapter $: Evolutionary dynamics in set-structured populations 44 h we must pick three individuals at random: then h is the average number of sets the first two individuals have in common given that there is a non-zero contribution to the average only if the latter two share the same strategy. We prove in the SI that for the limit of weak selection these three quantities can be calculated from the stationary distribution of the stochastic process under neutral drift. Our calculation uses arguments from perturbation theory and coalescent theory that were first developed for studying games in phenotype space [4]. Analytical calculations are possible if we assume that each individual belongs to K of M sets. We obtain exact results for any choice of population size and mutation rates (see SI). For large population size N and small strategy mutation rate, it, the critical benefit to cost ratio is given by b K Al v2 +3v +3 c M — K (v + 2) + Al — If v(v + (1) Here we introduced the parameter v = 2Nv, which denotes an effective set mutation rate scaled with population size: it is twice the expected number of individuals who change their set memberships per evolutionary updating. Eq (1) describes a U-shaped function of v. If the set mutation rate is too small, then all individuals belong to the same sets. If the set mutation rate is too large, then the affiliation with individual sets does not persist long enough in time. In both cases, cooperators have difficulties to thrive. But there exists an intermediate optimum set mutation rate which, for K c Ai is given by v.* = O1117K. At this optimum value of v, we find the smallest critical We ratio for cooperators to outcompete defectors. If each individual can only belong to a small number of all available sets, K cc M, then the minimum ratio is given by (b VT . C = 1 + 2 M . (2) Smaller values of K and larger values of Al facilitate the evolution of cooperation. For a EFTA00748911 Chapter 3: Evolutionary dynamics in set-structured populations 45 given number of sets, M, it is best if individuals belong to K = 1 set. Larger values of K make it harder for cooperators to avoid exploitation by defectors. But the extension, which we will discuss now, changes this particular property of the model and makes it advantageous to be in more sets. Let us generalize the model as follows: as before defectors always defect, but now cooperators only cooperate, if they have a certain minimum number of sets, L, in common with the other person. If a cooperator meets another person in i sets, then the cooperator cooperates i times if i ≥ otherwise cooperation is not triggered. L = 1 brings us back to the previous framework. Large values of L mean that cooperators are more selective in choosing with whom to cooperate. Amazingly, it turns out that this generalization leads to the same results as before, but K is replaced by an `effective number of set memberships', K. , which need not be an integer and can even be smaller than one (see SI). In Table 1, we show C and the minimum b/c ratio for a fixed total number of sets, M, and for any possible values of K and L. For any given number of set memberships, K, larger values of L favor cooperators. We observe that belonging to more sets, K > 1, can facilitate evolution of cooperation, because for given AI the smallest minimum b/c ratio is obtained for K = L = M/2. In Figure 2.3, we compare our analytical theory with numerical simulations of the mutation-selection process for various parameter choices and intensities of selection. We simulate evolutionary dynamics on sets and measure the frequency of cooperators averaged over many generations. Increasing the benefit-to-cost ratio favors cooperators, and above a critical value they become more abundant than defectors. The theory predicts this critical b/c ratio for the limit of weak selection. We observe that for decreasing selection intensity the numerical results converge to the theoretical prediction. Our theory can be extended to any evolutionary game. Let A and B denote two EFTA00748912 Chapter 3: Evolutionary dynamics in set-structured populations 46 strategies whose interaction is given by the payoff matrix [(R, 5), (T, P)]. We find that selection in set structured populations favors A over B provided al?+5 > T + aP. The value of a is calculated in the SI. A well-mixed population is given by a = 1. Larger values of a signify increasing effects of population structure. We observe that a is a one-humped function of the set imitation rate, v. The optimum value of v, which maximizes a, is close to fi liff*. For K = L =1 the maximum value of a grows as vri, but for K = L = M/2 the maximum value of a grows exponentially with Al. This demonstrates the power of sets. Suppose A and B are two Nash equilibrium strategies in a coordination game, defined by R > T and P > S. If R+ S C T + P then B is risk-dominant. If R > P then A is Pareto efficient. The well-mixed population chooses risk-dominance, but if a is large enough then the set structured population chooses the efficient equilibrium. Thus evolutionary dynamics on sets can select efficient outcomes. We have introduced a powerful new method to study the effect of a dynamical pop- ulation structure on evolutionary dynamics. We have explored the interaction of two types of strategies: unconditional defectors and cooperators who cooperate with others if they are in the same set or, more generally, if they have a certain number of sets in common. Such conditional cooperative behavior is supported by what psychologists call social identity the- ory [138]. According to this idea people treat others more favorably, if they share some social categories [169]. Moreover, people are motivated to establish positive characteristics for the groups with whom they identify. This implies that cooperation within sets is more likely than cooperation with individuals from other sets. Social identity theory suggests that preferential cooperation with group members exists. Our results show that it can be adaptive if certain conditions hold. Our new approach can also be used to study the dy- namics of tag based cooperation 11261, 11521, [64] : some of our sets could be seen as labels that help cooperators to identify each other. EFTA00748913 Chapter 3: Evolutionary dynamics in set-structured populations 47 In our theory, evolutionary updating includes both the strategic behavior and the set associations. Successful strategies leave more offspring, and successful sets attract more members. We derive an exact analytic theory to describe evolutionary dynamics on sets. This theory is in evePllent agreement with numerical simulations. We calculate the minimum benefit to cost ratio that is needed for selection to favor cooperators over defectors. The mechanism for the evolution of cooperation [101] that is at work here is similar to spatial selection [104] or graph selection [115]. The structure of the population allows cooperators to `cluster' in certain sets. These clusters of cooperators can prevail over defectors. The approach of evolutionary set theory can be applied to any evolutionary game or ecological interaction. EFTA00748914 Chapter 3: Evolutionary dynamics in set-structured populations 48 Figure 3.1: Evolutionary set theory offers a new approach for modeling popu- lation structure. The individuals of a population are distributed over sets. Individuals can belong to several sets. Some sets might contain many individuals, while others are empty. Individuals interact with others who share the same sets. These interactions lead to payoff from evolutionary games. Both the strategy ( = behavior in the game) and the set memberships of individuals are updated proportional to payoff. Sets that contain successful individuals attract more members. In this example, there are two strategies (indicated by red and blue). The population size is N = 10, and there are ill = 5 sets. EFTA00748915 Chapter 3: Evolutionary dynamics in set-structured populations 49 Figure 3.2: Evolutionary set theory is a dynamical graph theory. The set member- ships determine how individuals interact. If two individuals have several sets in common, then they interact several times. In this example, there are N = 5 individuals over M = 4 sets. Each individual belongs to K = 2 sets. The broken lines indicate the weighted inter- action graph. The graph changes as one individual moves to new sets. The evolutionary updating of strategies and set memberships happens at the same time scale. EFTA00748916 Chapter 3: Evolutionary dynamics in set-structured populations 50 M=10 K=1 b/c=2.8339 1.1.15 K=2 b/c=3.4956 0.51 6=0.05 i).," 0.51 6=0.05 c 0.50 o- 0.50 u. 0.49 LI: 0.49 0.48 0.48 2.70 2.80 2.90 3.00 3.10 3.30 3.40 3.50 3.60 3.70 Benefit to cost ratio, b/c Benefit to cost ratio, b/c M=10 M=15 K=1 K=2 O)% 0.51 6=0.1 0.51 6=0.1 5 0.50 0 a) 0.50 u. 0.49 tr. 0.49 0.48 0.481 2.70 2.80 2.90 3.00 3.10 3.30 3.40 3.50 3.60 3.70 Benefit to cost ratio, b/c Benefit to cost ratio, b/c M=10 M=15 K=1 K=2 0.51 6=0.2 tis 0.51 6=0.2 cr a) z 0.50 0.50 0.49 LI: 0.49 0.48 0.48 2.70 2.80 2.90 3.00 3.10 3.30 3.40 3.50 3.60 3.70 Benefit to cost ratio, b/c Benefit to cost ratio, b/c Figure 3.3: Agreement between numerical simulations and the analytical theory. A population of size N=40 is distributed over M = 10 or M = 15 sets. Individuals can belong to K = 1 or K = 2 sets. Each point indicates the frequency of cooperators averaged over 5 x 108 generations. Increasing the benefit-to-cost ratio, b/c, favors cooperators. At a certain b/c ratio cooperators become more abundant than defectors (intersection with the horizontal line). We study three different intensities of selection, 6 = 0.05,0.1 and 0.2. There is excellent agreement between the numerical simulations and the analytical prediction for weak selection, which is indicated by the vertical blue line. Other parameters values are L = 1, ae = 0.002, v = 0.1, b = 1; c varies as indicated. EFTA00748917 Chapter $: Evolutionary dynamics in set-structured populations 51 K L K* minimum b/c 1 1 1 2.17 2 1 2 3.13 2 2 2/9 1.42 3 1 3 4.29 3 2 5/4 2.30 3 3 1/12 1.24 4 1 4 5.80 4 2 64/21 4.35 4 3 19/21 2.09 4 4 1/21 1.18 5 1 5 7.94 5 2 605/126 7.44 5 3 45/14 4.58 5 4 5/6 2.02 5 5 51126 1.16 6 1,2 6 11.26 6 3 121/21 10.31 6 4 27/7 5.55 6 5 1 2.17 6 6 1/21 1.18 7 1,2,3,4 7 17.23 7 5 16/3 8.87 7 6 19/12 2.72 7 7 1/12 1.24 8 1,2,3,4,5,6 8 31.24 8 7 10/3 4.74 8 8 2/9 1.42 9 1,2,3,4,5,6,7,8 9 104.7 9 9 1 2.17 Figure 3.4: Table 1: The minimum benefit-to-cost ratio. Each individual belongs to K sets. Cooperation is triggered if the other person has at least L sets in common. For a fixed total number of sets, = 10, we can vary K = 1, ...,9 and L = 1,...,K. The effective number of set memberships, K. , is given by eq (54) in the SI. For a finite population of N = 100 we calculate the minimum benefit-to-cost ratio that is needed for selection to favor cooperators over defectors. For given K, cooperators are favored by larger L and the smallest b/c ratio is obtained by L = K. The global minimum occurs for L = K = M/2. Smaller values of IC imply smaller values of the critical b/c. The blue lines indicate minimum b/c ratios that are less than the value for K = 1. The red line indicates the global minimum. Note that various symmetries lead to identical K* values. EFTA00748918 Chapter 4 Supplementary Information for Evolutionary Dynamics in Set Structured Populations This `Supplementary Information' has the following structure. In Section 1 (Tvo- lution of cooperation on sets') we discuss the basic model and derive a general expression for the critical benefit-to-cost ratio. In Section 2 (Telonging to K sets') we calculate the critical benefit-to-cost ratio for the model where all individuals belong to exactly K sets and cooperators cooperate with all other individuals in the same set. In Section 3 ('Triggering cooperation ') we generalize the basic model to the situation where cooperators are only triggered to cooperate if the other individual has at least L sets in common. In Section 4 ('The minimum benefit-to-cost ratio') we calculate the optimum set mutation rate that minimizes the critical benefit-to-cost ratio. The results of Sections 3 and 4 are derived for large population size, N. In Section 5 ('Finite population size') we give the analytic expressions for any N. In Section 6 (`liumerical Simulations') we compare our analytical 52 EFTA00748919 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 53 results with computer simulations. In Section 7 (`General Payoff Matrix') we study the competition between two strategies, A and B, for a general payoff matrix. In the Appendix we give the analytic proof of our results. 4.1 Evolution of cooperation on sets Consider a population of N individuals distributed over Al sets. Each individual belongs to exactly K sets, where K < Al. Additionally, each individual has a strategy E {OM, refered to as cooperation, 1, or defection, 0. The system evolves according to a Wright-Fisher process [31], (27]. There are discrete, non-verlapping generations. All individuals update at the same time. The population size is constant. Individuals reproduce proportional to their fitness [86], [55]. An offspring inherits the sets of the parent with probability 1 — v or adopts a random configuration (including that of the parent) with probability v. Any particular configuration of set memberships is chosen with probability vi(:). Similarly, the offspring inherits the strategy of the parent with probability 1 — u; with probability u he adopts a random strategy. Thus, we have a strategy mutation rate, u, and a set mutation rate, v. If two individuals belong to the same set, they interact; if they have more than one set in common, they interact several times. An interaction can be any evolutionary game, but first we consider a simplified Prisoner's Dilemma game given by the payoff matrix: C D C (b — c —c D b 0 ) Here b > 0 is the benefit gained from cooperators and c > 0 is the cost cooperators have to pay. The payoff gained by an individual in each interaction is added to his total (4.1) EFTA00748920 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 54 payoff, p. The fitness of an individual is f =1+6p, where 6 corresponds to the intensity of selection 1114 The limit of weak selection is given by 6 0. Neutral drift corresponds to 6= 0. A state S of the system is given by a vector s and a matrix H. s is the strategy vector; its entry si describes the strategy of individual i. Thus, si = 0 if i is a defector and it is 1 if i is a cooperator. H is an N x Al matrix whose ij-th entry is 1 if individual i belongs to set j and is 0 otherwise. We will refer to row i of H as the vector hi; this vector gives the set memberships of individual i. Considering that two individuals interact as many times as many sets they have in common and that we do not allow self-interaction, we can now write the fitness of individual i as fi = 1 + 6 E(hi ' hi)(—esi + bsi) 1o/ Thus, individual i interacts with individual j only if they have at least one set in common (hi • hi 0). In this case, they interact as many times as they find themselves in joint sets, which is given by the dot product of their set membership vectors. For each interaction, i pays a cost if he is a cooperator (si = 1) and receives a benefit if j is a cooperator (sj = 1). Let Fe be the total payoff for cooperators, Fe = Ei si fi. Let FD be the total payoff for defectors, FD = E 1(1 - si) fi. The total number of cooperators is E, s,. The total number of defectors is N — E, st. Provided that the number of cooperators and that of defectors are both non-zero, we can write the average payoff of cooperators and defectors as fC = E isif/ Et s/ fD E'( 1 — Safi N — E, st (4.2) (4.3) EFTA00748921 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 55 The average fitness of cooperators is greater than that of defectors, fp > fp, if E sifi(N — E > E s, E(1 _ st)f, •; • (4.4) NE ad; >EstEfi (4.5) We rewrite equation (4.2) in a more convenient form, using the fact that hi • hi = K for any i. = + 6(E hi • k(—es, + hs,) _ K(h— d Then inequality (4.5) leads to (4.6) b— c , K(b — N E K(b — bE sojhchr eE s,h,•n • > — E E s, (4.7) 3 N N i,j,t In order for cooperators to be favored, we want this inequality to hold on average, where the average is taken in the stationary state, that is over every possible state S of the system, weigthed by the probability irg of finding the system in each state. b(E sis Ai • — Cs ihi • hi \ >bN—e(rEsiskh,•hi) K(b—c)(r sok)+ i,j i,y,k i,k K(b — c)( Esi) (4.8) The angular brackets denote this average. Thus, for example, ( Esisih, • hj) E (E sisihi • hj) • (4.9) id s id So far this has been an intuitive derivation. A more rigorous analytic derivation which explains why we take these averages is presented in the Appendix; it also appears in a different context in [4]. We further show in the Appendix that when we take the limit of weak selection, the above condition (4.7) is equivalent to the one where we take these EFTA00748922 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 56 averages in the neutral stationary state (see equations (4.90), (4.92) and the discussion following them). Neutrality means that no game is being played and all individuals have the same fitness. Thus, we show that in the limit of weak selection the decisive condition is b( Esisik . hoo _ c(Esik .ho N b— e(Esiskh, • hoo _ K 0 ( E sok)o id i,j,k i,k + - Esi N o (4.10) The zero subscript refers to taking the average in the neutral state, 6 = 0. For example, the term (Lid sisjhi • hi)0 is (Es ts)h,•h3) 0 = (E t, S i,2 sisihi • hi) • irr (4.11) Here 4 °) is the neutral stationary probability that the system is in state S. As before, the sum is taken over all possible states S. Solving for b/c we obtain the critical benefit-to-cost ratio ( b * _ (E1,5 Sihi •' hj)0 - k (a,,, sisihi •. hao — K(Ei ma + fir (a, sisi)0 a (Eid siaihi • too — 71,(Eid,, soak • 400 — I{ (Ei si)o + ffr (a d sisi)o (4.12) Thus, we have expressed the critical b/c ratio in the limit of weak selection, only in terms of correlations from the neutral stationary state. Now we can focus on the neutral case to obtain the desired terms. Nevertheless, the results we derive hold in the limit of weak selection, 6 —) 0. The strategies and the set memberships of the individuals change independently. All correlations in (4.12) can be expressed as averages and probabilities in the stationary state. We will describe each necessary term separately. First we consider the term (Esi) NPr(si = 1) = —2 . o (4.13) EFTA00748923 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 57 This is simply the average number of cooperators. In the absence of selection this is N/2. Next we consider (Esisi)o N2Pr(si = sj = 1) = 2 — N2 Pr(si = sj) id (4.14) The first equality is self-explanatory. The second equality follows from the fact that in the neutral stationary state the two strategies are equivalent. Thus we can interchange any 0 with any 1 and we can express everything in terms of individuals having the same strategy rather than being both cooperators. Mks in the absence of selection, Pr(si = sj = 1) = Pr(si = si)/2. We will use the same idea for all terms below. Next, we consider the term (Esih, • hi% = N20,, • h, N2 = (hi • h5)0 ij (4.15) The function 1.0 is the indicator function. It is 1 if its argument is true and 0 if it is false. For the last two terms of the equality, i and j are any two individuals picked at random, with replacement. In the sum E ij sihi • hi, we add the term hi • hi only if si = 1; otherwise, we add 0. Nevertheless, our sum has N2 terms. This leads to the first equality. To be more precise, we should say that (E silt; • 1O0 = N2 •E[(14 • hj L i=1)0], where the expectation is taken over the possible pairs (1, j). For simplicity, we will omit the expectation symbol. We can think of the term (111 • hi 1 84=1)0 as the average number of sets two random individuals have in common given that they have a non-zero contribution to the average only if the first one is a cooperator. By the same reasoning as above, any i can be interchanged with any j and thus we can obtain the second equality in (4.15). Thus, the term we end up calculating is (hi • hj)0 which is the average number of sets two random individuals have in common. EFTA00748924 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 58 The same reasoning leads to the final two correlations. We have (Eso,h, • h1) = N20,,, • hi 1 8, = „i= 00 = T(ii • hi 1 8,=8))o (4.16) i,j Using the same wording as above, equation (4.16) is the average number of sets two individuals have in common given that only individuals with the same strategy have a non-zero contribution to the average. Finally, we can write (E mak; • hi)0 =N3(hi • hi 18,=„00 = Tyij • al 1 8, = ,00 (4.17) i,j,i For this term we need to pick three individuals at random, with replacement. Then, (4.17) is the average number of sets the latter two have in common, given that they have a non-zero contribution to the average only if the first two are cooperators. Therefore, we can rewrite the critical ratio as ( by NOLi • h1)o — I (hi • hi 18,=00 — K + K • Pr(si = si) e r(hi • hi 3.„=00 — Noj • hi 1,,,=„40 — K + K • Pr(si = (4.18) For simplicity, we want to find the above quantities when the three individuals are chosen without replacement. We know, however, that out of two individuals, we pick the same individual twice with probability 1/N. Moreover, given three individuals i, j and 1, the probability that two are the same but the third is different is (1/N)(1 — 1/N), whereas the probability that all three are identical is 1/N2. EFTA00748925 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 59 Let us make the following notation y= Pr(si = sj I i j) (4.19) z= (4.20) 9 = (hi • hi 1s,=a) I i 0 .i)0 (4.21) h = (hj • hi 181=81 i j 01)0 (4.22) Then the quantities of interest in (4.18) become 1 N N-1 Pil af = si ) N 2 + N j 1 N — 1 (hi • hj)0 — KN 1 — (hi • hi 18,") 0 = KTIT + N 1 (hi • in 18,=„1)0 = K ;12 (N - 1)(N - 2)h + N —1 (z + g + N2 N2 The critical ratio can now be expressed in terms of z,g and h as b\* (N — 2)(z — + z — g c) (N —2)(g — h)— z + g Note that y cancels. In the limit N oo we have Lb\* = z —h ke) g —It (4.23) (4.24) (4.25) (4.26) (4.27) (4.28) For calculating the critical benefit-to-cost ratio in the limit of weak selection, it suffices to find z, g and h in the neutral case: z is the average number of sets two randomly picked individuals have in common; g is the average number of sets they have in common given that only individuals with the same strategy have a non-zero contribution to the average. For h we need to pick three individuals at random; then h is the average number of sets the latter two have in common given that they have a non-zero contribution to the average only if the first two have the same strategy. EFTA00748926 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 60 In general these quantities cannot be written as independent products of the average number of common sets times the probability of having the same strategy. However, if we fix the time to their most recent common ancestor (MRCA), then the set mutations and strategy mutations are obviously independent. If we knew that the time to their MRCA is T = t, we could then write g, for instance, as the product: (hi • hj I i j, T = 00 • Pr(si = si I i j, T = (4.29) Two individuals always have a common ancestor if we go back in time far enough. However, we cannot know how far we need to go back. Thus, we have to account for the possibility that T = t takes values anywhere between 1 and co. Note that T = 0 is excluded because we assume that the two individuals are distinct. Moreover, we know that this time is affected neither by the strategies, nor by the set memberships of the two individuals. It is solely a consequence of the W-F dynamics. We can calculate z,g and h provided that we know that the time to their MRCA is T. We first calculate the probability that given two random individuals, i and j, their MRCA is at time T = t: Pr(T = = (1 — N N (4.30) Next, we calculate the probability that given three randomly picked individuals i, j and k, and looking back at their trajectories, the first merging happens at time t3 while the second one takes t2 more time steps. If we follow the trajectories of these individuals back in time, the probability that there was no coalescence event in one time step is (1 —1/N)(1 — 2/N). Two individuals coalesce with probability 3/N(1 —1/N). When two individuals have coalesced, the remaining two merge with probability 1/N during an update step. For the probability that the first merging happens at time t3 > 1 and the second takes t2 > 1 more EFTA00748927 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 61 time steps, we obtain ( 2 1- y2 Pr(t3, t2) = — [(1 - Tr) - Tr)] fa -1 ( w 2 The probability that all three pat Is merge simultaneously at time t3 is: 2 Pr(t3,0) = A+.2 [(1 - 71 .1 ) (1 )113-1 - (4.31) (4.32) We can calculate both the case of finite N and the limit N co. The results for finite N will be discussed in Section 5. Here we deal only with the N —• oo limit. In this case, we introduce the notations r = LIN, r2 = t2/N and r3 = t3/N. We use a continuous time description, with r, r2, 73 ranging between 0 and oo. In the continuous time limit, the coalescent time distributions in (4.30) and (4.31) are given by P(r) = and (4.33) P(7'3, T2) = 3e- 0'3+70 (4.34) Due to the non-overlapping generations of the W-F process, each individual is newborn and has the chance to mutate both in strategy and in set configuration. In the N co and tz,v -. 0 limits, we can consider our process to be continuous in time, with strategy mutations arriving at a rate P = 2Nu and set membership mutations arriving at a rate v = 2Nv in the ancestry line of any two individuals. 4.2 Belonging to K sets First, we find the probability that two individuals have the same strategy at time t from their MRCA. Next we find the average number of sets two individuals have in common, a quantity which is necessary for finding z, g and h. Finally, we calculate the critical benefit-to-cost ratio. EFTA00748928 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 62 4.2.1 Probability that two individuals have the same strategy The first quantity we need is the probability that two individuals have the same strategy at time t from their MRCA. Imagining the two paths of two individuals i and j starting from their MRCA, it is easy to note that two players have the same strategy at time t if the total number of mutations which occurred in their ancestry lines is even. The probability that an even number of mutations has occurred is y(t) = Pr(si = sj T = t) = (2t) k.21 2) 1/4,2) — 1 + 1 - 2 \ 2t-21 ( u 21 ( 142t 1=0 (4.35) In the continuous time limit, making the substitutions r = t/N and A = 2Nu, we obtain 1+ — 2 , 2rN y(r) = lint N—.co 2 2N The limits above are taken for µ = constant. 1 + co' 2 4.2.2 Average number of sets two individuals have in common (4.36) The first quantity we need is z = (hi • hi I i j)0. As in the previous subsection, we begin by calculating this probability given that the MRCA of the two individuals is at time r. We use the notation z(r)= (hi • hj l i 0 j, T=r)o (4.37) We can interpret z as the average number of sets two randomly chosen, distinct individuals have in common. Then z(r) is this same average, but taken now only over the states where T = r. We start by finding the probability that two such individuals have 0 ≤ i ≤ K sets in common. We then have two options at time r from their MRCA: neither of the two have changed their configuration or at least one of them has changed his configuration. In the second case, the two individuals become random in terms of the comparison of their set memberships. EFTA00748929 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 63 Thus, we analyze the following possibilities: • neither has changed with probability e- "T and in this case they still have K sets in common; • at least one has changed with probability 1 — e- n and in this case they can have i E {0Y.. ,K} sets in common with probability: (t- Ki) (Z) (4.38) Hence, the probability that two individuals have i < K sets in common at time T = T from their MRCA is ii(T) = { e-vr + (1- e-mr)/(x) if i = K (1 - e-vr)(xi)(Airxiver) if < K (4.39) Our goal is to calculate the average number of sets they have in common. We obtain K-1 • K)( 111111-Ki) Z(T)= E i • irgr) = Ke- n + (1 - e- n) E i=1 0.40) K2) K2 = e -VT (K Al AI 4.2.3 Finding the critical ratio Once we know the average number of sets two individuals have in common at time T from their MRCA, we can again use the method of the coalescent to express z = (hi • hj I i ,j)0 in the continuous time limit as O0 , z = z(r)p(r) 11T K(AI + ulf) 0 M(/ +1) (4.41) The next quantity we need is g = • nj 1,1=8, I I j)0. As explained above, this can be interpreted as the average number of sets two distinct random individuals have in common given that they have a non-zero contribution to the average only if they have the EFTA00748930 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 64 same strategy. Let g(r) = (hi • hi 3.,,=s1 I i j, T = r)0. Once we fix the MRCA, the set mutations and strategy mutations are independent. Thus g(r) can be written as a product of the probability that i and j have the same strategy and the average number of sets two distinct individuals have in common. We can then write g(r) as g(r) = z(r)y(r) In the continuous time limit, we have (4.42) oo K + vK K M — K (4.43) g = z(r)y(r)p(r) dr = 2AI ks 1 + v l+fc + + 1 + v + Finally, we need to find h = (hi • hi 1.8i=ai I i j 00. This can be interpreted as follows: we pick three distinct random individuals i, j and I and ask how many sets j and I have in common on average, given that they have a non-zero contribution to the average only if i and j have the same strategy. As before, we need to fix the time up to the MRCA of the particular pairs of individuals. Let T(i,j) (respectively T(j, I)) be the time up to the IvIHCA of i and j (respectively j and I). If we look back far enough, all three individuals will have an MRCA (all their paths will coalesce). However, we do not know which two paths coalesce first, so we have to analyze all possibilities (shown in the figure below). Let r2 be the time up to the first coalescence and let r2 be the time between the first and the second coalescence. Then, we can find T(i,j) and T(j,1) in each case 72 r3 rz T3 t 3 t t 3 t z t 3 i and j coalesce first j and I coalesce first i and i coalesce first T(i, i) = T2 + T3 T(j,I) = r3 T(i,j) = T3 TUM =r2 + r3 T(i,j) = T2 + T3 TU, = T2 +73 EFTA00748931 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 65 The possibility that all three coalesce simultaneously is included in these three cases (when r2 = 0). Let h(r3,r2) = (hi • hi 1,4=kt i j 1)0. Once we fix the times to the MRCA's, the set mutations and the strategy mutations become independent. Then we can write h(r3, T2) as a product. We already know the probability y(r) that two individuals have the same strategy at time r from their MRCA (4.36). Moreover, we know z(r), the average number of sets they have in common if the time to their MRCA is T = T. So we only need to use the times T(i,j) and T(j,1) calculated in each of the three cases. With probability 1/3 we are in the first case, where i and j coalesce first and then they coalesce with 1. In this case, we can write h(r3,r2) = y(r3)z(rs + r2). With probability 1/3 we are in the second case, where j and I coalesce first and then they coalesce with i. Then h(rs, r2) = v(r3+1-2)z(r3). Finally, with probability 1/3 we are in the last case, where i and / coalesce first and then they coalesce with j. In this case h(r3O-2) = y(r3 + r2)z(r3 +v2). We finally obtain the expression for h = (hi • tit 1.,=„) I I j l)0 by adding the values in all three cases, multiplied by the corresponding probabilities. h = — 3 0 dr3 dr2 [+r(r3)z( + r2) + y(r3 + r2).z(rz) + y(rj + r2)z(n + r2)]p(i, P2) 1 Joy vx-2(3+10A+612+113+v2(2+,u) + 2v(2 + p)2)+ 2M(1 + v)(1 + /4(1 + v + /4(3 + v + p) IIIK(3 + + 6µ2 + 113 u 2(2 + v(8 + Op + 2/12)) 2M(I. + v)(1 + /4(1 + v + /4(3 + v + (4.44) Now we have calculated d, g and h. We can use (4.28) to obtain the critical b/c ratio l b * K 11, - 1 K v2 +3v+3+2(v+2)0+112 Ai M-K(v+2+11)+ M v(v+2+µ) (4.45) Note that the critical b/c ratio depends only on MIK and not on both M and K. EFTA00748932 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 66 For 0 we have (b\* K Al v2 +3v +3 c AI —If O, + 2) + AI —If v(v +2) (4.46) If the benefit-to-cost ratio exceeds this value, then cooperators are more frequent than defectors in the equilibrium distribution of the mutation-selection process. 4.3 Triggering cooperation We will now study an extended model, where cooperation is only triggered if the other person has L sets in common. We have 1 ≤ L < K. Setting L = 1 takes us back to the previous framework. In order to account for this conditional interaction, we define the following variable: 1 if hi • nj > L = 0 otherwise The fitness of individual i can be written as (4.47) A = 6 E 7„,, • hi(—esi+osi) (4.48) aoi Everything follows exactly as before, with the only change that wherever we have the product hi • hi, it will be replaced by ^yihi • hi. The quantity y(r) remains unchanged and represents the probability that two random, distinct individuals have the same strategy at time r from their MRCA. The quantity that is affected by the change is z(r) which now becomes z(r) = (^AA • hi)o; this is now the average number of sets two individuals have in common, provided that they have at least L sets in common. Implicitly, z , g and h will change: instead of accounting for the average number of sets in common, they account for the average number of sets in common, provided that there are at least L common sets. EFTA00748933 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 67 As before, we can express z,g and h as follows oo Z = Z(T)p(T) dr 0 g =.1 00 00 Pr(si = si I T = r)("rijk • hi I T = r)op(r) dr = .1 z(r)y(r)p(r) dr (4.50) h = — o r dr3 dr2 Iy(r3)z(r3 + r) + y(r3 + r2)z(r3) + y(r3 + r2)z(r3 + rz)IP(ra, P2) 3 (4.49) (4.51) We obtain the same expressions (4.27) and (4.28) in terms of these new z, g and h. The only quantity that has changed and needs to be calculated is z(r) = eyiihrhi T = r)o. The reasoning is as before, but we now need to account for the ^At We start by finding the probability that two random individuals have 0 < i ≤ K sets in common. This follows exactly as before: the probability that two individuals have i ≤ K sets in common at time T = r from their MRCA is r" + (1 — c")/(Z) if i = K Mr) = (4.52) (1 — e- yr)(Ine lk-il)/(Z) if < K Our goal is to estimate the quantity z(r) = (70/4 • hi I T = r)o. We know that -yij = 0 if they have less than L sets in common. Only the cases when they have at least L sets in common contribute to our average. Therefore, we have Z(r) = (viihi • hj I T = 1)0 = Ei• iri(t) (4.53) We have already analyzed the case L = 1. We will now study the case 1 < L < K. We denote: If"= i ( \ M — \(AI K ( — Kt , WO( —KlkiK)\ = L•kiK — 1) ks, K — if' i kK —1)\ iL Note that K* need not be an integer and that for L =1 we obtain Ks = K. Using (4.53) and (4.39), we can rewrite z(r) as z(r) = K(1 — —)r" K + I— M (4.54) (4.55) EFTA00748934 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 68 The critical ratio (4.28) becomes Ifs Al v2 +3v +3+ 2(v +2)µ + A2 cJ M — Ift (v + 2 + + M — If* v(v + 2 +p) (4.56) Since for L =1 we have K* = K, we recover the previous result, (4.45). For µ we have fb\* K" 2‘ M v2 + 3v -I- 3 ke) M — K* AI —If" v(v +2) (4.57) The critical benefit-to-cost ratio is the same as given by equation (4.46) but now K is replaced by K", which is the 'effective' number of sets that each individual belongs to. The smaller K" is, the smaller is the critical benefit-to-cost ratio. The critical benefit-to-cost ratio depends on Mfr. The mechanism for the evolution of cooperation in our model is similar to the clus- tering that occurs in spatial games [104] and games on graphs [115], [119]. Cooperators cluster together in some sets and thereby gain an advantage over defectors. But the dif- ference between evolutionary graph theory and evolutionary set theory is the following. In evolutionary graph theory, both the interaction (which leads to payoff) and the evolutionary updating must be local for cooperators to evolve. In evolutionary set theory, the interac- tions are local (among members of the same set), but the evolutionary updating is global: every individual can choose to imitate every other individual. Our model is also very different from standard models of group selection. In standard models of group selection, (i) each individual belongs to one group; (ii) there is selection on two levels (that of the individual and that of the group); (iii) and there is competition between groups resulting in turnover of groups. In contrast, in evolutionary set theory, (i) individuals can belong to several sets; (ii) there is only selection on the level of the individual; (iii) and there is no turnover of sets. EFTA00748935 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 69 4.4 The minimum benefit-to-cost ratio The critical We ratio given by eqn (4.57) has a minimum as a function of v. To find this minimum, we differentiate (ble)' as a function of v and set the result equal to zero. We obtain Al — 2 1/2 + 4V + 4 v K* v2 +6v+6 (4.58) It is easy to show that the solution, vopt, of this equation satisfies the inequality < v,,pt < #.7 + 1. Consequently, when Al/K" is large, the optimum v is v°P1— Thus, for Al/K" large, we obtain -) =1+2 K — M (4.59) (4.60) Figure S1 shows the critical benefit-to-cost ratio as a function of the effective set mutation rate v = 2Nv for various choices of K and L. We use M = 10, N oo and —) 0. As a function of v, the benefit-to-cost ratio is a U-shaped function. If the set mutation rate is too small, then all individuals belong to the same sets. If the set mutation rate is too large, then set affiliations do not persist long enough in time. In both cases the population behaves as if it were well-mixed and hence cooperators have difficulties to thrive. In between, there is an optimum set mutation rate given by (4.59). 4.5 Finite population size In order to do the exact calculation for finite population size, we start from equation (4.27): b\* (N — 2)(z — h)+ z — g kc) (N — 2)(g — h)— z+ g EFTA00748936 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 70 We deal from the beginning with the general case, 1 < L < K. First we calculate the probability that two individuals have the same strategy at time t from their MRCA. This is given in (4.35) as Y(t) 1 + (1Z u)2t (4.61) Next we calculate z(t) = (^yiihi • hi I T = t)0. The reasoning is the same as in the continuous time case. We analyze the following possibilities: • neither has changed with probability (1 — v)2t and in this case they still have K sets in common; • at least one has changed with probability 1— (1 — v)21 and in this case they can have i E 0,...,10 sets in common with probability (4.62) Hence, the probability that two individuals have i ≤ K sets in common at time T = t from their MRCA is given by = (1 - v)2t + (1 - (1 - v)29/(Ak4) if = K (4.63) We obtain: — — 1029M (tin / en if i <K z(0 = (7414 • hi IT = K* = Ei • MO = — K ri d0. — + K K* — (4.64) O0: limit St, This gives z = (71A; • hi)0, taking into account the fact that t ranges between 1 and 00 00 1 z.E(-yihi • 1i1 T = t)oPr(T = 0 = Ed(t) (1- AT.y-1 (4.65) t=I t=I We find g and h similarly and use (4.27) to find the exact critical b/c in the u 0 (b) . re(' + (4.66) leas + Mad EFTA00748937 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 71 where ozi,ct2,oi3, 0e4 are the following polynomials in v and N of = (N — 1)N3v(2 — v)[v(2 — v)(—Nv(2 — v) + 4(1 — v)2) + (1 — v)2(5v2 — 10v + 4) 02 = —(N — 1)(1 — v)2[N2v(2 — v)(—Nv(2 — v) — 4v2 +8v — 3)- - (1 — v)2(N(5v2 — 10v + 3) — 2(1 — 0 2)] 03 = —v(2 — v)IN4v(2 — + N2(1 — v)2(2N — 1)] as = (1 — v)4(2(1 — v)2 — N(7v2 — 14v + 3)) — N2v(2 — v)(1 — v)2(—N2v(2 — v)- - N(5v2 - 10v + 2) + 9v2 - 18v + 8) The exact benefit-to-cost formula (4.66) gives perfect agreement with our numerical simulations; see Fig. 3 of the main paper. Figures S2 and S3 illustrate the critical benefit-to-cost ratio as a function of the population size N and of the number of sets M for various choices of K and L. We use v = 0.01 and n = 0.0002. As a function of N (Fig. S2), the benefit-to-cost ratio is a U-shaped function. If the population size is too small then the effect of spite is too strong. In the limit of N = 2, it never pays to cooperate. If the population size is too large (for a fixed number of sets Al and a fixed set mutation rate v), then all the sets get populated by defectors and cooperators can not survive. As a function of the number of sets Al (Fig. S3), the benefit-to-cost ratio is a declining function. Adding more sets is always helpful for the cooperators. EFTA00748938 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 72 b/c 10 b/c 35 30 25 20 15 10 S 10 IS 20 25 03) (a) 15 20 V Fig. S 4.1: Critical benefit-to-cost ratio as a function of the effective set mutation rate v = 2Nv. The strategy mutation rate is u = 0.0002 and the population size is large, N —) co. (a) Critical b/c ratios for L = 1,K = 1,2,3, and total number of sets AI = 10. This shows that increasing K is worse for cooperation. (b) Critical b/c ratios for K = 1 and for L = 1, , 5, K = 5, and Al = 10. This shows that larger K can be better for cooperation, as long as L is sufficiently large. EFTA00748939 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 73 b/e (0) b/c SO 60 40 20 — Lei — L-2 — L-3 500 1000 1500 2000 2500 3000N (b) Fig. S 4.2: Critical benefit-to-cost ratio as a function of the population size N. The set mutation rate is v = 0.01. The strategy mutation rate is a = 0.0002. (a) Critical b/c ratios for L = K = M/2 and M = 6,8,10,20. (b) Critical b/c ratios for L = 1,2,3,4,5,K = 5 and M = 10. EFTA00748940 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 74 b/e 9.0 83 8.0 73 7.0 63 bit 83 8.0 73 7.0 63 — — — 20 40 60 (a) (b) leo m — 41 — 60 80 tie Fig. S 4.3: Critical benefit-to-cost ratio as a function of the number of sets M. The set mutation rate is v = 0.01. The strategy mutation rate is u = 0.0002. (a) Critical b/c ratios for L =1,K =1,2,3 and N = 20. (b) Critical b/c ratios for L =1,2,3,K = 3 and N = 20. EFTA00748941 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 75 4.6 Numerical simulations We have performed numerical simulations in order to test the results of our analytical theory (see Figure 3 of the main paper and Figure S3 here). We consider a population of N individuals distributed over Al sets. Each individual is in K sets. There are two types of strategies: cooperators, C, and defectors, D. Cooperators pay a cost, c, for another individual to receive a benefit, b. The fitness of an individual is given by 1+ JP, where P is the payoff of the individual. We simulate the Wright-Fisher process for a given intensity of selection, 6. In each generation we compute the fitness of each individual. The total population size, N, is constant. For the next generation, each individual leaves offspring proportional to its fitness. Thus, selection is always operating. Reproduction is subject to a strategy mutation rate, u, and a set mutation rate v, as explained previously. We follow the popula- tion over many generations in order to calculate an accurate time average of the frequency of cooperators in this mutation-selection process. In Figure S3 we show the time average of the frequency of cooperators as a function of the benefit-to-cost ratio, b/c. We simulate the Wright-Fisher Process for four different intensities of selection ranging from b = 0.05 to 0.4. The red points indicate the average frequency of cooperators in the mutation selection process. Each point is an average over t = 5 x 108 generations. As expected the average frequency of cooperators increases as a function of b/c. We are interested in the value of b/c when cooperators become more abundant than defectors (when their frequency exceeds 1/2.). The vertical blue line is the critical b/c ratio that is predicted from our analytical theory for the limit of weak selection, 6 -. 0. We observe excellent agreement between theory and simulations. For weaker intensity of selection the critical value moves closer to the theoretical prediction. EFTA00748942 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 76 b/c-3.8277 0.520 5 • 0.510 6=0.05 0.500 ▪ 0.490 3.70 0.520 5 0.510 0.500 ▪ 0.490 3.70 6 0 2 0.520 5 • 0.510 g 0.500 ▪ 0.490 3.70 3.80 3.90 4.00 4.10 0.1 0.520 5 0.510 g 0.500 Is 0.490 3.70 3.80 3.90 4.00 4.10 3.80 3.90 4.00 4.10 Benefit to cost ratio. b/c Fig. S 4.4: Numerical simulation of the mutation-selection process for population size N = 80 and various intensities of selection ranging from S = 0.05 to IS = 0.4. The red dots indicate the frequency of cooperators averaged over t = 5 x los generations. The cooperator frequency increases as a function of the b/c ratio. For a certain ratio, cooperators become more abundant than defectors (intersection with black horizontal line). The blue vertical line is the theoretical prediction of the critical b/c ratio in the limit of weak selection, (b/c)* = 3.8277. Parameter values: population size N = 80, number of sets M = 10, number of set memberships K = 1, set mutation rate v = 0.1, strategy mutation rate le = 0.004. We fix b = 1 and vary c. 4.7 General Payoff Matrix Let us now study a general game between two strategies A and B given by the payoff matrix A B A (R S) B T P (4.67) EFTA00748943 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 77 A derivation similar to the one presented in the Appendix leads to the following condition necessary for strategy A to be favored over B (R - S)g + (S - P)z 7 (R - S - T + 12)n + (S +T - 2P)h (4.68) The quantities z,g and h are as before and n is defined as follows n = (IA • hi 1.,=„)=8, I i j 1) (4.69) To interpret n, we pick three distinct individuals randomly. Then ,n is the average number of sets the last two individuals have in common given that they hav a non-zero contribution to the average only if all three have the same strategy. To calculate n we proceed similarly as for h. We fix the times r3 up to the first coalescence and r2 extra steps up to the second. We denote by y(r3,r2) the probability that the three individuals have the same strategy given these times to the coalescence. We can now rewrite n as co 00 n = dr21 e-373 -721/(73, T2)IZ(T3) z(r2 1-3)+ z(r2 + r3)]dr3 (4.70) The only quantity we need to compute is y(r3, r2). Let us assume that i and j coalesce first, and then they coalesce with I. As before, in order for i and j to have the same strategy, the total number of mutations that happen up to their coalescence must be even. Therefore, either both underwent an even number of mutations from their MRCA, or an odd one. If i underwent an odd number, then in order for i and I to have the same number of mutations, it must be that, in the remaining total time (which is r2+2r3) there must be an odd number of mutations. Thus, in this case we can write the probability that all three have the same strategy as -1(1 - e- in)2(1 - e-i fra+T21) (4.71) When i undergoes an even number of mutations up to its coalescence with j, the EFTA00748944 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 78 probability that all three have the same strategy is similarly obtained as (1 +e- in)2(1 (n+D2)) 8 Thus, we can write 1O3,72) e-119 2(1— rt (13+72)) +;(1 + e- 513)2(1+ ri(Ti+72)) (4.72) (4.73) Plugging into (4.70) we obtain the expression for n. Substituting z,g,h and n into (4.68) and rearranging terms, we obtain where aR+S>T+aP (4.74) 1+v+µ K*(/2 +2v + vp)+ M0+ 2v + a (4.75) 3 + v + K * (v2 + 2v + 1/µ)+ Af (1 + A) Note that if v 0, the condition a > 1 is equivalent to M > IC, which is always true. Therefore, a is always larger than one when V 0 0. Furthermore, a is exactly one in the following limits: when V -) 0, when v —) co or when MIK* —.1. In all of these cases, the population is well-mixed. For µ = 0, we obtain a — 1 + v K* v(2 + + Al (3 + 2v) 3+v lev(2+ v)+ M (4.76) We observe that a is a one-humped function of v. It attains a maximum, which we denote by a„,,,x. To find the value of v for which this maximum is achieved we differentiate (4.76) and set it equal to zero. We obtain the same expression as in (4.58). Therefore, it has the same solution which satisfies OW < vopt < fie ."//f" + 1. For large MIK*, the optimum v is viAi t"*. Then we can write amax (1 + 3 + (4.77) EFTA00748945 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 79 Thus, when M/K* is large, Erma? grows like MK*. We can also calculate a„. for a fixed number of sets M. Since If* is a function of L, K and M, each case has to be studied separately. For instance, if L = K = 1, then K* = 1 and thus o,,,ar is proportional to VM for AI large enough. If K ≥ 1 and L = K = M/2 we find r = M/ (2(5; 1 )). When M is large, M/Ks is also large and thus a„. grows proportional to V2(Alli,;11) 2/11/2/Alibl. Thus, a„. grows exponentially as a function of the number of sets, Al. Figure 55 shows the dependence of offear on M. The decisive condition for strategy A to be favored over B is aR+ S > T + oP (see eqn (4.74)). For a well-mixed population we have o = 1. Larger values of a indicate greater deviation from the well-mixed case and greater effect of the population structure. For o = 1, strategy A is selected if R+S > T+ P. In a coordination game (R > T and S < P) this is the well-known condition of risk- dominance. For large values of a, strategy A is selected if R> P. In a coordination game, this is the well-known condition of Pareto efficiency. Therefore evolutionary dynamics in set structured populations help to achieve the efficient equilibrium. EFTA00748946 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 80 10 is 20 (a) Fig. S 4.5: amax as a function of the number of sets M. We define amax to be the maximum value of a given by eqn (4.76). (a) L = K = 1. (b) L = K = Appendix - Analytic proof Let coi represent the average number of offspring of individual i. After one update step (which is one generation) we have: - h N (4.78) An individual is chosen to be a parent with probability given by its payoff relative to the total payoff and this choice is made independently N times per update step. Using EFTA00748947 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 81 (4.2) we can rewrite the denominator jj = N + We are interested in the limit co; =1+8 —csi hi • E hj — K [ i of co as: — c) E 35 (hj • E hi — 1 of weak selection, 6 0. Then, (4.78) + bhi • E sah, _ b — c E sisjhj . h1 i#i N 1,5,1 becomes +O(62) (4.79) (4.80) Let p denote the frequency of cooperators in the population. We think about an update step as having two parts: a selection part and a mutation part. We want to study the effect of mutation and selection on the average change in p. We denote by (Ap)sd the effect due to selection, and by (Ap)mut the effect due to mutation. Since the average value of p is constant, these effects must cancel: (AP)sel (AP)mut = 0 (4.81) In what follows, we will show that (Ap)„.1 is continuous as a function of 6. Then, we can write its Taylor expansion at 6 = 0 using the fact that when 6 = 0 both of the above terms go to zero due to the symmetry of strategies in the neutral state (Ap)set = 0 + 6(.Ap)2? + O(62) (4.82) Here (4)21 is the first derivative of (48,p).th with respect to 6, evaluated at 6 = 0. Thus, when (Ap)(6.11 is positive, it means that there is an increase in the frequency of cooperators due to selection. In this case, selection favors cooperators. If it is negative, then selection favors defectors. Therefore, for the critical parameter values we must have (Ap)(.11 = 0 (4.83) This condition holds for arbitrary values of the mutation rates. As the mutation rate goes to zero, the above equation corresponds to the equality of the fixation probabilities. EFTA00748948 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 82 We will next detail the calculation of the change due to selection which we can write as (AP).th = E(AP)s • irs (4.84) S Here (a,p)s is the average number of A individuals in a given state S of the system and as is the probability to find the system in that state. Next we detail the calculation of this quantity. Let si be the strategy of individual i, where si = 1 denotes A and si = 0 denotes B. Then, in a given state S of the system, the expected change of p due to selection in one update step is the number of offspring of A individuals minus the number of A individuals in the previous generation, divided by the population size. Thus, it is given by (AP)s = — N (Esicoi — E (4.85) where we is the expected number of offspring of individual i. Prom (4.80), we see that Loi is a polynomial in 6. Hence, (Ap)s is also a polynomial in S and thus it is continuous and infinitely differentiable at 6 = 0. Hence, we can write the Taylor expansion, using the fact that for the we function (4.80), (Ape = 0 (b,p)s = 0 + 6 d(ap)s + O(52) = wir E st d6 6=0 dwi O(52) 6=0 The probability rs that the system is in state S is also a function of S. We will show that as is continuous and infinitely differentiable around S = 0 and thus that we can write its Taylor expansion (4.86) ITS = IT(1 ) orr + O(52) (4.87) The 0 superscript refers to the neutral state, S = 0 and 741) is the first derivative of irs as a function of 6, evaluated at S = 0. Next we show that irs is continuous at S = 0 for all S. In order to find irs, we need the transition probabilities P,7 to go from state Si to state Si. Then the stationary distribution EFTA00748949 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 83 is given by a vector of probabilities rs, which is a normalized eigenvector corresponding to eigenvalue 1 of the stochastic matrix P. In our case, for the Wright-Fisher process with mutation, there is no absorbing subset of states. From every state of the system you can eventually reach every other state. This means that the matrix P is primitive, i.e. there exists some integer k such that Pk 7 0. For a primitive, stochastic matrix P, the Perron-Frobenius theorem ensures that 1 is its largest eigenvalue, that it is a simple eigenvalue and that it has a corresponding unique eigenvector with positive entries summing up to 1. This is precisely our vector of probabilities which gives the stationary distribution. To find this eigenvector we perform Gaussian elimination (also referred to as row echelon reduction) on the system Pv = v. Since 1 is a simple eigenvalue for P, the system we need to solve has only one degree of freedom; thus we can express the eigenvector in terms of the one free variable, which without loss of generality can be iv V1 = - Vnal, • • • vi = - WA, • • • vn-1 = - van-1 (4.88) The eigenvector that we are interested in is the vector with non-zero entries which sum up to 1. For this vector we have 1 = vn(-al - - an-1 + 1) (4.89) This proof is general for any primitive stochastic matrix. Let us now return to our structure and the %VF process. In our case, the transition probabilities come from the fitness f =1+8.payoff; they are fractions of such expressions and thus they are continuous at 6 = 0 and have Taylor expansions around 6 = 0. Thu.s, we can write all transition probabilities as polynomials in S. Because of the elementary nature of the row operations performed, the elements of the reduced matrix are fractions of polynomials (i.e. rational functions of 6). Thus, a; above are all rational functions of S. Therefore, from (4.89) we conclude that EFTA00748950 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 84 vn must also be a rational function of 6. This implies that in our vector of probabilities, all the entries are rational functions. Thus rrs is a fraction of polynomials in 6 which we write in irreducible form. The only way that this is not continuous at 8 = 0 is if the denominator is zero at 6 = 0. But in that case, lim,5_0 irs = co which is impossible since as is a probability. Therefore, irs is continuous at 6 = 0. Once we have the Taylor expansions for both (Ap)s and rrs we can substitute them into (4.84) to obtain (AAA = E(Ap)s Trs = 8 E d(Ap)s 74(9 + O(81 (4.90) d6 = E (E sit I ) +O(62) (4.91) s s .5=o (Esirs) ° Cal (4.92) The last line is just notation. The angular brackets denote the average and the 0 subscript refers to the neutral state S = 0. Note that we start by writing the average change in the presence of the game in equation (4.90) and we end up with an expression depending on the neutral state (4.92), but containing the parameters b and c. Therefore we have shown that we only need to do our calculations in the neutral state. Now using (4.80) in (4.92), the first derivative of the effect of selection in the stationary state evaluated at 6 = 0 becomes (Apc = N[-c (Esniiki • hi ) — K(b — c)(Es i) + Kb e (Esisj) b — c + b (E sismihi • n.1) + N (E sisnik • ht) (4.93) As discussed above, the critical We ratio is obtained when equation (4.83) holds. EFTA00748951 Chapter 4: Supplementary Information for Evolutionary Dynamics in Set Structured Populations 85 From this we obtain 1 1 ( x K b * cid sot" - hog - A,-,E1,1,, sisaishi - heo — K(Ei silo + xi ‘E1,1 sisj)o g (Eid sisniihi • hi),„ - k (E4111sisivhi • hi)0 - if (E 1 81)0 + hr (ad gisi)0 (4.94) Hence, we have derived the expression for the critical b/c ratio given by (4.12). EFTA00748952 Chapter 5 Mutation—selection equilibrium in games with multiple strategies 5.1 Introduction Evolutionary game theory is the study of frequency dependent selection [87, 86, 55, 56, 113]. The individuals of a population can adopt one of several strategies, which can be seen as genotypes or phenotypes. The payoff for each strategy is a linear function of the relative frequencies of all strategies. The coefficients of this linear function are the entries of the payoff matrix. Payoff is interpreted as fitness: individuals reproduce at rates that are proportional to their payoff. Reproduction can be genetic or cultural. Evolutionary game theory provides a theoretical foundation for understanding human and animal behavior [132, 86, 36, 9, 7, 129]. Applications of evolutionary game theory include games among viruses [159, 160] and bacteria [68] as well as host-parasite interactions [106]. Cellular interactions within the human body can also be evolutionary games. As an example we mention the combat between the immune system and virus infected cells [102, 86 EFTA00748953 Chapter 5: Mutation-selection equilibrium in games with multiple strategies 87 84, 14]. The ubiquity of evolutionary game dynamics is not surprising, because evolutionary game theory provides a fairly general approach to evolutionary dynamics [100]. There is also an equivalence between fundamental equations of ecology [81] and those of evolutionary game theory [55]. Let us consider a game with n strategies. The payoff values are given by the n x rt payoff matrix A = [au]. This means that an individual using strategy i receives payoff au when interacting with an individual that uses strategy j. For understanding a game it is useful to explore whether any of the strategies are Nash equilibria [94, 86, 147, 19]. Strategy k is a strict Nash equilibrium if akk > ath for all i k. Strategy k is a Nash equilibrium if akk ≥ aik for all i. Another useful concept is that of an evolutionarily stable strategy (ESS) [87, 86, 85]. Strategy k is ESS if either (i) akk > aik or (ii) akk = and aki > ate holds for all i k. We have the following implications: if k is a strict Nash equilibrium then it is an ESS; if k is an ESS then it is a Nash equilibrium. Both Nash and ESS, however, give conditions on whether a strategy, which is played by the majority of players, outperforms all other strategies. Hence they identify the `favored' strategy based on its performance at large frequencies. The traditional approach to evolutionary game dynamics uses well-mixed populations of infinite size. In this case the deterministic selection dynamics can be described by the replicator equation, which is an ordinary differential equation defined on the simplex S. [147, 165]. Many interesting properties of this equation are described in the book by [55]. More recently there have been efforts to study evolutionary game dynamics in popu- lations of finite size [125, 131, 65, 66, 32, 29, 133, 110, 142, 166, 152]. For finite populations a stochastic description is necessary. Of particular interest is the fixation probability of a strategy [110, 5, 75]: the probability that a single mutant strategy overtakes a homogeneous population which uses another strategy. When only two strategies are involved, the strategy EFTA00748954 Chapter 5: Mutation-selection equilibrium in games with multiple strategies 88 with higher fixation probability is considered to be more `favored' by selection. We can take a game of n strategies and analyze all pairwise fixation probabilities to find which strategies are favored by selection [63]. This concept, in some way, compares strategies at all relative frequencies during the fixation process, as opposed to the Nash and ESS conditions. The study of fixation probabilities, however, is only conclusive for small mutation rates, which means most of the time all players use the same strategy. In this paper, we propose a more general way of identifying the strategy most favored by selection: it is the strategy with the highest average frequency in the long time average. For brevity we call throughout this paper the average frequency of a strategy in the stationary state its abutulance. The criteria for higher abundance can be used for arbitrary mutation rates. Moreover, for small mutation rates this criteria can be formulated in terms of pairwise fixation probabilities. In particular, we focus on stochastic evolutionary dynamics in populations of finite size N, although for simplicity we shall consider the large (but still finite) population size limit. Evolutionary updating occurs according to the frequency dependent Moran process [110, 142], but the Wright Fisher process [63] and the Pairwise Comparison process [137, 156] are also discussed; the details of these processes are explained in the next sections. In addition, we assume that individuals reproduce proportional to their payoffs but subject to mutation with probability u > 0. With probability 1— u the imitator (or offspring) adopts the strategy of the teacher (or parent); with probability u one of the n strategies is chosen at random. We study the case of weak selection. For the frequency dependent Moran process, the payoff of strategy i is given by fi = 1 + car, which is the baseline payoff, 1, plus the payoff of strategy i obtained in the games, weighted by the intensity of selection 6 > 0. Weak selection means 6 cc 1/N. In this case, although the frequencies of the strategies can EFTA00748955 Chapter 5: Mutation-selection equilibrium in games with multiple strategies 89 widely fluctuate in time, all strategies have approximately the same abundance (average frequency), 1/n, in the stationary distribution of the mutation-selection process. We are interested in the deviation from this uniform distribution. To calculate this deviation we use a perturbation theory in the selection strength, 6. Here we follow the methods developed in [4] for studying two strategies in a phenotype space. Perturbation studies can also be found in [127] for subdivided populations. In this paper we study n-strategy games in a well mixed population of N players. We consider that selection favors a strategy if its abundance (average frequency) exceeds 1/n. Conversely, selection opposes a strategy, if its abundance is less than 1/n. We establish the following results. For low mutation probability (u GG 1/N), we find that selection favors strategy k if Lk = —n E(akk + aki — aik — au) > 0. For high mutation probability (u. > 1/N), selection favors strategy k if n n Hk = E Daki — aii) > O. i=1 j=t (5.1) (5.2) For arbitrary mutation probability the general expression for selection to favor strategy k is Lk + NUilk> 0. Strategy k is more abundant than strategy j if Lk + NUHk> Ntlf f 3 . (5.3) (5.4) All these results hold for large but finite population size, 1 <G N <G 1/8. They allow a complete characterization of n x n games in the limit of weak selection. The equilibrium frequencies of each strategy are also given in the paper. We can gain some qualitative understanding of our low (5.1) and high (5.2) mutation rate results. For low mutation rates, most of the time, all players use the same strategy EFTA00748956 Chapter 5: Mutation-selection equilibrium in games with multiple strategies 90 until another strategy takes over. There are only two strategies involved in a takeover. A single k-player fixates in all i-players with a higher probability than a single i-player into k-players, if akk +ak; — aik — 0 [100]. For only two strategies present, a higher fixation probability for k means that it is more abundant. Hence strategy k is the most abundant among all strategies if it fixates well against all strategies, which then explains expression (5.1). Conversely, for high mutation rates the frequencies of all strategies are close to 1/n all the time. Hence the payoff of strategy k is roughly fk = 1 + (61n)E;=, akj. One has to compare this payoff to the average payoff of the population (1/n) a which leads to expression (5.2). The rest of the paper is structured as follows. In Section 5.2, we derive the gen- eral conditions for strategy abundance for any mutation rates. Section 5.3 provides three concrete examples. Possible extensions of our method to strong selection, more general mutation rates, the Wright-Fisher and the Pairwise Comparison processes are discussed in Section 5.4. We summarize our results in Section 5.5. 5.2 Perturbation method Let us consider a well mixed population of N players. Each of them plays one of the n > 2 strategies. The state of the system is described by the n-dimensional column vector X, where Xi is the number of players using strategy i. The frequencies of strategies are x = X/N. The payoff matrix is given by then x n matrix A = Lau], where au is the payoff of an i-player playing against a j-player. The payoff of an individual using strategy i is f, and the column vector f is given by f = 1 + 8Ax. Here 6 > 0 is the selection strength, and = 1 (for all i) is the baseline payoff. The term AX/N = Ax in the player's payoff stands for the average contribution from all other players through the game. We included EFTA00748957 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