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