1 Bacterial Games Erwin Frey and Tobias Reichenbach 1 Arnold-Sommerfeld-Center for Theoretical Physics and Center for NanoScience, Ludwig-Maximilians-Universit¨at Mu¨nchen, Theresienstrasse 37, 80333 Mu¨nchen, Germany 2 Howard HughesMedical Instituteand Laboratory of Sensory Neuroscience, The Rockefeller University,New York,New York 10065-6399, U.S.A. Abstract. Microbiallaboratorycommunitieshavebecomemodelsystemsforstudy- ing the complex interplay between nonlinear dynamics of evolutionary selection forces, stochastic fluctuations arising from the probabilistic nature of interactions, andspatialorganization.Majorresearchgoalsaretoidentifyandunderstandmech- anisms that ensures viability of microbial colonies by allowing for species diversity, cooperativebehaviorandotherkindsof“social” behavior.Asynthesisofevolution- ary game theory, nonlinear dynamics, and the theory of stochastic processes pro- videsthemathematicaltoolsandconceptualframework foradeeperunderstanding of these ecological systems. We give an introduction into the modern formulation of these theories and illustrate their effectiveness focussing on selected examples of microbialsystems.Intrinsicfluctuations,stemmingfromthediscretenessofindivid- uals,areubiquitous,andcanhaveimportant impactonthestability ofecosystems. Intheabsenceofspeciation,extinctionofspeciesisunavoidable,may,however,take very long times. We provide a general concept for defining survival and extinction onecological time-scales.Spatialdegreesoffreedomcomewithacertainmobilityof individuals.Whenthelatterissufficientlyhigh,bacterialcommunitystructurescan beunderstoodthroughmappingindividual-basedmodels,inacontinuumapproach, ontostochasticpartialdifferentialequations.Theseallowprogressusingmethodsof nonlinear dynamics such as bifurcation analysis and invariant manifolds. We con- clude with a perspective on the current challenges in quantifying bacterial pattern formation, and how this might have an impact on fundamental research in non- equilibrium physics. 2 Erwin Frey and Tobias Reichenbach 1.1 Introduction Microbial systems are complex assemblies of large numbers of individuals, interacting competitively under multifaceted environmental conditions. Bac- teria often grow in complex, dynamical communities, pervading the earth’s ecologicalsystems, from hot springs to rivers and the human body [1]. As an example,inthelattercase,theycancauseanumberofinfectiousdiseases,such as lung infection by Pseudomonas aeruginosa. Bacterial communities, quite generically, form biofilms [1,2], i.e., they arrange into a quasi-multi-cellular entity where they highly interact. These interactions include competition for nutrients,cooperationbyprovidingvariouskindsofpublic goodsessentialfor theformationandmaintenanceofthebiofilm[3],communicationthroughthe secretionand detectionof extracellularsubstances [4,5], chemicalwarfare[7], and last but not least physical forces. The ensuing complexity of bacterial communities has conveyed the idea that they constitute a kind of “social groups” where the coordinated action of individuals leads to various kinds of system-level functionalities [6]. Since additionally microbial interactions can be manipulated in a multi- tude of ways, many researchers have turned to microbes as the organisms of choice to explore fundamental problems in ecology and evolutionary dynam- ics [7,8,9]. Much effort is currently devoted to qualitative and quantitative understanding of basic mechanisms that maintain the diversity of microbial populations. Hereby,withinexemplarymodels,theformationofdynamicspa- tial patterns has been identified as a key promoter [10,11,12,13]. In partic- ular, the crucial influence of self-organized patterns on biodiversity has been demonstrated in recent experimental studies [7], employing three bacterial strainsthatdisplaycycliccompetition.Thelatterismetaphoricallydescribed by the game “rock-paper-scissors” where rock smashes scissors, scissors cut paper, and paper wraps rock in turn. For the three bacterial strains, and for low microbes motility, cyclic dominance leads to the stable coexistence of all three strains through self-formation of spatial patterns. In contrast, stirring the system,ascanalsoresultfromhighmotilities of the individuals,destroys the spatialstructureswhichresultsinthe take overofonesubpopulationand the extinction of the others after a short transient. There is also an ongoing debate in sociobiology how cooperation within a population emerges in the first place and how it is maintained in the long run. Microbial communities again serve as versatile model systems for exploring these questions [8,9]. In those systems, cooperators are producers of a common good, usually a metabolically expensive biochemical product. Hence a successfully cooperat- ing collective of microbes permanently runs the risk to be undermined by non-producing strains (“cheaters”) saving the metabolically costly supply of biofilm formation [14,3]. As partial resolutions to this puzzling dilemma re- cents studies emphasize nonlinear benefits [8] and population bottlenecks in permanently regrouping populations [9]. 1 Bacterial Games 3 This article is intended as an introduction into some of the theoretical concepts which are useful in deepening our understanding of these systems. We will start with an introduction to the language of game theory and after a short discussion of “strategic games” quickly move to “evolutionary game theory”. The latter is the natural framework for the evolutionary dynamics of populations consisting of interacting multiple species, where the success of a given individual depends on the behavior of the surrounding ones. It is most naturally formulated in the language of nonlinear dynamics, where the gametheoryterms“Nashequilibrium”or“evolutionarystablestrategy”map onto “fixed points” of ordinary nonlinear differential equations. Illustrations of these concepts are given in terms of two-strategy games and the cyclic Lotka-Volterra model, also known as the “rock-paper-scissors” game. Before embarking on the theoretical analysis of the role of stochasticity and space we give, in a short chapter 3, some examples of game-theoreticalproblems in biology, mainly taken from the field of microbiology. A deterministic description of populations of interacting individuals in terms of nonlinear differential equations misses some important features of actualecologicalsystems.The molecularprocessesunderlying the interaction between individuals are often inherently stochastic and the number of indi- vidualsis alwaysdiscrete.Asaconsequence,there arerandomfluctuationsin thecompositionofthepopulationwhichcanhaveanimportantimpactonthe stability of ecosystems. In the absence of speciation, extinction of species is unavoidable,may, however,take very long times. Chapter 4 starts with some elementary, but very important, notes on extinction times, culminating in a generalconcept for defining survival and extinction on ecologicaltime scales. These ideas are then illustrated for the rock-scissors-papergame. Cycliccompetitionofspecies,asmetaphoricallydescribedbythechildrens game“rock-paper-scissors”,isanintriguingmotifofspeciesinteractions.Lab- oratoryexperiments onpopulations consisting ofdifferent bacterialstrains of E. coli have shown that bacteria can coexist if a low mobility enables the segregation of the different strains and thereby the formation of patterns [7]. In chapter5 we analyzethe impact ofstochasticityas wellas individuals mo- bility on the stability of diversity as well as the emerging patterns. Within a spatially-extendedversionoftheMay-Leonardmodel[15]wedemonstratethe existence of a sharpmobility threshold[13], suchthat diversity is maintained below, but jeopardized above that value. Computer simulations of the ensu- ing stochastic cellular automaton show that entangled rotating spiral waves accompany biodiversity. In our final chapter we conclude with a perspective on the current challenges in quantifying bacterial pattern formation and how this might also have an impact on fundamental research in non-equilibrium physics. 4 Erwin Frey and Tobias Reichenbach 1.2 The language of game theory 1.2.1 Strategic games and social dilemmas Classical game theory [16] describes the behavior of rational players. It at- tempts to mathematically capture behavior in strategic situations, in which an individual’s success in making choices depends on the choices of others. A classical example of a strategic game is the prisoner’s dilemma. It can be formulatedasakindofapublicgood game whereacooperatorprovidesaben- efit b to another individual, at a cost c to itself (with b c>0). In contrast, − a defector refuses to provide any benefit and hence does not pay any costs. For the selfish individual, irrespective of whether the partner cooperates or defects, defection is favorable, as it avoids the cost of cooperation, exploits cooperators,and ensures not to become exploited. However, if all individuals act rationally and defect, everybody is, with a gain of 0, worse off compared touniversalcooperation,whereanetgainofb c>0wouldbeachieved.This − unfavorable outcome of the game, where both play “defect”, is called Nash equilibrium [17].The prisoner’sdilemma thereforedescribes,inits mostbasic form, the fundamental problem of establishing cooperation.It is summarized in the following payoff matrix (for the column player): P Cooperator(C) Defector(D) C b c c − − D b 0 Thisschemecanbegeneralizedtoincludeotherbasictypesofsocialdilem- mas [18,19]. Namely, two cooperators that meet are both rewarded a payoff , while two defectors obtain a punishment . When a defector encounters R P a cooperator, the first exploits the second, gaining the temptation , while T the cooperator only gets the suckers payoff . Social dilemmas occur when S > , such that cooperation is favorable in principle, while temptation to R P defect is large: > , > . These interactions may be summarizedby the T S T P payoff matrix: P Cooperator(C) Defector(D) C R S D T P Variationoftheparameters , , and yieldsfourdistincttypesofgames. T P R S Theprisoner’s dilemma arisesifthetemptation todefectislargerthanthe T reward , and if the punishment is larger than the suckers payoff . As R P S we have already seen above, in this case, defection is the best strategy for the selfish player. Within the three other types of games, defectors are not always better off. For the snowdrift game the temptation is still higher T than the reward but the sucker’s payoff is larger than the punishment R S . Therefore,now actually cooperationis favorablewhen meeting a defector, P but defection pays off when encountering a cooperator, and a rational strat- egy consists of a mixture of cooperation and defection. The snowdrift game 1 Bacterial Games 5 derives its name from the potentially cooperative interaction present when two drivers are trapped behind a large pile of snow, and each driver must decide whether to clear a path. Obviously, then the optimal strategy is the oppositeofthe opponent’s(cooperatewhenyouropponentdefects anddefect when your opponent cooperates). Another scenario is the coordination game, wheremutualagreementispreferred:eitherallindividualscooperateordefect as the reward is higher than the temptation and the punishment is R T P higher than sucker’s payoff . Lastly, the scenario of by-product mutualism S (also called harmony) yields cooperators fully dominating defectors since the reward is higherthan the temptation andthe sucker’spayoff is higher R T S than the punishment . P 1.2.2 Evolutionary game theory Strategic games are thought to be a useful framework in economic and social settings.Inordertoanalyzethebehaviorofbiologicalsystems,theconceptof rationalityisnotmeaningful.EvolutionaryGameTheory(EGT),asdeveloped mainly by Maynard Smith and Price [20,21], does not rely on rationality assumptionsbutontheideathatevolutionaryforceslikenaturalselectionand mutation arethe driving forces ofchange.The interpretationof game models in biology is fundamentally different from strategic games in economics or social sciences. In biology, strategies are considered to be inherited programs which control the individual’s behavior. Typically one looks at a population composedofindividualswithdifferentstrategieswhointeractgenerationafter generation in game situations of the same type. The interactions may be described by deterministic rules or stochastic processes, depending on the particular system under study. The ensuing dynamic process can then be viewed as an iterative (nonlinear) map or a stochastic process (either with discreteorcontinuoustime).Thisnaturallyputsevolutionarygametheoryin the contextof nonlinear dynamics and the theory of stochastic processes.We will see later on how a synthesis of both approaches helps to understand the emergence of complex spatio-temporal dynamics. In this section, we focus on a deterministic description of well-mixed pop- ulations. The term “well-mixed” signifies systems where the individual’s mo- bility (or diffusion) is so large that one may neglect any spatial degrees of freedom and assume that every individual is interacting with everyoneat the same time. This is a mean-field picture where interactions are given in terms oftheaveragenumberofindividualsplayingaparticularstrategy.Frequently, this situation is visualized as an “urn model”, where two individuals from a population are randomly selected to play with each other according to some specified game theoretical scheme. The term “deterministic” means that we areseekingadescriptionofpopulationswherethenumberofindividualsN (t) i playingaparticularstrategyA aremacroscopicallylargesuchthatstochastic i effects can be neglected. 6 Erwin Frey and Tobias Reichenbach Fig. 1.1. The urn model describes the evolution of well-mixed finite populations. Here, as an example, we show three species as yellow (A), red (B), and blue (C) spheres.Ateachtimestep,tworandomlyselectedindividualsarechosen(indicated byarrows in theleft picture) andinteract with each otheraccording to therules of thegame resulting in an updated composition of thepopulation (right picture). Pairwise reactions and rate equations In the simplest setup the interaction between individuals playing different strategies can be represented as a reaction process characterized by a set of rateconstants.Forexample,consideragamewherethreestrategies A,B,C { } cyclically dominate each other, as in the rock-paper-scissorsgame: A invades B, B outperforms C, and C in turn dominates over A, schematically drawn in Fig.1.2: A C B Fig. 1.2. IllustrationofcyclicdominanceofthreestatesA,B,andC:AinvadesB, B outperforms C, and C in turn dominates over A. In an evolutionary setting, the game may be played according to an urn model as illustrated in Fig.1.1: at a given time t two individuals from a pop- ulation with constant size N are randomly selected to play with each other (react) according to the reaction scheme A+B kA A+A, −→ B+C kB B+B, (1.1) −→ C+A kC C+C, −→ where k are rate constants, i.e. probabilities per unit time. This interaction i scheme is termed a cyclic Lotka-Volterra model 3. It is equivalent to a set of 3 Thetwo-speciesLotka-Volterraequationsdescribeapredator-preysystemwhere theper-capitagrowthrateofpreydecreaseslinearlywiththeamountofpredators 1 Bacterial Games 7 chemical reactions, and in the deterministic limit of a well-mixed population one obtains rate equations for the frequencies (a,b,c)=(N ,N ,N )/N: A B C ∂ a = a(k b k c), t A C − ∂ b= b(k c k a), (1.2) t B A − ∂ c = c(k a k b). t C B − Here the right hand sides gives the balance of “gain” and “loss” processes. The phase space of the model is the simplex S3, where the species’ densities are constrained by a+b+c = 1. There is a constant of motion for the rate equations, Eq.(1.3), namely the quantity ρ := akBbkCckA does not evolve in time [25]. As a consequence, the phase portrait of the dynamics, shown in Fig. 1.3, yield neutrally stable cycles with fixed ρ around the reactive fixed point F. This implies that the deterministic dynamics is oscillatory with the amplitude and frequency determined by the initial composition of the popu- lation. Fig. 1.3. The three-species simplex for reaction rates kA = 0.2, kB = 0.4, kC = 0.4. Since there is a conserved quantity, the rate equations predict cyclic orbits of constant ρ=akBbkCckA; F signifies the neutrally stable reactive fixedpoint. The concept of fitness and replicator equations Another line of thought to define an evolutionary dynamics, often taken in the mathematical literature of evolutionary game theory [24,25], introduces the concept of fitness and then assumes that the per-capita growth rate of a strategy A is given by the surplus in its fitness with respect to the average i fitness of the population. We will illustrate this reasoning for two-strategy present.Intheabsenceofprey,predatorsdie,butthereisapositivecontribution totheirgrowth which increaseslinearly withtheamount ofpreypresent[22,23]. 8 Erwin Frey and Tobias Reichenbach games with a payoff matrix given by Eq. (1.2.1). Let N and N be the A B number of individuals playing strategy A (cooperator) and B (defector) in a population of size N =N +N . Then the relative abundances of strategies A B A and B are given by N N A B a= , b= =(1 a). (1.3) N N − The “fitness” of a particular strategy A or B is defined as a constant back- ground fitness, set to 1, plus the average payoff obtained from playing the game: f (a):= 1+ a+ (1 a), (1.4) A R S − f (a):= 1+ a+ (1 a). (1.5) B T P − In order to mimic an evolutionary process one is seeking a dynamics which guarantees that individuals using strategies with a fitness larger than the av- eragefitnessincreasewhile thoseusingstrategieswithafitness belowaverage decline in number. This is, for example, achieved by choosing the per-capita growth rate, ∂ a/a, of individuals playing strategy A proportional to their t surplus in fitness with respect to the averagefitness of the population: f¯(a):=af (a)+(1 a)f (a). (1.6) A B − Theensuingordinarydifferentialequationisknownasthestandard replicator equation [24,25] ∂ a= f (a) f¯(a) a. (1.7) t A − (cid:2) (cid:3) Lacking a detailed knowledge of the actual “interactions” of individuals in a population, there is, of course, plenty of freedom in how to write down a differentialequationdescribingtheevolutionarydynamicsofapopulation.In- deed,thereisanothersetofequationsfrequentlyusedinEGT,calledadjusted replicator equations, which reads f (a) f¯(a) A ∂ a= − a. (1.8) t f¯(a) The correct form to be used in an actual biologicalsetting may be neither of these standard formulations. Typically, some knowledge about the molecular mechanisms is needed to formulate a realistic dynamics. As we will learn in section 1.3 the functional form of the payoff depends on the microbes’ metabolismandis,ingeneral,anonlinearfunctionoftherelativeabundances of the various strains in the population. One may also criticise the assumption of constant population size made in evolutionary game theory. The internal evolution of different traits and the dynamics of the species population size are in fact not independent [26]. 1 Bacterial Games 9 Species typical coevolve with other species in a changing environment and a separatedescriptionofboth,evolutionaryandpopulationdynamics,isingen- eral not justified. In particular,a species’ population dynamics does not only affect the evolution within each species as considered for example by models of density-dependent selection [27] but population dynamics is also biased by the internalevolutionof different traits. One visualexample for this coupling arebiofilmswhichpermanentlygrowandshrink.Inthesemicrobialstructures diversestrainslive,interact,andoutcompete eachotherwhile simultaneously affecting the population size [14]. A proper combined description of the total temporal development should therefore be solely based on isolated birth and death events, as recently suggested in Ref. [28]. Such an approach offers also a more biological interpretation of evolutionary dynamics than common for- mulations like the Fisher-Wright or the Moran process [29,30,31,32]: fitter individuals prevaildue to higher birth rates and not by winning a tooth-and- claw struggle where the birth of one individual directly results in the death of another one. 1.2.3 Nonlinear dynamics of two-player games Thissectionisintendedtogiveaconciseintroductionintoelementaryconcepts of nonlinear dynamics [33]. We illustrate those for the evolutionarydynamics of two-player games characterized in terms of the payoff matrix, Eq.(1.2.1), and the ensuing replicator dynamics ∂ a = a(f f¯)=a(1 a)(f f ). (1.9) t A A B − − − This equation has a simple interpretation: the first factor, a(1 a), is the − probabilityfor AandB to meetandthe secondfactor,f f ,is the fitness A B − advantageofAoverB.Insertingtheexplicitexpressionsforthefitnessvalues one finds ∂ a=a(1 a) µ (1 a) µ a =:F(a), (1.10) t A B − − − (cid:2) (cid:3) where µ is the relativebenefit of A playing againstB and µ is the relative A B benefit of B playing against A: µ := , µ := . (1.11) A B S−P T −R Eq.1.10 is a one-dimensional nonlinear first-oder differential equation for the fraction a of players A in the population, whose dynamics is most easily analyzed graphically.The sign of F(a) determines the increase or decrease of the dynamic variable a; compare the right half of Fig.1.4. The intersections of F(a) with the a-axis (zeros) are fixed points, a∗. Generically, these inter- ′ ∗ sections are with a finite slope F (a )=0; a negative slope indicates a stable 6 fixedpointwhile a positiveslope anunstable fixedpoint.Depending onsome control parameters, here µ and µ , the firstor higher order derivatives of F A B 10 Erwin Frey and Tobias Reichenbach µ B Prisoner’s Dilemma Snowdrift Game F(a) µA 0 1 a Coordination Game Harmony Fig. 1.4. Classification of two-player games. Left: The black arrows in the control parameter plane (µA,µB) indicate the flow behavior of the four different types of two-player games. Right: Graphically the solution of a one-dimensional nonlinear dynamics equation, ∂ta = F(a), is simply read off from the signs of the function F(a);illustration for thesnowdrift game. atthe fixedpoints mayvanish.Thesespecialparametervalues mark“thresh- old values” for changes in the flow behavior (bifurcations) of the nonlinear dynamics. We may now classify two-player games as illustrated in Fig.1.4. For the prisoner’s dilemma µ = c < 0 and µ = c > 0 and hence A B − players with strategy B (defectors) are always better off (compare the payoff matrix). Both players playing strategy B is a Nash equilibrium. In terms of the replicator equations this situation corresponds to F(a)<0 for a=0 and ∗ 6 F(a) = 0 at a = 0, 1 such that a = 0 is the only stable fixed point. Hence the term “Nash equilibrium” translates into the “stable fixed point” of the replicator dynamics (nonlinear dynamics). Forthesnowdriftgamebothµ >0andµ >0suchthatF(a)canchange A B ∗ sign for a [0,1]. In fact, a = µ /(µ +µ ) is a stable fixed point while int A A B ∗ ∈ a = 0, 1 are unstable fixed points; see the right panel of Fig.1.4. Inspection of the payoff matrix tells us that it is always better to play the opposite strategy of your opponent. Hence there is no Nash equilibrium in terms of pure strategies A or B. This corresponds to the fact that the boundary fixed ∗ points a = 0, 1 are unstable. There is, however, a Nash equilibrium with a mixed strategy wherearationalplayerwouldplaystrategyAwithprobability p = µ /(µ +µ ) and strategy B with probability p = 1 p . Hence, A A A B B A − again,the term“Nashequilibrium” translatesintothe “stablefixedpoint” of the replicator dynamics (nonlinear dynamics). ∗ For the coordination game, there is also an interior fixed point at a = int µ /(µ +µ ),butnowitisunstable,whilethefixedpointsattheboundaries A A B a∗ = 0, 1 are stable. Hence we have bistability: for initial values a < a∗ the int flowistowardsa=0whileitistowardsa=1otherwise.Intheterminologyof strategicgamestherearetwoNashequilibria.Thegameharmonycorresponds to the prisoner’s dilemma with the roles of A and B interchanged.