Score-dependent fertility model for the evolution of cooperation in a lattice

The evolution of cooperation in the unidirectional division of labour on a tree network

Division of labour on complex networks is rarely investigated using evolutionary game theory. We investigate a division of labour where divided roles are assigned to groups on the nodes of a general unidirectional finite tree graph network. From the network's original node, a task flows and is divided along the branches. A player is randomly selected in each group of cooperators and defectors, who receives a benefit from a cooperator in the upstream group and a part of the task. A cooperator completes their part by paying a cost and then passing it downstream until the entire task is completed. Defectors do not do anything and the division of labour stops, causing all groups to suffer losses due to the incomplete task. We develop a novel method to analyse the local stability in this general tree. We discover that not the benefits but the costs of the cooperation influence the evolution of cooperation, and defections in groups that are directly related to that group's task cause damage to players in that group. We introduce two sanction systems, one of which induces the evolution of cooperation more than the system without sanctions, and promote the coexistence of cooperator and defector groups.

Categorizing update mechanisms for graph-structured metapopulations

The structure of a population strongly influences its evolutionary dynamics. In various settings ranging from biology to social systems, individuals tend to interact more often with those present in their proximity and rarely with those far away. A common approach to model the structure of a population is evolutionary graph theory. In this framework, each graph node is occupied by a reproducing individual. The links connect these individuals to their neighbours. The offspring can be placed on neighbouring nodes, replacing the neighbours-or the progeny of its neighbours can replace a node during the course of ongoing evolutionary dynamics. Extending this theory by replacing single individuals with subpopulations at nodes yields a graph-structured metapopulation. The dynamics between the different local subpopulations is set by an update mechanism. There are many such update mechanisms. Here, we classify update mechanisms for structured metapopulations, which allows to find commonalities between past work and illustrate directions for further research and current gaps of investigation.

The evolution of cooperation in the unidirectional linear division of labour of finite roles

Evolution of cooperation is a puzzle in evolutionary biology and social sciences. Previous studies assumed that players are equal and have symmetric relationships. In our society, players are in different roles, have an asymmetric relationship and cooperate together. We focused on the linear division of labour in a unidirectional chain that has finite roles, each of which is assigned to one group with cooperators and defectors. A cooperator in an upstream group produces and modifies a product, paying a cost of cooperation, and hands it to a player in a downstream group who obtains the benefit from the product. If players in all roles cooperate, a final product can be completed. However, if a player in a group chooses defection, the division of labour stops, the final product cannot be completed and all players in all roles suffer damage. By using the replicator equations of the asymmetric game, we investigate which sanction system promotes the evolution of cooperation in the division of labour. We find that not the benefit of the product but the cost of cooperation matters to the evolutionary dynamics and that the probability of finding a defector determines which sanction system promotes the evolution of cooperation.

A game-theoretical dynamic imitation model on networks

A game-theoretical model is constructed to capture the effect of imitation on the evolution of cooperation. This imitation describes the case where successful individuals are more likely to be imitated by newcomers who will employ their strategies and social networks. Two classical repeated strategies 'always defect (ALLD)' and 'tit-for-tat (TFT)' are adopted. Mathematical analyses are mainly conducted by the method of coalescence theory. Under the assumption of a large population size and weak selection, the results show that the evolution of cooperation is promoted in this dynamic network. As we observed that the critical benefit-to-cost ratio is smaller compared to that in well-mixed populations. The critical benefit-to-cost ratio approaches a specific value which depends on three parameters, the repeated rounds of the game, the effective strategy mutation rate, and the effective link mutation rate. Specifically, for a very high value of the effective link mutation rate, the critical benefit-to-cost ratio approaches 1. Remarkably, for a low value of the effective link mutation rate, by letting the effective strategy mutation is nearly equal to zero, the critical benefit-to-cost ratio approaches [Formula: see text] for the resulting highly connected networks, which allows TFT to be evolutionary stable. It illustrates that dominance of TFTs is associated with more connected networks. This research can enrich the theory of the coevolution of game strategy and network structure with dynamic imitation.

Computational complexity of ecological and evolutionary spatial dynamics

There are deep, yet largely unexplored, connections between computer science and biology. Both disciplines examine how information proliferates in time and space. Central results in computer science describe the complexity of algorithms that solve certain classes of problems. An algorithm is deemed efficient if it can solve a problem in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes of harder problems for which the fastest possible algorithm requires exponential time. Another criterion is the space requirement of the algorithm. There is a crucial distinction between algorithms that can find a solution, verify a solution, or list several distinct solutions in given time and space. The complexity hierarchy that is generated in this way is the foundation of theoretical computer science. Precise complexity results can be notoriously difficult. The famous question whether polynomial time equals nondeterministic polynomial time (i.e., P = NP) is one of the hardest open problems in computer science and all of mathematics. Here, we consider simple processes of ecological and evolutionary spatial dynamics. The basic question is: What is the probability that a new invader (or a new mutant) will take over a resident population? We derive precise complexity results for a variety of scenarios. We therefore show that some fundamental questions in this area cannot be answered by simple equations (assuming that P is not equal to NP).

Cellular cooperation with shift updating and repulsion

Population structure can facilitate evolution of cooperation. In a structured population, cooperators can form clusters which resist exploitation by defectors. Recently, it was observed that a shift update rule is an extremely strong amplifier of cooperation in a one dimensional spatial model. For the shift update rule, an individual is chosen for reproduction proportional to fecundity; the offspring is placed next to the parent; a random individual dies. Subsequently, the population is rearranged (shifted) until all individual cells are again evenly spaced out. For large population size and a one dimensional population structure, the shift update rule favors cooperation for any benefit-to-cost ratio greater than one. But every attempt to generalize shift updating to higher dimensions while maintaining its strong effect has failed. The reason is that in two dimensions the clusters are fragmented by the movements caused by rearranging the cells. Here we introduce the natural phenomenon of a repulsive force between cells of different types. After a birth and death event, the cells are being rearranged minimizing the overall energy expenditure. If the repulsive force is sufficiently high, shift becomes a strong promoter of cooperation in two dimensions.

Evolutionary graph theory revisited: when is an evolutionary process equivalent to the Moran process?

Evolution in finite populations is often modelled using the classical Moran process. Over the last 10 years, this methodology has been extended to structured populations using evolutionary graph theory. An important question in any such population is whether a rare mutant has a higher or lower chance of fixating (the fixation probability) than the Moran probability, i.e. that from the original Moran model, which represents an unstructured population. As evolutionary graph theory has developed, different ways of considering the interactions between individuals through a graph and an associated matrix of weights have been considered, as have a number of important dynamics. In this paper, we revisit the original paper on evolutionary graph theory in light of these extensions to consider these developments in an integrated way. In particular, we find general criteria for when an evolutionary graph with general weights satisfies the Moran probability for the set of six common evolutionary dynamics.

A structured population model suggests that long life and post-reproductive lifespan promote the evolution of cooperation

Social organization correlates with longevity across animal taxa. This correlation has been explained by selection for longevity by social evolution. The reverse causality is also conceivable but has not been sufficiently considered. We constructed a simple, spatially structured population model of asexually reproducing individuals to study the effect of temporal life history structuring on the evolution of cooperation. Individuals employed fixed strategies of cooperation or defection towards all neighbours in a basic Prisoner's Dilemma paradigm. Individuals aged and transitioned through different life history stages asynchronously without migration. An individual's death triggered a reproductive event by one immediate neighbour. The specific neighbour was chosen probabilistically according to the cumulative payoff from all local interactions. Varying the duration of pre-reproductive, reproductive, and post-reproductive life history stages, long-term simulations allowed a systematic evaluation of the influence of the duration of these specific life history stages. Our results revealed complex interactions among the effects of the three basic life history stages and the benefit to defect. Overall, a long post-reproductive stage promoted the evolution of cooperation, while a prolonged pre-reproductive stage has a negative effect. In general, the total length of life also increased the probability of the evolution of cooperation. Thus, our specific model suggests that the timing of life history transitions and total duration of life history stages may affect the evolution of cooperative behaviour. We conclude that the causation of the empirically observed association of life expectancy and sociality may be more complex than previously realized.

Strict or graduated punishment? Effect of punishment strictness on the evolution of cooperation in continuous public goods games

Whether costly punishment encourages cooperation is one of the principal questions in studies on the evolution of cooperation and social sciences. In society, punishment helps deter people from flouting rules in institutions. Specifically, graduated punishment is a design principle for long-enduring common-pool resource institutions. In this study, we investigate whether graduated punishment can promote a higher cooperation level when each individual plays the public goods game and has the opportunity to punish others whose cooperation levels fall below the punisher's threshold. We then examine how spatial structure affects evolutionary dynamics when each individual dies inversely proportional to the game score resulting from the social interaction and another player is randomly chosen from the population to produce offspring to fill the empty site created after a player's death. Our evolutionary simulation outcomes demonstrate that stricter punishment promotes increased cooperation more than graduated punishment in a spatially structured population, whereas graduated punishment increases cooperation more than strict punishment when players interact with randomly chosen opponents from the population. The mathematical analysis also supports the results.

Multi-player games on the cycle

In multi-player games n individuals interact in any one encounter and derive a payoff from that interaction. We assume that individuals adopt one of two strategies, and we consider symmetric games, which means the payoff depends only on the number of players using either strategy, but not on any particular configuration of the encounter. On the cycle we assume that any string of n neighbouring players interacts. We study fixation probabilities of stochastic evolutionary dynamics. We derive analytical results on the cycle both for linear and exponential fitness for any intensity of selection, and compare those to results for the well-mixed population. As particular examples we study multi-player public goods games, stag hunt games and snowdrift games.

Coveting thy neighbors fitness as a means to resolve social dilemmas

In spatial evolutionary games the fitness of each individual is traditionally determined by the payoffs it obtains upon playing the game with its neighbors. Since defection yields the highest individual benefits, the outlook for cooperators is gloomy. While network reciprocity promotes collaborative efforts, chances of averting the impending social decline are slim if the temptation to defect is strong. It is, therefore, of interest to identify viable mechanisms that provide additional support for the evolution of cooperation. Inspired by the fact that the environment may be just as important as inheritance for individual development, we introduce a simple switch that allows a player to either keep its original payoff or use the average payoff of all its neighbors. Depending on which payoff is higher, the influence of either option can be tuned by means of a single parameter. We show that, in general, taking into account the environment promotes cooperation. Yet coveting the fitness of one's neighbors too strongly is not optimal. In fact, cooperation thrives best only if the influence of payoffs obtained in the traditional way is equal to that of the average payoff of the neighborhood. We present results for the prisoner's dilemma and the snowdrift game, for different levels of uncertainty governing the strategy adoption process, and for different neighborhood sizes. Our approach outlines a viable route to increased levels of cooperative behavior in structured populations, but one that requires a thoughtful implementation.

Local replicator dynamics: a simple link between deterministic and stochastic models of evolutionary game theory

Classical replicator dynamics assumes that individuals play their games and adopt new strategies on a global level: Each player interacts with a representative sample of the population and if a strategy yields a payoff above the average, then it is expected to spread. In this article, we connect evolutionary models for infinite and finite populations: While the population itself is infinite, interactions and reproduction occurs in random groups of size N. Surprisingly, the resulting dynamics simplifies to the traditional replicator system with a slightly modified payoff matrix. The qualitative results, however, mirror the findings for finite populations, in which strategies are selected according to a probabilistic Moran process. In particular, we derive a one-third law that holds for any population size. In this way, we show that the deterministic replicator equation in an infinite population can be used to study the Moran process in a finite population and vice versa. We apply the results to three examples to shed light on the evolution of cooperation in the iterated prisoner's dilemma, on risk aversion in coordination games and on the maintenance of dominated strategies.

Inclusive fitness analysis on mathematical groups

Recent work on the evolution of behaviour is set in a structured population, providing a systematic way to describe gene flow and behavioural interactions. To obtain analytical results one needs a structure with considerable regularity. Our results apply to such "homogeneous" structures (e.g., lattices, cycles, and island models). This regularity has been formally described by a "node-transitivity" condition but in mathematics, such internal symmetry is powerfully described by the theory of mathematical groups. Here, this theory provides elegant direct arguments for a more general version of a number of existing results. Our main result is that in large "group-structured" populations, primary fitness effects on others play no role in the evolution of the behaviour. The competitive effects of such a trait cancel the primary effects, and the inclusive fitness effect is given by the direct effect of the actor on its own fitness. This result is conditional on a number of assumptions such as (1) whether generations overlap, (2) whether offspring dispersal is symmetric, (3) whether the trait affects fecundity or survival, and (4) whether the underlying group is abelian. We formulate a number of results of this type in finite and infinite populations for both Moran and Wright-Fisher demographies.

Birth-death symmetry in the evolution of a social trait

Studies of the evolution of a social trait often make ecological assumptions (of population structure, life history), and thus a trait can be studied many different times with different assumptions. Here, I consider a Moran model of continuous reproduction and use an inclusive fitness analysis to investigate the relationships between fecundity or survival selection and birth-death (BD) or death-birth (DB) demography on the evolution of a social trait. A simple symmetry obtains: fecundity (respectively survival) effects under BD behave the same as survival (respectively fecundity) effects under DB. When these results are specialized to a homogeneous population, greatly simplified conditions for a positive inclusive fitness effect are obtained in both a finite and an infinite population. The results are established using the elegant formalism of mathematical group theory and are illustrated with an example of a finite population arranged in a cycle with asymmetric offspring dispersal.

Invasion and expansion of cooperators in lattice populations: prisoner's dilemma vs. snowdrift games

The evolution of cooperation is an enduring conundrum in biology and the social sciences. Two social dilemmas, the prisoner's dilemma and the snowdrift game have emerged as the most promising mathematical metaphors to study cooperation. Spatial structure with limited local interactions has long been identified as a potent promoter of cooperation in the prisoner's dilemma but in the spatial snowdrift game, space may actually enhance or inhibit cooperation. Here we investigate and link the microscopic interaction between individuals to the characteristics of the emerging macroscopic patterns generated by the spatial invasion process of cooperators in a world of defectors. In our simulations, individuals are located on a square lattice with Moore neighborhood and update their strategies by probabilistically imitating the strategies of better performing neighbors. Under sufficiently benign conditions, cooperators can survive in both games. After rapid local equilibration, cooperators expand quadratically until global saturation is reached. Under favorable conditions, cooperators expand as a large contiguous cluster in both games with minor differences concerning the shape of embedded defectors. Under less favorable conditions, however, distinct differences arise. In the prisoner's dilemma, cooperators break up into isolated, compact clusters. The compact clustering reduces exploitation and leads to positive assortment, such that cooperators interact more frequently with other cooperators than with defectors. In contrast, in the snowdrift game, cooperators form small, dendritic clusters, which results in negative assortment and cooperators interact more frequently with defectors than with other cooperators. In order to characterize and quantify the emerging spatial patterns, we introduce a measure for the cluster shape and demonstrate that the macroscopic patterns can be used to determine the characteristics of the underlying microscopic interactions.

Evolution of cooperation in rotating indivisible goods game

Collective behavior is theoretically and experimentally studied through a public goods game in which players contribute resources or efforts to produce goods (or pool), which are then divided equally among all players regardless of the amount of their contribution. However, if goods are indivisible, only one player can receive the goods. In this case, the problem is how to distribute indivisible goods, and here therefore we propose a new game, namely the "rotating indivisible goods game." In this game, the goods are not divided but distributed by regular rotation. An example is rotating savings and credit associations (ROSCAs), which exist all over the world and serve as efficient and informal institutions for collecting savings for small investments. In a ROSCA, members regularly contribute money to produce goods and to distribute them to each member on a regular rotation. It has been pointed out that ROSCA members are selected based on their reliability or reputation, and that defectors who stop contributing are excluded. We elucidate mechanisms that sustain cooperation in rotating indivisible goods games by means of evolutionary simulations. First, we investigate the effect of the peer selection rule by which the group chooses members based on the players reputation, also by which players choose groups based on their reputation. Regardless of the peer selection rule, cooperation is not sustainable in a rotating indivisible goods game. Second, we introduce the forfeiture rule that forbids a member who has not contributed earlier from receiving goods. These analyses show that employing these two rules can sustain cooperation in the rotating indivisible goods game, although employing either of the two cannot. Finally, we prove that evolutionary simulation can be a tool for investigating institutional designs that promote cooperation.

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.

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(abcd). We study a mutation and selection process. For weak selection strategy A is favored over B if and only if sigma a+b>c+sigma d. This means the effect of population structure on strategy selection can be described by a single parameter, sigma. We present the values of sigma 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 sigma, 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 sigma and the critical benefit to cost ratio for the evolution of cooperation. The single parameter, sigma, allows us to quantify the ability of a population structure to promote the evolution of cooperation or to choose efficient equilibria in coordination games.

Effect of the presence of empty sites on the evolution of cooperation by costly punishment in spatial games

Cooperation and spiteful behavior are still evolutionary puzzles. Costly punishment, for which the game payoff is the same as that of spiteful behavior, is one mechanism for promoting the evolution of cooperation. A spatially structured population facilitates the evolution of either cooperation or spite/punishment if cooperation is linked explicitly or implicitly with spite/punishment; a cooperator cooperates with another cooperator and punishes/spites the other type of player. Different updating rules in the evolutionary game produce different evolutionary outcomes: with one updating rule-the score-dependent viability model, in which a player dies with a probability inversely proportional to the game score and the resulting unoccupied site is colonized by one player chosen randomly-the evolution of spite/punishment is promoted more than with the other updating rule-the score-dependent fertility model, in which, after a player dies randomly, the site is colonized by a player with a higher game score. If the population has empty sites, spiteful players or punishers should have less chance to interact with others and then spite/punish others. Thus the presence of empty sites would affect the evolutionary dynamics of spite/punishment. Here, we investigated whether the presence of empty sites discourages the evolution of spite/punishment in both a lattice-structured population and a completely mixing population where players interact with others randomly, especially when the score-dependent viability model is adopted. In the lattice-structured population adopting this viability model, the presence of empty sites promoted the evolution of cooperation and did not reduce the effect of spite/punishment. In the completely mixing population, the presence of empty sites did not promote evolution of cooperation by punishment. The evolutionary dynamics of the score-dependent viability model with empty sites were close to those of the score-dependent fertility model.

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.

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.

Repeated games and direct reciprocity under active linking

Direct reciprocity relies on repeated encounters between the same two individuals. Here we examine the evolution of cooperation under direct reciprocity in dynamically structured populations. Individuals occupy the vertices of a graph, undergoing repeated interactions with their partners via the edges of the graph. Unlike the traditional approach to evolutionary game theory, where individuals meet at random and have no control over the frequency or duration of interactions, we consider a model in which individuals differ in the rate at which they seek new interactions. Moreover, once a link between two individuals has formed, the productivity of this link is evaluated. Links can be broken off at different rates. Whenever the active dynamics of links is sufficiently fast, population structure leads to a simple transformation of the payoff matrix, effectively changing the game under consideration, and hence paving the way for reciprocators to dominate defectors. We derive analytical conditions for evolutionary stability.

Transforming the dilemma

How does natural selection lead to cooperation between competing individuals? The Prisoner's Dilemma captures the essence of this problem. Two players can either cooperate or defect. The payoff for mutual cooperation, R, is greater than the payoff for mutual defection, P. But a defector versus a cooperator receives the highest payoff, T, where as the cooperator obtains the lowest payoff, S. Hence, the Prisoner's Dilemma is defined by the payoff ranking T > R > P > S. In a well-mixed population, defectors always have a higher expected payoff than cooperators, and therefore natural selection favors defectors. The evolution of cooperation requires specific mechanisms. Here we discuss five mechanisms for the evolution of cooperation: direct reciprocity, indirect reciprocity, kin selection, group selection, and network reciprocity (or graph selection). Each mechanism leads to a transformation of the Prisoner's Dilemma payoff matrix. From the transformed matrices, we derive the fundamental conditions for the evolution of cooperation. The transformed matrices can be used in standard frameworks of evolutionary dynamics such as the replicator equation or stochastic processes of game dynamics in finite populations.

Evolution of cooperation in spatial public goods games with common resource dynamics

Investment in a common resource shared by all players is difficult to evolve despite higher returns because a non-investor (free-rider) always receives more than an investor (altruist). This situation is referred to as the Tragedy of the Commons and is often observed in various biological systems including environmental problems of human society. Punishment and reputation are effective mechanisms but require cooperator's ability to identify free-riders. Volunteering can work in anonymous public goods games but this requires voluntary participation, which is not always the case. Here, we show that the evolution of altruism is possible in anonymous and obligate public goods games if we consider the spatiotemporal dynamics of the common resource that incorporate spatial diffusion and internal dynamics of the commons. The investors' strategy to counter free-riders is to increase population density and to outnumber them with the common resource level kept as low as that of the free-riders.

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.

Direct reciprocity on graphs

Direct reciprocity is a mechanism for the evolution of cooperation based on the idea of repeated encounters between the same two individuals. Here we examine direct reciprocity in structured populations, where individuals occupy the vertices of a graph. The edges denote who interacts with whom. The graph represents spatial structure or a social network. For birth-death or pairwise comparison updating, we find that evolutionary stability of direct reciprocity is more restrictive on a graph than in a well-mixed population, but the condition for reciprocators to be advantageous is less restrictive on a graph. For death-birth and imitation updating, in contrast, both conditions are easier to fulfill on a graph. Moreover, for all four update mechanisms, reciprocators can dominate defectors on a graph, which is never possible in a well-mixed population. We also study the effect of an error rate, which increases with the number of links per individual; interacting with more people simultaneously enhances the probability of making mistakes. We provide analytic derivations for all results.

Breaking the symmetry between interaction and replacement in evolutionary dynamics on graphs

We study the evolution of cooperation modeled as symmetric 2x2 games in a population whose structure is split into an interaction graph defining who plays with whom and a replacement graph specifying evolutionary competition. We find it is always harder for cooperators to evolve whenever the two graphs do not coincide. In the thermodynamic limit, the dynamics on both graphs is given by a replicator equation with a rescaled payoff matrix in a rescaled time. Analytical results are obtained in the pair approximation and for weak selection. Their validity is confirmed by computer simulations.

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.

The replicator equation on graphs

We study evolutionary games on graphs. Each player is represented by a vertex of the graph. The edges denote who meets whom. A player can use any one of n strategies. Players obtain a payoff from interaction with all their immediate neighbors. We consider three different update rules, called 'birth-death', 'death-birth' and 'imitation'. A fourth update rule, 'pairwise comparison', is shown to be equivalent to birth-death updating in our model. We use pair approximation to describe the evolutionary game dynamics on regular graphs of degree k. In the limit of weak selection, we can derive a differential equation which describes how the average frequency of each strategy on the graph changes over time. Remarkably, this equation is a replicator equation with a transformed payoff matrix. Therefore, moving a game from a well-mixed population (the complete graph) onto a regular graph simply results in a transformation of the payoff matrix. The new payoff matrix is the sum of the original payoff matrix plus another matrix, which describes the local competition of strategies. We discuss the application of our theory to four particular examples, the Prisoner's Dilemma, the Snow-Drift game, a coordination game and the Rock-Scissors-Paper game.

The role of trade-off shapes in the evolution of parasites in spatial host populations: an approximate analytical approach

Given the substantial changes in mixing in many populations, there is considerable interest in the role that spatial structure can play in the evolution of disease. Here we examine the role of different trade-off shapes in the evolution of parasites in a spatially structured host population where infection can occur locally or globally. We develop an approximate adaptive dynamic analytical approach, to examine how the evolutionarily stable (ES) virulence depends not only on the fraction of global infection/transmission but also on the shape of the trade-off between transmission and virulence. Our analysis can successfully predict the ES virulence found previously by simulation of the full system. The analysis confirms that when there is a linear trade-off between transmission and virulence spatial structure may lead to an ES virulence that increases as the proportion of global transmission increases. However, we also show that the ESS disappears above a threshold level of global infection, leading to maximization. In addition just below this threshold, there is the possibility of evolutionary bi-stabilities. When we assume the realistic trade-off between transmission and virulence that results in an ESS in the classical mixed model, we find that spatial structure can increase or decrease the ES virulence. A relatively high proportion of local infection reduces virulence but intermediate levels can select for higher virulence. Our work not only emphasizes the importance of spatial structure to the evolution of parasites, but also makes it clear that situations between the local and the global need to be considered. We also emphasize the key role that the shape of trade-offs plays in evolutionary outcomes.

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.

A symmetry of fixation times in evoultionary dynamics

In this paper, we show that for evolutionary dynamics between two types that can be described by a Moran process, the conditional fixation time of either type is the same irrespective of the selective scenario. With frequency dependent selection between two strategies A and B of an evolutionary game, regardless of whether A dominates B, A and B are best replies to themselves, or A and B are best replies to each other, the conditional fixation times of a single A and a single B mutant are identical. This does not hold for Wright-Fisher models, nor when the mutants start from multiple copies.

The coevolution of altruism and punishment: Role of the selfish punisher

Punishment is an important mechanism promoting the evolution of altruism among non-relatives. We investigate the coevolution of altruism and punitive behavior, considering four possible strategies: the altruist punisher (AP, a cooperator who punishes defectors), the altruist non-punisher (AN, a pure cooperator), the selfish punisher (SP, a defector who punishes defectors), and the selfish non-punisher (SN, a pure defector). The SP uses a paradoxical strategy as it punishes other defectors. We analyse the effects of SP and AN on the coevolution of altruism and punishment. We study both the score-dependent viability model (whereby the game's score affects survivorship only) and the score-dependent fertility model (whereby the score affects fertility only). In the viability model of a completely mixed population, SP first drives out SN, and hence it helps cooperators (AP and AN) to evolve. In contrast, in the fertility model of a completely mixed population, neither SP nor AN helps the evolution of cooperation. In both the viability and fertility models of a lattice-structured population, SP promotes the spread of AP. In contrast, AN discourages the evolution of AP. These results can be understood that punishment is a form of spite behavior, paying a cost to reduce the fitness of the opponents, and that different models give different magnitude of advantage to spite behavior.

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.

A mathematical analysis on public goods games in the continuous space

We consider the population dynamics of two competing species sharing the same resource, which is modeled by the carrying capacity term of logistic equation. One species (farmer) increases the carrying capacity in exchange for a decreased survival rate, while the other species (exploiter) does not. As the carrying capacity is shared by both species, farmer is altruistic. The effect of continuous spatial structure on the performance of such strategies is studied using the reaction diffusion equations. Mathematical analysis on the traveling wave solution of the system revealed; (1) Farmers can never expel exploiters in any traveling wave solution. (2) The expanding velocity of the exploiter population invading the farmer population can be analytically determined and it depends only on a cost of altruism and the diffusion coefficients while it is independent of the benefit of altruism. (3) When the effect of altruism is small, the dynamics of the invasion of exploiters obeys the Fisher-KPP equation. Numerical calculations confirm these results.

Evolutionary game dynamics with non-uniform interaction rates

The classical setting of evolutionary game theory, the replicator equation, assumes uniform interaction rates. The rate at which individuals meet and interact is independent of their strategies. Here we extend this framework by allowing the interaction rates to depend on the strategies. This extension leads to non-linear fitness functions. We show that a strict Nash equilibrium remains uninvadable for non-uniform interaction rates, but the conditions for evolutionary stability need to be modified. We analyze all games between two strategies. If the two strategies coexist or exclude each other, then the evolutionary dynamics do not change qualitatively, only the location of the equilibrium point changes. If, however, one strategy dominates the other in the classical setting, then the introduction of non-uniform interaction rates can lead to a pair of interior equilibria. For the Prisoner's Dilemma, non-uniform interaction rates allow the coexistence between cooperators and defectors. For the snowdrift game, non-uniform interaction rates change the equilibrium frequency of cooperators.

Stochastic evolutionary dynamics on two levels

We consider a population that is subdivided into groups. Individuals reproduce proportional to their fitness. When a group reaches a certain size it has a probability to split into two groups while another group is eliminated. In this stochastic process, the number of groups is constant, while the total population size fluctuates between well-defined bounds. We calculate the fixation probability of newly introduced mutants under constant selection. We show that the described population structure acts as a suppressor of selection compared to an unstructured population of the same size. The maximum suppression of selection is obtained, when the number of groups equals the number of individuals per group. We also study opposing selection on two or more levels by analysing the evolutionary dynamics of hierarchically embedded Moran processes.

Adaptive Evolution of Social Traits: Origin, Trajectories, and Correlations of Altruism and Mobility

Social behavior involves "staying and helping," two individual attributes that vary considerably among organisms. Investigating the ultimate causes of such variation, this study integrates previously separate lines of research by analyzing the joint evolution of altruism and mobility. We unfold the network of selective pressures and derive how these depend on physiological costs, eco-evolutionary feedbacks, and a complex interaction between the evolving traits. Our analysis highlights habitat saturation, both around individuals (local aggregation) and around unoccupied space (local contention), as the key mediator of altruism and mobility evolution. Once altruism and mobility are allowed to evolve jointly, three general insights emerge. First, the cost of mobility affects the origin of altruism, determining whether and how quickly selfishness is overcome. Second, the cost of altruism determines which of two qualitatively different routes to sociality are taken: an evolutionary reduction of mobility, resulting in higher habitat saturation, is either preceded or followed by the adaptive rise of altruism. Third, contrary to conventional expectations, a positive correlation between evolutionarily stable levels of altruism and mobility can arise; this is expected when comparing populations that evolved under different constraints on mobility or that differ in other life-history traits.

Effects of neighbourhood size and connectivity on the spatial Continuous Prisoner's Dilemma

The Prisoner's Dilemma, a two-person game in which the players can either cooperate or defect, is a common paradigm for studying the evolution of cooperation. In real situations cooperation is almost never all or nothing. This observation is the motivation for the Continuous Prisoner's Dilemma, in which individuals exhibit variable degrees of cooperation. It is known that in the presence of spatial structure, when individuals "play against" (i.e. interact with) their neighbours, and "compare to" ("learn from") them, cooperative investments can evolve to considerable levels. Here, we examine the effect of increasing the neighbourhood size: we find that the mean-field limit of no cooperation is reached for a critical neighbourhood size of about five neighbours on each side in a Moore neighbourhood, which does not depend on the size of the spatial lattice. We also find the related result that in a network of players, the critical average degree (number of neighbours) of nodes for which defection is the final state does not depend on network size, but only on the network topology. This critical average degree is considerably (about 10 times) higher for clustered (social) networks, than for distributed random networks. This result strengthens the argument that clustering is the mechanism which makes the development and maintenance of the cooperation possible. In the lattice topology, it is observed that when the neighbourhood sizes for "interacting" and "learning" differ by more than 0.5, cooperation is not sustainable, even for neighbourhood sizes that are below the mean-field limit of defection. We also study the evolution of neighbourhood sizes, as well as investment level. Here, we observe that the series of the interaction and learning neighbourhoods converge, and a final cooperative state with considerable levels of average investment is achieved.

The adaptive dynamics of altruism in spatially heterogeneous populations

We study the spatial adaptive dynamics of a continuous trait that measures individual investment in altruism. Our study is based on an ecological model of a spatially heterogeneous population from which we derive an appropriate measure of fitness. The analysis of this fitness measure uncovers three different selective processes controlling the evolution of altruism: the direct physiological cost, the indirect genetic benefits of cooperative interactions, and the indirect genetic costs of competition for space. In our model, habitat structure and a continuous life cycle makes the cost of competing for space with relatives negligible. Our study yields a classification of adaptive patterns of altruism according to the shape of the costs of altruism (with decelerating, linear, or accelerating dependence on the investment in altruism). The invasion of altruism occurs readily in species with accelerating costs, but large mutations are critical for altruism to evolve in selfish species with decelerating costs. Strict selfishness is maintained by natural selection only under very restricted conditions. In species with rapidly accelerating costs, adaptation leads to an evolutionarily stable rate of investment in altruism that decreases smoothly with the level of mobility. A rather different adaptive pattern emerges in species with slowly accelerating costs: high altruism evolves at low mobility, whereas a quasi-selfish state is promoted in more mobile species. The high adaptive level of altruism can be predicted solely from habitat connectedness and physiological parameters that characterize the pattern of cost. We also show that environmental changes that cause increased mobility in those highly altruistic species can beget selection-driven self-extinction, which may contribute to the rarity of social species.