Spatial evolutionary prisoner's dilemma game with three strategies and external constraints

Conditional cooperation with longer memory

Direct reciprocity is a wide-spread mechanism for the evolution of cooperation. In repeated interactions, players can condition their behavior on previous outcomes. A well-known approach is given by reactive strategies, which respond to the coplayer's previous move. Here, we extend reactive strategies to longer memories. A reactive-n strategy takes into account the sequence of the last n moves of the coplayer. A reactive-n counting strategy responds to how often the coplayer cooperated during the last n rounds. We derive an algorithm to identify the partner strategies within these strategy sets. Partner strategies are those that ensure mutual cooperation without exploitation. We give explicit conditions for all partner strategies among reactive-2, reactive-3 strategies, and reactive-n counting strategies. To further explore the role of memory, we perform evolutionary simulations. We vary several key parameters, such as the cost-to-benefit ratio of cooperation, the error rate, and the strength of selection. Within the strategy sets we consider, we find that longer memory tends to promote cooperation. This positive effect of memory is particularly pronounced when individuals take into account the precise sequence of moves.

Diffusion and pattern formation in spatial games

Diffusion plays an important role in a wide variety of phenomena, from bacterial quorum sensing to the dynamics of traffic flow. While it generally tends to level out gradients and inhomogeneities, diffusion has nonetheless been shown to promote pattern formation in certain classes of systems. Formation of stable structures often serves as a key factor in promoting the emergence and persistence of cooperative behavior in otherwise competitive environments, however, an in-depth analysis on the impact of diffusion on such systems is lacking. We therefore investigate the effects of diffusion on cooperative behavior using a cellular automaton (CA) model of the noisy spatial iterated prisoner's dilemma (IPD), physical extension, and stochasticity being unavoidable characteristics of several natural phenomena. We further derive a mean-field (MF) model that captures the three-species predation dynamics from the CA model and highlight how pattern formation arises in this new model, then characterize how including diffusion by interchange similarly enables the emergence of large scale structures in the CA model as well. We investigate how these emerging patterns favors cooperative behavior for parameter space regions where IPD error rates classically forbid such dynamics. We thus demonstrate how the coupling of diffusion with nonlinear dynamics can, counterintuitively, promote large-scale structure formation and in return establish new grounds for cooperation to take hold in stochastic spatial systems.

Vacancies in growing habitats promote the evolution of cooperation

We study evolutionary game dynamics in a growing habitat with vacancies. Fitness is determined by the global effect of the environment and a local prisoner's dilemma among neighbors. We study population growth on a one-dimensional lattice and analyze how the environment affects evolutionary competition. As the environment becomes harsh, an absorbing phase transition from growing populations to extinction occurs. The transition point depends on which strategies are present in the population. In particular, we find a 'cooperative window' in parameter space, where only cooperators can survive. A mutant defector in a cooperative community might briefly proliferate, but over time naturally occurring vacancies separate cooperators from defectors, thereby driving defectors to extinction. Our model reveals that vacancies provide a strong boost for cooperation by spatial selection.

Adaptive dynamics of memory-one strategies in the repeated donation game

Human interactions can take the form of social dilemmas: collectively, people fare best if all cooperate but each individual is tempted to free ride. Social dilemmas can be resolved when individuals interact repeatedly. Repetition allows them to adopt reciprocal strategies which incentivize cooperation. The most basic model for direct reciprocity is the repeated donation game, a variant of the prisoner's dilemma. Two players interact over many rounds; in each round they decide whether to cooperate or to defect. Strategies take into account the history of the play. Memory-one strategies depend only on the previous round. Even though they are among the most elementary strategies of direct reciprocity, their evolutionary dynamics has been difficult to study analytically. As a result, much previous work has relied on simulations. Here, we derive and analyze their adaptive dynamics. We show that the four-dimensional space of memory-one strategies has an invariant three-dimensional subspace, generated by the memory-one counting strategies. Counting strategies record how many players cooperated in the previous round, without considering who cooperated. We give a partial characterization of adaptive dynamics for memory-one strategies and a full characterization for memory-one counting strategies.

Mutation enhances cooperation in direct reciprocity

Direct reciprocity is a powerful mechanism for the evolution of cooperation based on repeated interactions between the same individuals. But high levels of cooperation evolve only if the benefit-to-cost ratio exceeds a certain threshold that depends on memory length. For the best-explored case of one-round memory, that threshold is two. Here, we report that intermediate mutation rates lead to high levels of cooperation, even if the benefit-to-cost ratio is only marginally above one, and even if individuals only use a minimum of past information. This surprising observation is caused by two effects. First, mutation generates diversity which undermines the evolutionary stability of defectors. Second, mutation leads to diverse communities of cooperators that are more resilient than homogeneous ones. This finding is relevant because many real-world opportunities for cooperation have small benefit-to-cost ratios, which are between one and two, and we describe how direct reciprocity can attain cooperation in such settings. Our result can be interpreted as showing that diversity, rather than uniformity, promotes evolution of cooperation.

Cooperation in alternating interactions with memory constraints

In repeated social interactions, individuals often employ reciprocal strategies to maintain cooperation. To explore the emergence of reciprocity, many theoretical models assume synchronized decision making. In each round, individuals decide simultaneously whether to cooperate or not. Yet many manifestations of reciprocity in nature are asynchronous. Individuals provide help at one time and receive help at another. Here, we explore such alternating games in which players take turns. We mathematically characterize all Nash equilibria among memory-one strategies. Moreover, we use evolutionary simulations to explore various model extensions, exploring the effect of discounted games, irregular alternation patterns, and higher memory. In all cases, we observe that mutual cooperation still evolves for a wide range of parameter values. However, compared to simultaneous games, alternating games require different strategies to maintain cooperation in noisy environments. Moreover, none of the respective strategies are evolutionarily stable.

In many instances of reciprocity, individuals cooperate in turns. Here, the authors analyze the equilibria and the dynamics of such alternating games, and in particular describe all strategies with one-round memory that maintain cooperation.

Evolution of Cooperation in Social Dilemmas with Assortative Interactions

Cooperation in social dilemmas plays a pivotal role in the formation of systems at all levels of complexity, from replicating molecules to multi-cellular organisms to human and animal societies. In spite of its ubiquity, the origin and stability of cooperation pose an evolutionary conundrum, since cooperation, though beneficial to others, is costly to the individual cooperator. Thus natural selection would be expected to favor selfish behavior in which individuals reap the benefits of cooperation without bearing the costs of cooperating themselves. Many proximate mechanisms have been proposed to account for the origin and maintenance of cooperation, including kin selection, direct reciprocity, indirect reciprocity, and evolution in structured populations. Despite the apparent diversity of these approaches they all share a unified underlying logic: namely, each mechanism results in assortative interactions in which individuals using the same strategy interact with a higher probability than they would at random. Here we study the evolution of cooperation in both discrete strategy and continuous strategy social dilemmas with assortative interactions. For the sake of tractability, assortativity is modeled by an individual interacting with another of the same type with probability r and interacting with a random individual in the population with probability 1−r, where r is a parameter that characterizes the degree of assortativity in the system. For discrete strategy social dilemmas we use both a generalization of replicator dynamics and individual-based simulations to elucidate the donation, snowdrift, and sculling games with assortative interactions, and determine the analogs of Hamilton’s rule, which govern the evolution of cooperation in these games. For continuous strategy social dilemmas we employ both a generalization of deterministic adaptive dynamics and individual-based simulations to study the donation, snowdrift, and tragedy of the commons games, and determine the effect of assortativity on the emergence and stability of cooperation.

Social dilemmas among unequals

Direct reciprocity is a powerful mechanism for the evolution of cooperation on the basis of repeated interactions^1-4. It requires that interacting individuals are sufficiently equal, such that everyone faces similar consequences when they cooperate or defect. Yet inequality is ubiquitous among humans^5,6 and is generally considered to undermine cooperation and welfare^7-10. Most previous models of reciprocity do not include inequality^11-15. These models assume that individuals are the same in all relevant aspects. Here we introduce a general framework to study direct reciprocity among unequal individuals. Our model allows for multiple sources of inequality. Subjects can differ in their endowments, their productivities and in how much they benefit from public goods. We find that extreme inequality prevents cooperation. But if subjects differ in productivity, some endowment inequality can be necessary for cooperation to prevail. Our mathematical predictions are supported by a behavioural experiment in which we vary the endowments and productivities of the subjects. We observe that overall welfare is maximized when the two sources of heterogeneity are aligned, such that more productive individuals receive higher endowments. By contrast, when endowments and productivities are misaligned, cooperation quickly breaks down. Our findings have implications for policy-makers concerned with equity, efficiency and the provisioning of public goods.

Fixation Probabilities for Any Configuration of Two Strategies on Regular Graphs

Population structure and spatial heterogeneity are integral components of evolutionary dynamics, in general, and of evolution of cooperation, in particular. Structure can promote the emergence of cooperation in some populations and suppress it in others. Here, we provide results for weak selection to favor cooperation on regular graphs for any configuration, meaning any arrangement of cooperators and defectors. Our results extend previous work on fixation probabilities of rare mutants. We find that for any configuration cooperation is never favored for birth-death (BD) updating. In contrast, for death-birth (DB) updating, we derive a simple, computationally tractable formula for weak selection to favor cooperation when starting from any configuration containing any number of cooperators. This formula elucidates two important features: (i) the takeover of cooperation can be enhanced by the strategic placement of cooperators and (ii) adding more cooperators to a configuration can sometimes suppress the evolution of cooperation. These findings give a formal account for how selection acts on all transient states that appear in evolutionary trajectories. They also inform the strategic design of initial states in social networks to maximally promote cooperation. We also derive general results that characterize the interaction of any two strategies, not only cooperation and defection.

Anisotropic invasion and its consequences in two-strategy evolutionary games on a square lattice

We have studied invasion processes in two-strategy evolutionary games on a square lattice for imitation rule when the players interact with their nearest neighbors. Monte Carlo simulations are performed for systems where the pair interactions are composed of a unit strength coordination game when varying the strengths of the self-dependent and cross-dependent components at a fixed noise level. The visualization of strategy distributions has clearly indicated that circular homogeneous domains evolve into squares with an orientation dependent on the composition. This phenomenon is related to the anisotropy of invasion velocities along the interfaces separating the two homogeneous regions. The quantified invasion velocities indicate the existence of a parameter region in which the invasions are opposite for the horizontal (or vertical) and the tilted interfaces. In this parameter region faceted islands of both strategies shrink and the system evolves from a random initial state into the homogeneous state that first percolated.

Aspiration promotes cooperation in the prisoner's dilemma game with the imitation rule

A model of stochastic evolutionary game dynamics with finite population of size N+M was built. Among these individuals, N individuals update strategies with aspiration updating, while the other M individuals update strategies with imitation updating. In the proposed model, we obtain the expression of the mean fraction of cooperators and analyze some concrete cases. Compared with the standard imitation dynamics, there is always a positive probability to support the formation of cooperation in the system with the aspiration and imitation rules. Moreover, the numerical results indicate that more aspiration-driven individuals lead to a higher mean fraction of imitation-driven cooperators, which means the invasion of the aspiration-driven individuals is conducive to promoting the cooperation of the imitation-driven individuals.

Games of multicellularity

Evolutionary game dynamics are often studied in the context of different population structures. Here we propose a new population structure that is inspired by simple multicellular life forms. In our model, cells reproduce but can stay together after reproduction. They reach complexes of a certain size, n, before producing single cells again. The cells within a complex derive payoff from an evolutionary game by interacting with each other. The reproductive rate of cells is proportional to their payoff. We consider all two-strategy games. We study deterministic evolutionary dynamics with mutations, and derive exact conditions for selection to favor one strategy over another. Our main result has the same symmetry as the well-known sigma condition, which has been proven for stochastic game dynamics and weak selection. For a maximum complex size of n=2 our result holds for any intensity of selection. For n≥3 it holds for weak selection. As specific examples we study the prisoner's dilemma and hawk-dove games. Our model advances theoretical work on multicellularity by allowing for frequency-dependent interactions within groups.

Evolution of Cooperation in Social Dilemmas on Complex Networks

Cooperation in social dilemmas is essential for the functioning of systems at multiple levels of complexity, from the simplest biological organisms to the most sophisticated human societies. Cooperation, although widespread, is fundamentally challenging to explain evolutionarily, since natural selection typically favors selfish behavior which is not socially optimal. Here we study the evolution of cooperation in three exemplars of key social dilemmas, representing the prisoner's dilemma, hawk-dove and coordination classes of games, in structured populations defined by complex networks. Using individual-based simulations of the games on model and empirical networks, we give a detailed comparative study of the effects of the structural properties of a network, such as its average degree, variance in degree distribution, clustering coefficient, and assortativity coefficient, on the promotion of cooperative behavior in all three classes of games.

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.

Universal scaling for the dilemma strength in evolutionary games

Why would natural selection favor the prevalence of cooperation within the groups of selfish individuals? A fruitful framework to address this question is evolutionary game theory, the essence of which is captured in the so-called social dilemmas. Such dilemmas have sparked the development of a variety of mathematical approaches to assess the conditions under which cooperation evolves. Furthermore, borrowing from statistical physics and network science, the research of the evolutionary game dynamics has been enriched with phenomena such as pattern formation, equilibrium selection, and self-organization. Numerous advances in understanding the evolution of cooperative behavior over the last few decades have recently been distilled into five reciprocity mechanisms: direct reciprocity, indirect reciprocity, kin selection, group selection, and network reciprocity. However, when social viscosity is introduced into a population via any of the reciprocity mechanisms, the existing scaling parameters for the dilemma strength do not yield a unique answer as to how the evolutionary dynamics should unfold. Motivated by this problem, we review the developments that led to the present state of affairs, highlight the accompanying pitfalls, and propose new universal scaling parameters for the dilemma strength. We prove universality by showing that the conditions for an ESS and the expressions for the internal equilibriums in an infinite, well-mixed population subjected to any of the five reciprocity mechanisms depend only on the new scaling parameters. A similar result is shown to hold for the fixation probability of the different strategies in a finite, well-mixed population. Furthermore, by means of numerical simulations, the same scaling parameters are shown to be effective even if the evolution of cooperation is considered on the spatial networks (with the exception of highly heterogeneous setups). We close the discussion by suggesting promising directions for future research including (i) how to handle the dilemma strength in the context of co-evolution and (ii) where to seek opportunities for applying the game theoretical approach with meaningful impact.

Evolutionary prisoner's dilemma game on graphs and social networks with external constraint

A game-theoretical model is constructed to capture the effect of external constraint on the evolution of cooperation. External constraint describes the case where individuals are forced to cooperate with a given probability in a society. Mathematical analyses are conducted via pair approximation and diffusion approximation methods. The results show that the condition for cooperation to be favored on graphs with constraint is b¯/c¯>k/A¯ (A¯=1+kp/(1-p)), where b¯ and c¯ represent the altruistic benefit and cost, respectively, k is the average degree of the graph and p is the probability of compulsory cooperation by external enforcement. Moreover, numerical simulations are also performed on a repeated game with three strategies, always defect (ALLD), tit-for-tat (TFT) and always cooperate (ALLC). These simulations demonstrate that a slight enforcement of ALLC can only promote cooperation when there is weak network reciprocity, while the catalyst effect of TFT on cooperation is verified. In addition, the interesting phenomenon of stable coexistence of the three strategies can be observed. Our model can represent evolutionary dynamics on a network structure which is disturbed by a specified external constraint.

Bluffing promotes overconfidence on social networks

The overconfidence, a well-established bias, in fact leads to unrealistic expectations or faulty assessment. So it remains puzzling why such psychology of self-deception is stabilized in human society. To investigate this problem, we draw lessons from evolutionary game theory which provides a theoretical framework to address the subtleties of cooperation among selfish individuals. Here we propose a spatial resource competition model showing that, counter-intuitively, moderate values rather than large values of resource-to-cost ratio boost overconfidence level most effectively. In contrast to theoretical results in infinite well-mixed populations, network plays a role both as a “catalyst” and a “depressant” in the spreading of overconfidence, especially when resource-to-cost ratio is in a certain range. Moreover, when bluffing is taken into consideration, overconfidence evolves to a higher level to counteract its detrimental effect, which may well explain the prosperity of this “erroneous” psychology.

Quasiperiodic, periodic, and slowing-down states of coupled heteroclinic cycles

We investigate two coupled oscillators, each of which shows an attracting heteroclinic cycle in the absence of coupling. The two heteroclinic cycles are nonidentical. Weak coupling can lead to the elimination of the slowing-down state that asymptotically approaches the heteroclinic cycle for a single cycle, giving rise to either quasiperiodic motion with separate frequencies from the two cycles or periodic motion in which the two cycles are synchronized. The synchronization transition, which occurs via a Hopf bifurcation, is not induced by the commensurability of the two cycle frequencies but rather by the disappearance of the weaker frequency oscillation. For even larger coupling the motion changes via a resonant heteroclinic bifurcation to a slowing-down state corresponding to a single attracting heteroclinic orbit. Coexistence of multiple attractors can be found for some parameter regions. These results are of interest in ecological, sociological, neuronal, and other dynamical systems, which have the structure of coupled heteroclinic cycles.

Phase diagrams for the spatial public goods game with pool punishment

The efficiency of institutionalized punishment is studied by evaluating the stationary states in the spatial public goods game comprising unconditional defectors, cooperators, and cooperating pool punishers as the three competing strategies. Fines and costs of pool punishment are considered as the two main parameters determining the stationary distributions of strategies on the square lattice. Each player collects a payoff from five five-person public goods games, and the evolution of strategies is subsequently governed by imitation based on pairwise comparisons at a low level of noise. The impact of pool punishment on the evolution of cooperation in structured populations is significantly different from that reported previously for peer punishment. Representative phase diagrams reveal remarkably rich behavior, depending also on the value of the synergy factor that characterizes the efficiency of investments payed into the common pool. Besides traditional single- and two-strategy stationary states, a rock-paper-scissors type of cyclic dominance can emerge in strikingly different ways.

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.

Phase diagrams for three-strategy evolutionary prisoner's dilemma games on regular graphs

Evolutionary prisoner's dilemma games are studied with players located on square lattice and random regular graph defining four neighbors for each one. The players follow one of the three strategies: tit-for-tat, unconditional cooperation, and defection. The simplified payoff matrix is characterized by two parameters: the temptation b to choose defection and the cost c of inspection reducing the income of tit-for-tat. The strategy imitation from one of the neighbors is controlled by pairwise comparison at a fixed level of noise. Using Monte Carlo simulations and the extended versions of pair approximation we have evaluated the b-c phase diagrams indicating a rich plethora of phase transitions between stationary coexistence, absorbing, and oscillatory states, including continuous and discontinuous phase transitions. By reasonable costs the tit-for-tat strategy prevents extinction of cooperators across the whole span of b determining the prisoner's dilemma game, irrespective of the connectivity structure. We also demonstrate that the system can exhibit a repetitive succession of oscillatory and stationary states upon changing a single payoff value, which highlights the remarkable sensitivity of cyclical interactions on the parameters that define the strength of dominance.

Coevolutionary games--a mini review

Prevalence of cooperation within groups of selfish individuals is puzzling in that it contradicts with the basic premise of natural selection. Favoring players with higher fitness, the latter is key for understanding the challenges faced by cooperators when competing with defectors. Evolutionary game theory provides a competent theoretical framework for addressing the subtleties of cooperation in such situations, which are known as social dilemmas. Recent advances point towards the fact that the evolution of strategies alone may be insufficient to fully exploit the benefits offered by cooperative behavior. Indeed, while spatial structure and heterogeneity, for example, have been recognized as potent promoters of cooperation, coevolutionary rules can extend the potentials of such entities further, and even more importantly, lead to the understanding of their emergence. The introduction of coevolutionary rules to evolutionary games implies, that besides the evolution of strategies, another property may simultaneously be subject to evolution as well. Coevolutionary rules may affect the interaction network, the reproduction capability of players, their reputation, mobility or age. Here we review recent works on evolutionary games incorporating coevolutionary rules, as well as give a didactic description of potential pitfalls and misconceptions associated with the subject. In addition, we briefly outline directions for future research that we feel are promising, thereby particularly focusing on dynamical effects of coevolutionary rules on the evolution of cooperation, which are still widely open to research and thus hold promise of exciting new discoveries.

Effect of spatial structure on the evolution of cooperation

Spatial structure is known to have an impact on the evolution of cooperation, and so it has been intensively studied during recent years. Previous work has shown the relevance of some features, such as the synchronicity of the updating, the clustering of the network, or the influence of the update rule. This has been done, however, for concrete settings with particular games, networks, and update rules, with the consequence that some contradictions have arisen and a general understanding of these topics is missing in the broader context of the space of 2x2 games. To address this issue, we have performed a systematic and exhaustive simulation in the different degrees of freedom of the problem. In some cases, we generalize previous knowledge to the broader context of our study and explain the apparent contradictions. In other cases, however, our conclusions refute what seems to be established opinions in the field, as for example the robustness of the effect of spatial structure against changes in the update rule, or offer new insights into the subject, e.g., the relation between the intensity of selection and the asymmetry between the effects on games with mixed equilibria.

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.

Evolutionary games on minimally structured populations

Population structure induced by both spatial embedding and more general networks of interaction, such as model social networks, have been shown to have a fundamental effect on the dynamics and outcome of evolutionary games. These effects have, however, proved to be sensitive to the details of the underlying topology and dynamics. Here we introduce a minimal population structure that is described by two distinct hierarchical levels of interaction, similar to the structured metapopulation concept of ecology and island models in population genetics. We believe this model is able to identify effects of spatial structure that do not depend on the details of the topology. While effects depending on such details clearly lie outside the scope of our approach, we expect that those we are able to reproduce should be generally applicable to a wide range of models. We derive the dynamics governing the evolution of a system starting from fundamental individual level stochastic processes through two successive mean-field approximations. In our model of population structure the topology of interactions is described by only two parameters: the effective population size at the local scale and the relative strength of local dynamics to global mixing. We demonstrate, for example, the existence of a continuous transition leading to the dominance of cooperation in populations with hierarchical levels of unstructured mixing as the benefit to cost ratio becomes smaller then the local population size. Applying our model of spatial structure to the repeated prisoner's dilemma we uncover a counterintuitive mechanism by which the constant influx of defectors sustains cooperation. Further exploring the phase space of the repeated prisoner's dilemma and also of the "rock-paper-scissor" game we find indications of rich structure and are able to reproduce several effects observed in other models with explicit spatial embedding, such as the maintenance of biodiversity and the emergence of global oscillations.

Emergence of synchronization induced by the interplay between two prisoner's dilemma games with volunteering in small-world networks

We studied synchronization between prisoner's dilemma games with voluntary participation in two Newman-Watts small-world networks. It was found that there are three kinds of synchronization: partial phase synchronization, total phase synchronization, and complete synchronization, for varied coupling factors. Besides, two games can reach complete synchronization for the large enough coupling factor. We also discussed the effect of the coupling factor on the amplitude of oscillation of cooperator density.

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.

Randomness enhances cooperation: a resonance-type phenomenon in evolutionary games

We investigate the effect of randomness in both relationships and decisions on the evolution of cooperation. Simulation results show, in such randomness' presence, the system evolves more frequently to a cooperative state than in its absence. Specifically, there is an optimal amount of randomness, which can induce the highest level of cooperation. The mechanism of randomness promoting cooperation resembles a resonancelike fashion, which could be of particular interest in evolutionary game dynamics in economic, biological, and social systems.

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.

Does mobility decrease cooperation?

We explore the minimal conditions for sustainable cooperation on a spatially distributed population of memoryless, unconditional strategies (cooperators and defectors) in presence of unbiased, non-contingent mobility in the context of the Prisoner's Dilemma game. We find that cooperative behavior is not only possible but may even be enhanced by such an "always-move" rule, when compared with the strongly viscous ("never-move") case. In addition, mobility also increases the capability of cooperation to emerge and invade a population of defectors, what may have a fundamental role in the problem of the onset of cooperation.

Transition from Gaussian to Levy distributions of stochastic payoff variations in the spatial prisoner's dilemma game

We study the impact of stochastic payoff variations with different distributions on the evolution of cooperation in the spatial prisoner's dilemma game. We find that Gaussian-distributed payoff variations are most successful in promoting cooperation irrespective of the temptation to defect. In particular, the facilitative effect of noise on the evolution of cooperation decreases steadily as the frequency of rare events increases. Findings are explained via an analysis of local payoff ranking violations. The relevance of results for economics and sociology is discussed.

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.

Phase diagrams for an evolutionary prisoner's dilemma game on two-dimensional lattices

The effects of payoffs and noise on the maintenance of cooperative behavior are studied in an evolutionary prisoner's dilemma game with players located on the sites of different two-dimensional lattices. This system exhibits a phase transition from a mixed state of cooperators and defectors to a homogeneous one where only the defectors remain alive. Using Monte Carlo simulations and the generalized mean-field approximations we have determined the phase boundaries (critical points) separating the two phases on the plane of the temperature (noise) and temptation to choose defection. In the zero temperature limit the cooperation can be sustained only for those connectivity structures where three-site clique percolation occurs.

Extended estimator approach for 2 x 2 games and its mapping to the Ising Hamiltonian

We consider a system of adaptive self-interested agents interacting by playing an iterated pairwise prisoner's dilemma (PD) game. Each player has two options: either cooperate (C) or defect (D). Agents have no (long term) memory to reciprocate nor identifying tags to distinguish C from D. We show how their 16 possible elementary Markovian (one-step memory) strategies can be cast in a simple general formalism in terms of an estimator of expected utilities Delta*. This formalism is helpful to map a subset of these strategies into an Ising Hamiltonian in a straightforward way. This connection in turn serves to shed light on the evolution of the iterated games played by agents, which can represent a broad variety of individuals from firms of a market to species coexisting in an ecosystem. Additionally, this magnetic description may be useful to introduce noise in a natural and simple way. The equilibrium states reached by the system depend strongly on whether the dynamics are synchronous or asynchronous and also on the system connectivity.

Cooperation for volunteering and partially random partnerships

Competition among cooperative, defective, and loner strategies is studied by considering an evolutionary prisoner's dilemma game for different partnerships. In this game each player can adopt one of its coplayer's strategy with a probability depending on the difference of payoffs coming from games with the corresponding coplayers. Our attention is focused on the effects of annealed and quenched randomness in the partnership for fixed number of coplayers. It is shown that only the loners survive if the four coplayers are chosen randomly (mean-field limit). On the contrary, on the square lattice all the three strategies are maintained by the cyclic invasions resulting in a self-organizing spatial pattern. If the fixed partnership is described by a regular small-world structure then a homogeneous oscillation occurs in the population dynamics when the measure of quenched randomness exceeds a threshold value. Similar behavior with higher sensitivity to the randomness is found if temporary partners are substituted for the standard ones with some probability at each step of iteration.

Self-organization in a simple model of adaptive agents playing 2 x 2 games with arbitrary payoff matrices

We analyze, both analytically and numerically, the self-organization of a system of "selfish" adaptive agents playing an arbitrary iterated pairwise game (defined by a 2 x 2 payoff matrix). Examples of possible games to play are the prisoner's dilemma (PD) game, the chicken game, the hero game, etc. The agents have no memory, use strategies not based on direct reciprocity nor "tags" and are chosen at random, i.e., geographical vicinity is neglected. They can play two possible strategies: cooperate (C) or defect (D). The players measure their success by comparing their utilities with an estimate for the expected benefits and update their strategy following a simple rule. Two versions of the model are studied: (1) the deterministic version (the agents are either in definite states C or D) and (2) the stochastic version (the agents have a probability c of playing C). Using a general master equation we compute the equilibrium states into which the system self-organizes, characterized by their average probability of cooperation c(eq). Depending on the payoff matrix, we show that c(eq) can take five different values. We also consider the mixing of agents using two different payoff matrices and show that any value of c(eq) can be reached by tuning the proportions of agents using each payoff matrix. In particular, this can be used as a way to simulate the effect of a fraction d of "antisocial" individuals--incapable of realizing any value to cooperation--on the cooperative regime hold by a population of neutral or "normal" agents.

Evolutionary prisoner's dilemma games with voluntary participation

Voluntary participation in public good games has recently been demonstrated to be a simple yet effective mechanism to avoid deadlocks in states of mutual defection and to promote persistent cooperative behavior. Apart from cooperators and defectors a third strategical type is considered: the risk averse loners who are unwilling to participate in the social enterprise and rather rely on small but fixed earnings. This results in a rock-scissors-paper type of cyclic dominance of the three strategies. In the prisoner's dilemma, the effects of voluntary participation crucially depend on the underlying population structure. While leading to homogeneous states of all loners in well-mixed populations, we demonstrate that cyclic dominance produces self-organizing patterns on square lattices but leads to different types of oscillatory behavior on random regular graphs: the temptation to defect determines whether damped, periodic, or increasing oscillations occur. These Monte Carlo simulations are complemented by predictions from pair approximation reproducing the results for random regular graphs particularly well.

Coevolutionary games on networks

We study agents on a network playing an iterated Prisoner's dilemma against their neighbors. The resulting spatially extended coevolutionary game exhibits stationary states which are Nash equilibria. After perturbation of these equilibria, avalanches of mutations reestablish a stationary state. Scale-free avalanche distributions are observed that are in accordance with calculations from the Nash equilibria and a confined branching process. The transition from subcritical to critical avalanche dynamics can be traced to a change in the degeneracy of the cooperative macrostate and is observed for many variants of this game.

Phase transitions and volunteering in spatial public goods games

We present a simple yet effective mechanism promoting cooperation under full anonymity by allowing for voluntary participation in public goods games. This natural extension leads to "rock-scissors-paper"-type cyclic dominance of the three strategies, cooperate, defect, and loner. In spatial settings with players arranged on a regular lattice, this results in interesting dynamical properties and intriguing spatiotemporal patterns. In particular, variations of the value of the public good leads to transitions between one-, two-, and three-strategy states which either are in the class of directed percolation or show interesting analogies to Ising-type models. Although volunteering is incapable of stabilizing cooperation, it efficiently prevents successful spreading of selfish behavior.

Dynamic instabilities induced by asymmetric influence: prisoners' dilemma game in small-world networks

A two-dimensional small-world-type network, subject to spatial prisoners' dilemma dynamics and containing an influential node defined as a special node, with a finite density of directed random links to the other nodes in the network, is numerically investigated. It is shown that the degree of cooperation does not remain at a steady state level but displays a punctuated equilibrium-type behavior manifested by the existence of sudden breakdowns of cooperation. The breakdown of cooperation is linked to an imitation of a successful selfish strategy of the influential node. It is also found that while the breakdown of cooperation occurs suddenly, its recovery requires longer time. This recovery time may, depending on the degree of steady state cooperation, either increase or decrease with an increasing number of long-range connections.

Generalized contact process on random environments

Spreading from a seed is studied by Monte Carlo simulation on a square lattice with two types of sites affecting the rates of birth and death. These systems exhibit a critical transition between survival and extinction. For time-dependent background, this transition is equivalent to those found in homogeneous systems (i.e., to directed percolation). For frozen backgrounds, the appearance of the Griffiths phase prevents the accurate analysis of this transition. For long times in the subcritical region, the spreading remains localized in compact (rather than ramified) patches, and the average number of occupied sites increases logarithmically in the surviving trials.

Disordered environments in spatial games

The Prisoner's dilemma is the main game theoretical framework in which the onset and maintainance of cooperation in biological populations is studied. In the spatial version of the model, we study the robustness of cooperation in heterogeneous ecosystems in spatial evolutionary games by considering site diluted lattices. The main result is that, due to disorder, the fraction of cooperators in the population is enhanced. Moreover, the system presents a dynamical transition at rho*, separating a region with spatial chaos from one with localized, stable groups of cooperators.

Defensive alliances in spatial models of cyclical population interactions

As a generalization of the three-strategy Rock-Scissors-Paper game dynamics in space, cyclical interaction models of six mutating species are studied on a square lattice, in which each species is supposed to have two dominant, two subordinated, and a neutral interacting partner. Depending on their interaction topologies, all imaginable systems can be classified into four (isomorphic) groups exhibiting significantly different behaviors as a function of mutation rate. In three out of four cases three (or four) species form defensive alliances that maintain themselves in a self-organizing polydomain structure via cyclic invasions. Varying the mutation rate, this mechanism results in an ordering phenomenon analogous to that of magnetic Ising systems. The model explains a very basic mechanism of community organization, which might gain important applications in biology, economics, and sociology.