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 > (v + 2) + c Al — K 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 [A(p, + A(p, — A(q, p) — A (q, (0]dq. LP= 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) (2.1) B c d 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 10), 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 10), 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