Evolutionary graph theory: breaking the symmetry between interaction and replacement

We study evolutionary dynamics in a population whose structure is given by two graphs: the interaction graph determines who plays with whom in an evolutionary game; the replacement graph specifies the geometry of evolutionary competition and updating. First, we calculate the fixation probabilities of frequency dependent selection between two strategies or phenotypes. We consider three different update mechanisms: birth-death, death-birth and imitation. Then, as a particular example, we explore the evolution of cooperation. Suppose the interaction graph is a regular graph of degree h, the replacement graph is a regular graph of degree g and the overlap between the two graphs is a regular graph of degree l. We show that cooperation is favored by natural selection if b/c>hg/l. Here, b and c denote the benefit and cost of the altruistic act. This result holds for death-birth updating, weak-selection and large population size. Note that the optimum population structure for cooperators is given by maximum overlap between the interaction and the replacement graph (g=h=l), which means that the two graphs are identical. We also prove that a modified replicator equation can describe how the expected values of the frequencies of an arbitrary number of strategies change on replacement and interaction graphs: the two graphs induce a transformation of the payoff matrix.     

Ecological public goods games: cooperation and bifurcation

The Public Goods Game is one of the most popular models for studying the origin and maintenance of cooperation. In its simplest form, this evolutionary game has two regimes: defection goes to fixation if the multiplication factor r is smaller than the interaction group size N, whereas cooperation goes to fixation if the multiplication factor r is larger than the interaction group size N. Hauert et al. [Hauert, C., Holmes, M., Doebeli, M., 2006a. Evolutionary games and population dynamics: Maintenance of cooperation in public goods games. Proc. R. Soc. Lond. B 273, 2565-2570] have introduced the Ecological Public Goods Game by viewing the payoffs from the evolutionary game as birth rates in a population dynamic model. This results in a feedback between ecological and evolutionary dynamics: if defectors are prevalent, birth rates are low and population densities decline, which leads to smaller interaction groups for the Public Goods game, and hence to dominance of cooperators, with a concomitant increase in birth rates and population densities. This feedback can lead to stable co-existence between cooperators and defectors. Here we provide a detailed analysis of the dynamics of the Ecological Public Goods Game, showing that the model exhibits various types of bifurcations, including supercritical Hopf bifurcations, which result in stable limit cycles, and hence in oscillatory co-existence of cooperators and defectors. These results show that including population dynamics in evolutionary games can have important consequences for the evolutionary dynamics of cooperation.     

Spatial invasion of cooperation

The evolutionary puzzle of cooperation describes situations where cooperators provide a fitness benefit to other individuals at some cost to themselves. Under Darwinian selection, the evolution of cooperation is a conundrum, whereas non-cooperation (or defection) is not. In the absence of supporting mechanisms, cooperators perform poorly and decrease in abundance. Evolutionary game theory provides a powerful mathematical framework to address the problem of cooperation using the prisoner's dilemma. One well-studied possibility to maintain cooperation is to consider structured populations, where each individual interacts only with a limited subset of the population. This enables cooperators to form clusters such that they are more likely to interact with other cooperators instead of being exploited by defectors. Here we present a detailed analysis of how a few cooperators invade and expand in a world of defectors. If the invasion succeeds, the expansion process takes place in two stages: first, cooperators and defectors quickly establish a local equilibrium and then they uniformly expand in space. The second stage provides good estimates for the global equilibrium frequencies of cooperators and defectors. Under hospitable conditions, cooperators typically form a single, ever growing cluster interspersed with specks of defectors, whereas under more hostile conditions, cooperators form isolated, compact clusters that minimize exploitation by defectors. We provide the first quantitative assessment of the way cooperators arrange in space during invasion and find that the macroscopic properties and the emerging spatial patterns reveal information about the characteristics of the underlying microscopic interactions.     

Active linking in evolutionary games

In the traditional approach to evolutionary game theory, the individuals of a population meet each other at random, and they have no control over the frequency or duration of interactions. Here we remove these simplifying assumptions. We introduce a new model, where individuals differ in the rate at which they seek new interactions. Once a link between two individuals has formed, the productivity of this link is evaluated. Links can be broken off at different rates. In a limiting case, the linking dynamics introduces a simple transformation of the payoff matrix. We outline conditions for evolutionary stability. As a specific example, we study the interaction between cooperators and defectors. We find a simple relationship that characterizes those linking dynamics which allow natural selection to favour cooperation over defection.     

Global mutations and local mutations have very different effects on evolution, illustrated by mixed strategies of asymmetric binary games

We study the evolutionary effect of rare mutations causing global changes in traits. We consider asymmetric binary games between two players. The first player takes two alternative options with probability x and 1−x; and the second player takes options with probability y and 1−y. Due to natural selection and recurrent mutation, the population evolves to have broad distributions of x and y. We analyze three cases showing qualitatively different dynamics, exemplified by (1) vigilance-intrusion game, (2) asymmetric hawk-dove game and (3) cleaner-client game. We found that the evolutionary outcome is strongly dependent upon the distribution of mutants’ traits, more than the mutation rates. For example in the vigilance-intrusion game, the evolutionary dynamics show a perpetual stable oscillation if mutants are always close to the parent (local-mutation mode), whilst the population converges to a stable equilibrium distribution if mutants can be quite different from the parent (global-mutation mode), even for extremely low mutation rate. When common local mutations and rare global mutations occur simultaneously, the evolutionary outcome is controlled by the latter.     

Evolution of cooperation under -person snowdrift games

In the animal world, performing a given task which is beneficial to an entire group requires the cooperation of several individuals of that group who often share the workload required to perform the task. The mathematical framework to study the dynamics of collective action is game theory. Here we study the evolutionary dynamics of cooperators and defectors in a population in which groups of individuals engage in N-person, non-excludable public goods games. We explore an N-person generalization of the well-known two-person snowdrift game. We discuss both the case of infinite and finite populations, taking explicitly into consideration the possible existence of a threshold above which collective action is materialized. Whereas in infinite populations, an N-person snowdrift game (NSG) leads to a stable coexistence between cooperators and defectors, the introduction of a threshold leads to the appearance of a new interior fixed point associated with a coordination threshold. The fingerprints of the stable and unstable interior fixed points still affect the evolutionary dynamics in finite populations, despite evolution leading the population inexorably to a monomorphic end-state. However, when the group size and population size become comparable, we find that spite sets in, rendering cooperation unfeasible.     

Mutation in evolutionary games can increase average fitness at equilibrium

We study game dynamical interactions between two strategies, A and B, and analyse whether the average fitness of the population at equilibrium can be increased by adding mutation from A to B. Classifying all two by two games with payoff matrix [(a,b),(c,d)], we show that mutation from A to B enhances the average fitness of the whole population (i) if both a and d are less than (b + c)/2 and (ii) if c is less than b. Furthermore, we study conditions for maximizing the productivity of strategy A, and we analyse the effect of mutations in both directions. Depending on the biological system, a mutation in an evolutionary game can be interpreted as a genetic alteration, a cellular differentiation, a change in gene expression, an accidental or deliberate modification in cultural transmission, or a learning error. In a cultural context, our results indicate that the equilibrium payoff of the population can be increased if players sometimes choose the strategy with lower payoff. In a genetic context, we have shown that for frequency-dependent selection mutation can enhance the average fitness of the population at equilibrium.     

Maintenance affects the stability of a two-tiered microbial 'food chain'?

Recent studies have shown that constraints on available resources may play an important role in the evolution of cooperation, especially when individuals do not posses the capacity to recognize other individuals, memory or other developed abilities, as it is the case of most unicellular organisms, algae or even plants. We analyze the evolution of cooperation in the case of a limiting resource, which is necessary for reproduction and survival. We show that, if the strategies determine a prisoner's dilemma, the outcome of the interactions may be modified by the limitation of resources allowing cooperators to invade the entire population. Analytic expressions for the region of cooperation are provided. Furthermore we derive expressions for the connection between fitness, as understood in evolutionary game theory, and resource exchanges, which may be of help to link evolutionary game theoretical results with resource based models.     

For whom is it more beneficial to stop interactions with defectors: Cooperators or defectors?

Cooperation is a mysterious evolutionary phenomenon and its mechanisms require elucidation. When cooperators can stop interactions with defectors, the evolution of cooperation becomes possible; this is one mechanism that facilitates the evolution of cooperation. Here, stopping interactions with defectors is beneficial not only for cooperators but also for defectors. The question then arises, for whom is stopping interactions with defectors more beneficial: cooperators or defectors? By utilizing evolutionary game theory, I addressed this question using a two-player game involving four strategies: (1) cooperators who stop the interaction if the current partner is a defector, (2) cooperators who attempt to maintain a relationship with anyone, (3) defectors who stop the interaction if the current partner is a defector, and (4) defectors who attempt to maintain a relationship with anyone. Our results show that, at equilibrium, the ratio of cooperators who stop the interaction if the current partner is a defector to cooperators who attempt to maintain a relationship with anyone is larger than the ratio of defectors who stop the interaction if the current partner is a defector to defectors who attempt to maintain a relationship with anyone. Thus, cooperators rather than defectors are more likely to stop interactions with defectors at equilibrium. This result is consistent with a previous experimental study in which a positive correlation was detected between the degree of individuals’ cooperativeness and how accurately the individuals recognize whether other individuals are cooperators or defectors. Thus, the theoretical work presented in this study provides relevant insights into the natural phenomena of cooperation and recognition.     

Mutation-selection equilibrium in games with mixed strategies

We develop a new method for studying stochastic evolutionary game dynamics of mixed strategies. We consider the general situation: there are n pure strategies whose interactions are described by an n×n payoff matrix. Players can use mixed strategies, which are given by the vector (p₁,…,p_n). Each entry specifies the probability to use the corresponding pure strategy. The sum over all entries is one. Therefore, a mixed strategy is a point in the simplex S_n. We study evolutionary dynamics in a well-mixed population of finite size. Individuals reproduce proportional to payoff. We consider the case of weak selection, which means the payoff from the game is only a small contribution to overall fitness. Reproduction can be subject to mutation; a mutant adopts a randomly chosen mixed strategy. We calculate the average abundance of every mixed strategy in the stationary distribution of the mutation-selection process. We find the crucial conditions that specify if a strategy is favored or opposed by selection. One condition holds for low mutation rate, another for high mutation rate. The result for any mutation rate is a linear combination of those two. As a specific example we study the Hawk-Dove game. We prove general statements about the relationship between games with pure and with mixed strategies.     

Stochastic evolutionary dynamics of bimatrix games

Evolutionary game dynamics of two-player asymmetric games in finite populations is studied. We consider two roles in the game, roles α and β. α-players and β-players interact and gain payoffs. The game is described by a pair of matrices, which is called bimatrix. One's payoff in the game is interpreted as its fecundity, thus strategies are subject to natural selection. In addition, strategies can randomly mutate to others. We formulate a stochastic evolutionary game dynamics of bimatrix games as a frequency-dependent Moran process with mutation. We analytically derive the stationary distribution of strategies under weak selection. Our result provides a criterion for equilibrium selection in general bimatrix games.     

Stochastic sampling of interaction partners versus deterministic payoff assignment

Evolutionary game dynamics describes how successful strategies spread in a population. In well-mixed populations, the usual assumption, e.g. underlying the replicator dynamics, is that individuals obtain a payoff from interactions with a representative sample of the population. This determines their fitness. Here, we analyze a situation in which payoffs are obtained through a single interaction, so that individuals of the same type can have different payoffs. We show analytically that for weak selection, this scenario is identical to the usual approach in which an individual interacts with the whole population. For strong selection, however, differences arise that are reflected in the fixation probabilities and lead to deviating evolutionary dynamics.     

John Maynard Smith and the importance of consistency in evolutionary game theory

John Maynard Smith was the founder of evolutionary game theory. He has also been the major influence on the direction of this field, which now pervades behavioural ecology and evolutionary biology. In its original formulation the theory had three components: a set of strategies, a payoff structure, and a concept of evolutionary stability. These three key components are still the basis of the theory, but what is assumed about each component is often different to the original assumptions. We review modern approaches to these components. We emphasis that if a game is considered in isolation, and arbitrary payoffs are assumed, then the payoffs may not be consistent with other components of the system which are not modelled. Modelling the whole system, including not only the focal game, but also the future behaviour of the players and the behaviour of other population members, allows a consistent model to be constructed. We illustrate this in the case of two models of parental care, showing how linking a focal game to other aspects of the system alters what is predicted.     

Evolutionary dynamics in structured populations

Evolutionary dynamics shape the living world around us. At the centre of every evolutionary process is a population of reproducing individuals. The structure of that population affects evolutionary dynamics. The individuals can be molecules, cells, viruses, multicellular organisms or humans. Whenever the fitness of individuals depends on the relative abundance of phenotypes in the population, we are in the realm of evolutionary game theory. Evolutionary game theory is a general approach that can describe the competition of species in an ecosystem, the interaction between hosts and parasites, between viruses and cells, and also the spread of ideas and behaviours in the human population. In this perspective, we review the recent advances in evolutionary game dynamics with a particular emphasis on stochastic approaches in finite sized and structured populations. We give simple, fundamental laws that determine how natural selection chooses between competing strategies. We study the well-mixed population, evolutionary graph theory, games in phenotype space and evolutionary set theory. We apply these results to the evolution of cooperation. The mechanism that leads to the evolution of cooperation in these settings could be called ‘spatial selection’: cooperators prevail against defectors by clustering in physical or other spaces.     

Tit-for-tat or win-stay, lose-shift?

The repeated Prisoner's Dilemma is usually known as a story of tit-for-tat (TFT). This remarkable strategy has won both of Robert Axelrod's tournaments. TFT does whatever the opponent has done in the previous round. It will cooperate if the opponent has cooperated, and it will defect if the opponent has defected. But TFT has two weaknesses: (i) it cannot correct mistakes (erroneous moves) and (ii) a population of TFT players is undermined by random drift when mutant strategies appear which play always-cooperate (ALLC). Another equally simple strategy called 'win-stay, lose-shift' (WSLS) has neither of these two disadvantages. WSLS repeats the previous move if the resulting payoff has met its aspiration level and changes otherwise. Here, we use a novel approach of stochastic evolutionary game dynamics in finite populations to study mutation-selection dynamics in the presence of erroneous moves. We compare four strategies: always-defect (ALLD), ALLC, TFT and WSLS. There are two possible outcomes: if the benefit of cooperation is below a critical value then ALLD is selected; if the benefit of cooperation is above this critical value then WSLS is selected. TFT is never selected in this evolutionary process, but lowers the selection threshold for WSLS.     

Adaptive dynamics of cooperation may prevent the coexistence of defectors and cooperators and even cause extinction

It has recently been demonstrated that ecological feedback mechanisms can facilitate the emergence and maintenance of cooperation in public goods interactions: the replicator dynamics of defectors and cooperators can result, for example, in the ecological coexistence of cooperators and defectors. Here we show that these results change dramatically if cooperation strategy is not fixed but instead is a continuously varying trait under natural selection. For low values of the factor with which the value of resources is multiplied before they are shared among all participants, evolution will always favour lower cooperation strategies until the population falls below an Allee threshold and goes extinct, thus evolutionary suicide occurs. For higher values of the factor, there exists a unique evolutionarily singular strategy, which is convergence stable. Because the fitness function is linear with respect to the strategy of the mutant, this singular strategy is neutral against mutant invasions. This neutrality disappears if a nonlinear functional response in receiving benefits is assumed. For strictly concave functional responses, singular strategies become uninvadable. Evolutionary branching, which could result in the evolutionary emergence of cooperators and defectors, can occur only with locally convex functional responses, but we illustrate that it can also result in coevolutionary extinction.     

Spatial effects in social dilemmas

Social dilemmas and the evolutionary conundrum of cooperation are traditionally studied through various kinds of game theoretical models such as the prisoner's dilemma, public goods games, snowdrift games or by-product mutualism. All of them exemplify situations which are characterized by different degrees of conflicting interests between the individuals and the community. In groups of interacting individuals, cooperators produce a common good benefitting the entire group at some cost to themselves, whereas defectors attempt to exploit the resource by avoiding the costly contributions. Based on synergistic or discounted accumulation of cooperative benefits a unifying theoretical framework was recently introduced that encompasses all games that have traditionally been studied separately (Hauert, Michor, Nowak, Doebeli, 2005. Synergy and discounting of cooperation in social dilemmas. J. Theor. Biol., in press.). Within this framework we investigate the effects of spatial structure with limited local interactions on the evolutionary fate of cooperators and defectors. The quantitative effects of space turn out to be quite sensitive to the underlying microscopic update mechanisms but, more general, we demonstrate that in prisoner's dilemma type interactions spatial structure benefits cooperation-although the parameter range is quite limited-whereas in snowdrift type interactions spatial structure may be beneficial too, but often turns out to be detrimental to cooperation.     

How inconsistency between attitude and behavior persists through cultural transmission

Individuals tend to conform their behavior to that of the majority. Consequently, an individual's behavior is not always consistent with his or her attitude, and such inconsistency sometimes causes mental distress. Understanding the mechanism of sustaining inconsistency between attitude and behavior is a challenging problem from the viewpoint of evolutionary theory. We constructed an evolutionary game theory model in which each player has an attitude and behavior toward a single social norm, and the players' attitudes and behaviors are affected by three types of cultural transmission: vertical, oblique, and horizontal. We assumed that strategy is a combination of attitude and behavior and that the process of learning or transmitting the social norm depends on the life stage of each player. Adults play a coordination game in which players whose behaviors match those of the majority obtain a high payoff, which is diminished by any inconsistency between attitude and behavior. The adults' strategies are passed to newborns via vertical transmission, and the frequency of a newborn's replication of strategy is proportional to the corresponding adult's payoff. Newborns imitate behaviors of unrelated adults via oblique transmission. Juveniles change their attitudes or behaviors by observing other juveniles' behaviors or inferring other juveniles' attitudes (horizontal transmission). We conclude that the key factor for sustaining inconsistency between attitude and behavior is the ability of players to infer and imitate others' attitudes, and that oblique transmission promotes inconsistency.     

Evolutionary games on cycles

Traditional evolutionary game theory explores frequency-dependent selection in well-mixed populations without spatial or stochastic effects. But recently there has been much interest in studying the evolutionary game dynamics in spatial settings, on lattices and other graphs. Here, we present an analytic approach for the stochastic evolutionary game dynamics on the simplest possible graph, the cycle. For three different update rules, called 'birth-death' (BD), 'death-birth' (DB) and 'imitation' (IM), we derive exact conditions for natural selection to favour one strategy over another. As specific examples, we consider a coordination game and Prisoner's Dilemma. In the latter case, selection can favour cooperators over defectors for DB and IM updating. We also study the case where the replacement graph of evolutionary updating remains a cycle, but the interaction graph for playing the game is a complete graph. In this setting, all three update rules lead to identical conditions in the limit of weak selection, where we find the '1/3-law' of well-mixed populations.     

Fixation probabilities in evolutionary game dynamics with a two-strategy game in finite diploid populations

Fixation processes in evolutionary game dynamics in finite diploid populations are investigated. Traditionally, frequency dependent evolutionary dynamics is modeled as deterministic replicator dynamics. This implies that the infinite size of the population is assumed implicitly. In nature, however, population sizes are finite. Recently, stochastic processes in finite populations have been introduced in order to study finite size effects in evolutionary game dynamics. One of the most significant studies on evolutionary dynamics in finite populations was carried out by Nowak et al. which describes “one-third law” [Nowak, et al., 2004. Emergence of cooperation and evolutionary stability in finite populations. Nature 428, 646-650]. It states that under weak selection, if the fitness of strategy α is greater than that of strategy β when α has a frequency , strategy α fixates in a β-population with selective advantage. In their study, it is assumed that the inheritance of strategies is asexual, i.e. the population is haploid. In this study, we apply their framework to a diploid population that plays a two-strategy game with two ESSs (a bistable game). The fixation probability of a mutant allele in this diploid population is derived. A “three-tenth law” for a completely recessive mutant allele and a “two-fifth law” for a completely dominant mutant allele are found; other cases are also discussed.