Strategy selection in structured populations

Evolutionary game theory studies frequency dependent selection. The fitness of a strategy is not constant, but depends on the relative frequencies of strategies in the population. This type of evolutionary dynamics occurs in many settings of ecology, infectious disease dynamics, animal behavior and social interactions of humans. Traditionally evolutionary game dynamics are studied in well-mixed populations, where the interaction between any two individuals is equally likely. There have also been several approaches to study evolutionary games in structured populations. In this paper we present a simple result that holds for a large variety of population structures. We consider the game between two strategies, A and B, described by the payoff matrix . We study a mutation and selection process. For weak selection strategy A is favored over B if and only if σa+b>c+σd. This means the effect of population structure on strategy selection can be described by a single parameter, σ. We present the values of σ for various examples including the well-mixed population, games on graphs, games in phenotype space and games on sets. We give a proof for the existence of such a σ, which holds for all population structures and update rules that have certain (natural) properties. We assume weak selection, but allow any mutation rate. We discuss the relationship between σ and the critical benefit to cost ratio for the evolution of cooperation. The single parameter, σ, allows us to quantify the ability of a population structure to promote the evolution of cooperation or to choose efficient equilibria in coordination games.     

Evolutionary stability and quasi-stationary strategy in stochastic evolutionary game dynamics

Stochastic evolutionary game dynamics for finite populations has recently been widely explored in the study of evolutionary game theory. It is known from the work of Traulsen et al. [2005. Phys. Rev. Lett. 95, 238701] that the stochastic evolutionary dynamics approaches the deterministic replicator dynamics in the limit of large population size. However, sometimes the limiting behavior predicted by the stochastic evolutionary dynamics is not quite in agreement with the steady-state behavior of the replicator dynamics. This paradox inspired us to give reasonable explanations of the traditional concept of evolutionarily stable strategy (ESS) in the context of finite populations. A quasi-stationary analysis of the stochastic evolutionary game dynamics is put forward in this study and we present a new concept of quasi-stationary strategy (QSS) for large but finite populations. It is shown that the consistency between the QSS and the ESS implies that the long-term behavior of the replicator dynamics can be predicted by the quasi-stationary behavior of the stochastic dynamics. We relate the paradox to the time scales and find that the contradiction occurs only when the fixation time scale is much longer than the quasi-stationary time scale. Our work may shed light on understanding the relationship between the deterministic and stochastic methods of modeling evolutionary game dynamics.     

A review of evolutionary graph theory with applications to game theory

Evolutionary graph theory (EGT), studies the ability of a mutant gene to overtake a finite structured population. In this review, we describe the original framework for EGT and the major work that has followed it. This review looks at the calculation of the “fixation probability” - the probability of a mutant taking over a population and focuses on game-theoretic applications. We look at varying topics such as alternate evolutionary dynamics, time to fixation, special topological cases, and game theoretic results. Throughout the review, we examine several interesting open problems that warrant further research.     

Evolutionary stable strategies and game dynamics for n-person games

This note contains a generalization of the definition of an evolutionary stable strategy and of the corresponding game dynamics from 2-person to n-person games. This broader framework also allows modelling of several interacting populations or of populations containing different types of individuals, for example males and females.     

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.     

Evolutionary game dynamics in a finite asymmetric two-deme population and emergence of cooperation

We consider evolutionary game dynamics in a finite population subdivided into two demes with both unequal deme sizes and different migration rates. Assuming viability differences in the population according to a linear game within each deme as a result of pairwise interactions, we specify conditions for weak selection favoring a mutant strategy to go to fixation, under the structured-coalescent assumptions, and their connections with evolutionary stability concepts. In the framework of the Iterated Prisoner's Dilemma with strategy ‘tit-for-tat’ as mutant strategy and ‘always defect’ as resident strategy, we deduce a condition under which the emergence of cooperation is favored by selection, when the game matrix is the same in both demes. We show how this condition extends the one-third law for a panmictic population and when an asymmetry in the spatial structure of a two-deme population facilitates the emergence of the cooperative tit-for-tat strategy in comparison with both its symmetric and panmictic population structure counterparts. We find that the condition is less stringent in the asymmetric scenario versus the symmetric scenario if both the fraction of the population in the deme where the mutant was initially introduced, and the expected proportion of migrant offspring in this deme among all migrant offspring after population regulation, are smaller than, or equal to, , provided they are not too small. On the other hand, the condition is less stringent than the one-third law, which holds in the panmictic case, if the latter proportion remains not too close to 1.     

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.     

Evolutionary stability on graphs

Evolutionary stability is a fundamental concept in evolutionary game theory. A strategy is called an evolutionarily stable strategy (ESS), if its monomorphic population rejects the invasion of any other mutant strategy. Recent studies have revealed that population structure can considerably affect evolutionary dynamics. Here we derive the conditions of evolutionary stability for games on graphs. We obtain analytical conditions for regular graphs of degree k>2. Those theoretical predictions are compared with computer simulations for random regular graphs and for lattices. We study three different update rules: birth-death (BD), death-birth (DB), and imitation (IM) updating. Evolutionary stability on sparse graphs does not imply evolutionary stability in a well-mixed population, nor vice versa. We provide a geometrical interpretation of the ESS condition on graphs.     

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.     

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.     

Fixation probabilities for the Moran process in evolutionary games with two strategies: graph shapes and large population asymptotics

This paper is based on the complete classification of evolutionary scenarios for the Moran process with two strategies given by Taylor et al. (Bull Math Biol 66(6):1621–1644, 2004. https://doi.org/10.1016/j.bulm.2004.03.004). Their classification is based on whether each strategy is a Nash equilibrium and whether the fixation probability for a single individual of each strategy is larger or smaller than its value for neutral evolution. We improve on this analysis by showing that each evolutionary scenario is characterized by a definite graph shape for the fixation probability function. A second class of results deals with the behavior of the fixation probability when the population size tends to infinity. We develop asymptotic formulae that approximate the fixation probability in this limit and conclude that some of the evolutionary scenarios cannot exist when the population size is large.

     

The one-third law of evolutionary dynamics

Evolutionary game dynamics in finite populations provide a new framework for studying selection of traits with frequency-dependent fitness. Recently, a "one-third law" of evolutionary dynamics has been described, which states that strategy A fixates in a B-population with selective advantage if the fitness of A is greater than that of B when A has a frequency 13. This relationship holds for all evolutionary processes examined so far, from the Moran process to games on graphs. However, the origin of the "number"13 is not understood. In this paper we provide an intuitive explanation by studying the underlying stochastic processes. We find that in one invasion attempt, an individual interacts on average with B-players twice as often as with A-players, which yields the one-third law. We also show that the one-third law implies that the average Malthusian fitness of A is positive.     

Cross entropy minimization in uninvadable states of complex populations

Selection is often. viewed as a process that maximizes the average fitness of a population. However, there are often constraints even on the phenotypic level which may prevent fitness optimization. Consequently, in evolutionary game theory, models of frequency dependent selection are investigated, which focus on equilibrium states that are characterized by stability (or uninvadability) rather than by optimality. The aim of this article is to show that nevertheless there is a biologically meaningful quantity, namely cross (fitness) entropy, which is optimized during the course of evolution: a dynamical model adapted to evolutionary games is presented which has the property that relative entropy decreases monotonically, if the state of a (complex) population is close to an uninvadable state. This result may be interpreted as if evolution has an order stabilizing effect.     

Finite populations choose an optimal language

This paper studies the evolution of a proto-language in a finite population under the frequency-dependent Moran process. A proto-language can be seen as a collection of concept-to-sign mappings. An efficient proto-language is a bijective mapping from objects of communication to used signs and vice versa. Based on the comparison of fixation probabilities, a method for deriving conditions of evolutionary stability in a finite population [Nowak et al., 2004. Emergence of cooperation and evolutionary stability in finite populations. Nature 428, 246-650], it is shown that efficient proto-languages are the only strategies that are protected by selection, which means that no mutant strategy can have a fixation probability that is greater than the inverse population size. In passing, the paper provides interesting results about the comparison of fixation probabilities as well as Maynard Smith's notion of evolutionary stability for finite populations [Maynard Smith, 1988. Can a mixed strategy be stable in a finite population? J. Theor. Biol. 130, 247-251] that are generally true for games with a symmetric payoff function.     

A game theoretical approach to the evolution of structured communication codes

Structured meaning-signal mappings, i.e., mappings that preserve neighborhood relationships by associating similar signals with similar meanings, are advantageous in an environment where signals are corrupted by noise and sub-optimal meaning inferences are rewarded as well. The evolution of these mappings, however, cannot be explained within a traditional language evolutionary game scenario in which individuals meet randomly because the evolutionary dynamics is trapped in local maxima that do not reflect the structure of the meaning and signal spaces. Here we use a simple game theoretical model to show analytically that when individuals adopting the same communication code meet more frequently than individuals using different codes—a result of the spatial organization of the population—then advantageous linguistic innovations can spread and take over the population. In addition, we report results of simulations in which an individual can communicate only with its K nearest neighbors and show that the probability that the lineage of a mutant that uses a more efficient communication code becomes fixed decreases exponentially with increasing K. These findings support the mother tongue hypothesis that human language evolved as a communication system used among kin, especially between mothers and offspring.     

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.     

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.     

A stochastic model of evolutionary dynamics with deterministic large-population asymptotics

An evolutionary birth-death process is proposed as a model of evolutionary dynamics. Agents residing in a continuous spatial environment X, play a game G, with a continuous strategy set S, against other agents in the environment. The agents’ positions and strategies continuously change in response to other agents and to random effects. Agents spawn asexually at rates that depend on their current fitness, and agents die at rates that depend on their local population density. Agents’ individual evolutionary trajectories in X and S are governed by a system of stochastic ODEs. When the number of agents is large and distributed in a smooth density on (X,S), the collective dynamics of the entire population is governed by a certain (deterministic) PDE, which we call a fitness-diffusion equation.     

One-third rules with equality: Second-order evolutionary stability conditions in finite populations

The one-third law of evolutionary dynamics [Nowak et al. 2004. Emergence of cooperation and evolutionary stability in finite populations. Nature 428, 246-650] describes a robustness criterion for evolution in a finite population: If at an A-frequency of 1/3, the fitness of an A player is greater (smaller) than the fitness of a B player, then a single A mutant that appears in a population of otherwise all B has a fixation probability greater (smaller) than the neutral threshold 1/N, the inverse population size. We examine the case where at an A-frequency of 1/3, the fitness of an A player is exactly equal to the fitness of a B player. We find that in this case the relative magnitude of the cross payoffs matters: If the payoff of A against B is larger (smaller) than the payoff of B against A, then a single A mutant has a fixation probability larger (smaller) than 1/N. If the cross payoffs coincide, we are in the special case of a partnership game, where the deviation cost from an inefficient equilibrium is exactly balanced by the potential gain of switching to the payoff dominant equilibrium. We show that in this case the fixation probability of A is lower than 1/N. Finally, we illustrate our findings by a language game with differentiated costs of signals.     

Evolutionary game dynamics in finite populations

We introduce a model of stochastic evolutionary game dynamics in finite populations which is similar to the familiar replicator dynamics for infinite populations. Our focus is on the conditions for selection favoring the invasion and/or fixation of new phenotypes. For infinite populations, there are three generic selection scenarios describing evolutionary game dynamics among two strategies. For finite populations, there are eight selection scenarios. For a fixed payoff matrix a number of these scenarios can occur for different population sizes. We discuss several examples with unexpected behavior.