The replicator equation on graphs

Consolidating birth-death and death-birth processes in structured populations

Network models extend evolutionary game theory to settings with spatial or social structure and have provided key insights on the mechanisms underlying the evolution of cooperation. However, network models have also proven sensitive to seemingly small details of the model architecture. Here we investigate two popular biologically motivated models of evolution in finite populations: Death-Birth (DB) and Birth-Death (BD) processes. In both cases reproduction is proportional to fitness and death is random; the only difference is the order of the two events at each time step. Although superficially similar, under DB cooperation may be favoured in structured populations, while under BD it never is. This is especially troubling as natural populations do not follow a strict one birth then one death regimen (or vice versa); such constraints are introduced to make models more tractable. Whether structure can promote the evolution of cooperation should not hinge on a simplifying assumption. Here, we propose a mixed rule where in each time step DB is used with probability and BD is used with probability . We derive the conditions for selection favouring cooperation under the mixed rule for all social dilemmas. We find that the only qualitatively different outcome occurs when using just BD (). This case admits a natural interpretation in terms of kin competition counterbalancing the effect of kin selection. Finally we show that, for any mixed BD-DB update and under weak selection, cooperation is never inhibited by population structure for any social dilemma, including the Snowdrift Game.

Strategy diversity stabilizes mutualism through investment cycles, phase polymorphism, and spatial bubbles

There is continuing interest in understanding factors that facilitate the evolution and stability of cooperation within and between species. Such interactions will often involve plasticity in investment behavior, in response to the interacting partner's investments. Our aim here is to investigate the evolution and stability of reciprocal investment behavior in interspecific interactions, a key phenomenon strongly supported by experimental observations. In particular, we present a comprehensive analysis of a continuous reciprocal investment game between mutualists, both in well-mixed and spatially structured populations, and we demonstrate a series of novel mechanisms for maintaining interspecific mutualism. We demonstrate that mutualistic partners invariably follow investment cycles, during which mutualism first increases, before both partners eventually reduce their investments to zero, so that these cycles always conclude with full defection. We show that the key mechanism for stabilizing mutualism is phase polymorphism along the investment cycle. Although mutualistic partners perpetually change their strategies, the community-level distribution of investment levels becomes stationary. In spatially structured populations, the maintenance of polymorphism is further facilitated by dynamic mosaic structures, in which mutualistic partners form expanding and collapsing spatial bubbles or clusters. Additionally, we reveal strategy-diversity thresholds, both for well-mixed and spatially structured mutualistic communities, and discuss factors for meeting these thresholds, and thus maintaining mutualism. Our results demonstrate that interspecific mutualism, when considered as plastic investment behavior, can be unstable, and, in agreement with empirical observations, may involve a polymorphism of investment levels, varying both in space and in time. Identifying the mechanisms maintaining such polymorphism, and hence mutualism in natural communities, provides a significant step towards understanding the coevolution and population dynamics of mutualistic interactions.

Mutualistic interactions between species are often best understood as gradually adjustable reciprocal investments made continuously or iteratively between participants. Prime examples are the mycorrhizal and rhizobial mutualisms so strongly affecting the productivity of plants. When such interactions are described by continuous reciprocal investment games, participants adjust their investments plastically in response to their mutualistic partner's most recent investment. Although common sense suggests that such conditional or reactive behavior provides a potent defense against exploitation, our comprehensive model analysis reveals that the coevolution of investment strategies will often instead induce instability and decay of mutualistic interactions. We also identify several factors that can prevent this decay. First, mutualisms can be stably maintained if the investment strategies of participants are sufficiently diverse. Second, if participants are limited in their movements, the formation of dynamic spatial mosaic structures promotes strategy diversity and thereby facilitates the maintenance of mutualism. These ecological and evolutionary dynamics result in communities with a diversity of interaction types, ranging from mutually beneficial to exploitative, and varying both in space and in time.

Metastability and anomalous fixation in evolutionary games on scale-free networks

We study the influence of complex graphs on the metastability and fixation properties of a set of evolutionary processes. In the framework of evolutionary game theory, where the fitness and selection are frequency dependent and vary with the population composition, we analyze the dynamics of snowdrift games (characterized by a metastable coexistence state) on scale-free networks. Using an effective diffusion theory in the weak selection limit, we demonstrate how the scale-free structure affects the system's metastable state and leads to anomalous fixation. In particular, we analytically and numerically show that the probability and mean time of fixation are characterized by stretched-exponential behaviors with exponents depending on the network's degree distribution.

Defense mechanisms of empathetic players in the spatial ultimatum game

Experiments on the ultimatum game have revealed that humans are remarkably fond of fair play. When asked to share an amount of money, unfair offers are rare and their acceptance rate small. While empathy and spatiality may lead to the evolution of fairness, thus far considered continuous strategies have precluded the observation of solutions that would be driven by pattern formation. Here we introduce a spatial ultimatum game with discrete strategies, and we show that this simple alteration opens the gate to fascinatingly rich dynamical behavior. In addition to mixed stationary states, we report the occurrence of traveling waves and cyclic dominance, where one strategy in the cycle can be an alliance of two strategies. The highly webbed phase diagram, entailing continuous and discontinuous phase transitions, reveals hidden complexity in the pursuit of human fair play.

Approximating evolutionary dynamics on networks using a Neighbourhood Configuration model

Evolutionary dynamics have been traditionally studied on homogeneously mixed and infinitely large populations. However, real populations are finite and characterised by complex interactions among individuals. Recent studies have shown that the outcome of the evolutionary process might be significantly affected by the population structure. Although an analytic investigation of the process is possible when the contact structure of the population has a simple form, this is usually infeasible on complex structures and the use of various assumptions and approximations is necessary. In this paper, we adopt an approximation method which has been recently used for the modelling of infectious disease transmission to model evolutionary game dynamics on complex networks. Comparisons of the predictions of the model constructed with the results of computer simulations reveal the effectiveness of the method and the improved accuracy that it provides when, for example, compared to well-known pair approximation methods. This modelling framework offers a flexible way to carry out a systematic analysis of evolutionary game dynamics on graphs and to establish the link between network topology and potential system behaviours. As an example, we investigate how the Hawk and Dove strategies in a Hawk-Dove game spread in a population represented by a random regular graph, a random graph and a scale-free network, and we examine the features of the graph which affect the evolution of the population in this particular game.

Stochastic dynamics of the prisoner's dilemma with cooperation facilitators

In the framework of the paradigmatic prisoner's dilemma game, we investigate the evolutionary dynamics of social dilemmas in the presence of "cooperation facilitators." In our model, cooperators and defectors interact as in the classical prisoner's dilemma, where selection favors defection. However, here the presence of a small number of cooperation facilitators enhances the fitness (reproductive potential) of cooperators, while it does not alter that of defectors. In a finite population of size N, the dynamics of the prisoner's dilemma with facilitators is characterized by the probability that cooperation takes over (fixation probability) by the mean times to reach the absorbing states. These quantities are computed exactly using Fokker-Planck equations. Our findings, corroborated by stochastic simulations, demonstrate that the influence of facilitators crucially depends on the difference between their density z and the game's cost-to-benefit ratio r. When z > r, the fixation of cooperators is likely in a large population and, under weak selection pressure, invasion and replacement of defection by cooperation is favored by selection if b(z - r)(1 - z) > N(-1), where 0<b ≤ 1 is the cooperation payoff benefit. When z < r, the fixation probability of cooperators is exponentially enhanced by the presence of facilitators but defection is the dominating strategy.

Does synergy rescue the evolution of cooperation? An analysis for homogeneous populations with non-overlapping generations

Recent developments of social evolution theory have revealed conditions under which cooperation is favored by natural selection. Effects of population structure on the evolution of cooperation have been one of the central questions in this issue, and inclusive fitness analyses have unveiled two different selective forces that favor cooperation; the direct fitness effect to the helper and the indirect fitness benefit to the helper via its kin. Although these theoretical frameworks have made a significant contribution to our understanding of cooperative traits, there is still one factor to be taken into account, synergy. Synergy means a nonlinear effect that arises when two individuals help each other. In other words, it represents deviation from additivity, to which inclusive fitness theory has paid relatively little attention. Here I provide a theoretical result on the possibility that synergy favors the evolution of cooperation. For homogeneously structured populations with non-overlapping generations, I show that incorporating synergistic effects does not rescue the evolution of cooperation. Potential factors that could enable synergy to rescue the evolution of cooperation are also discussed.

Different reactions to adverse neighborhoods in games of cooperation

In social dilemmas, cooperation among randomly interacting individuals is often difficult to achieve. The situation changes if interactions take place in a network where the network structure jointly evolves with the behavioral strategies of the interacting individuals. In particular, cooperation can be stabilized if individuals tend to cut interaction links when facing adverse neighborhoods. Here we consider two different types of reaction to adverse neighborhoods, and all possible mixtures between these reactions. When faced with a gloomy outlook, players can either choose to cut and rewire some of their links to other individuals, or they can migrate to another location and establish new links in the new local neighborhood. We find that in general local rewiring is more favorable for the evolution of cooperation than emigration from adverse neighborhoods. Rewiring helps to maintain the diversity in the degree distribution of players and favors the spontaneous emergence of cooperative clusters. Both properties are known to favor the evolution of cooperation on networks. Interestingly, a mixture of migration and rewiring is even more favorable for the evolution of cooperation than rewiring on its own. While most models only consider a single type of reaction to adverse neighborhoods, the coexistence of several such reactions may actually be an optimal setting for the evolution of cooperation.

From local to global dilemmas in social networks

Social networks affect in such a fundamental way the dynamics of the population they support that the global, population-wide behavior that one observes often bears no relation to the individual processes it stems from. Up to now, linking the global networked dynamics to such individual mechanisms has remained elusive. Here we study the evolution of cooperation in networked populations and let individuals interact via a 2-person Prisoner's Dilemma – a characteristic defection dominant social dilemma of cooperation. We show how homogeneous networks transform a Prisoner's Dilemma into a population-wide evolutionary dynamics that promotes the coexistence between cooperators and defectors, while heterogeneous networks promote their coordination. To this end, we define a dynamic variable that allows us to track the self-organization of cooperators when co-evolving with defectors in networked populations. Using the same variable, we show how the global dynamics — and effective dilemma — co-evolves with the motifs of cooperators in the population, the overall emergence of cooperation depending sensitively on this co-evolution.

Network homophily and the evolution of the pay-it-forward reciprocity

The pay-it-forward reciprocity is a type of cooperative behavior that people who have benefited from others return favors to third parties other than the benefactors, thus pushing forward a cascade of kindness. The phenomenon of the pay-it-forward reciprocity is ubiquitous, yet how it evolves to be part of human sociality has not been fully understood. We develop an evolutionary dynamics model to investigate how network homophily influences the evolution of the pay-it-forward reciprocity. Manipulating the extent to which actors carrying the same behavioral trait are linked in networks, the computer simulation model shows that strong network homophily helps consolidate the adaptive advantage of cooperation, yet introducing some heterophily to the formation of network helps advance cooperation's scale further. Our model enriches the literature of inclusive fitness theory by demonstrating the conditions under which cooperation or reciprocity can be selected for in evolution when social interaction is not confined exclusively to relatives.

Choosing fitness-enhancing innovations can be detrimental under fluctuating environments

The ability to predict the consequences of one's behavior in a particular environment is a mechanism for adaptation. In the absence of any cost to this activity, we might expect agents to choose behaviors that maximize their fitness, an example of directed innovation. This is in contrast to blind mutation, where the probability of becoming a new genotype is independent of the fitness of the new genotypes. Here, we show that under environments punctuated by rapid reversals, a system with both genetic and cultural inheritance should not always maximize fitness through directed innovation. This is because populations highly accurate at selecting the fittest innovations tend to over-fit the environment during its stable phase, to the point that a rapid environmental reversal can cause extinction. A less accurate population, on the other hand, can track long term trends in environmental change, keeping closer to the time-average of the environment. We use both analytical and agent-based models to explore when this mechanism is expected to occur.

A review of evolutionary graph theory with applications to game theory

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

Evolutionary dynamics on stochastic evolving networks for multiple-strategy games

Evolutionary game theory on dynamical networks has received much attention. Most of the work has been focused on 2×2 games such as prisoner's dilemma and snowdrift, with general n×n games seldom addressed. In particular, analytical methods are still lacking. Here we generalize the stochastic linking dynamics proposed by Wu, Zhou, Fu, Luo, Wang, and Traulsen [PLoS ONE 5, e11187 (2010)] to n×n games. We analytically obtain that the fast linking dynamics results in the replicator dynamics with a rescaled payoff matrix. In the rescaled matrix, intuitively, each entry is the product of the original entry and the average duration time of the corresponding link. This result is shown to be robust to a wide class of imitation processes. As applications, we show both analytically and numerically that the biodiversity, modeled as the stability of a zero-sum rock-paper-scissors game, cannot be altered by the fast linking dynamics. In addition, we show that the fast linking dynamics can stabilize tit-for-tat as an evolutionary stable strategy in the repeated prisoner's dilemma game provided the interaction between the identical strategies happens sufficiently often. Our method paves the way for an analytical study of the multiple-strategy coevolutionary dynamics.

"If you can't be with the one you love, love the one you're with": how individual habituation of agent interactions improves global utility

Simple distributed strategies that modify the behavior of selfish individuals in a manner that enhances cooperation or global efficiency have proved difficult to identify. We consider a network of selfish agents who each optimize their individual utilities by coordinating (or anticoordinating) with their neighbors, to maximize the payoffs from randomly weighted pairwise games. In general, agents will opt for the behavior that is the best compromise (for them) of the many conflicting constraints created by their neighbors, but the attractors of the system as a whole will not maximize total utility. We then consider agents that act as creatures of habit by increasing their preference to coordinate (anticoordinate) with whichever neighbors they are coordinated (anticoordinated) with at present. These preferences change slowly while the system is repeatedly perturbed, so that it settles to many different local attractors. We find that under these conditions, with each perturbation there is a progressively higher chance of the system settling to a configuration with high total utility. Eventually, only one attractor remains, and that attractor is very likely to maximize (or almost maximize) global utility. This counterintuitive result can be understood using theory from computational neuroscience; we show that this simple form of habituation is equivalent to Hebbian learning, and the improved optimization of global utility that is observed results from well-known generalization capabilities of associative memory acting at the network scale. This causes the system of selfish agents, each acting individually but habitually, to collectively identify configurations that maximize total utility.

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.

The replicator dynamics with n players and population structure

The well-known replicator dynamics is usually applied to 2-player games and random matching. Here we allow for games with n players, and for population structures other than random matching. This more general application leads to a version of the replicator dynamics of which the standard 2-player, well-mixed version is a special case, and which allows us to explore the dynamic implications of population structure. The replicator dynamics also allows for a reformulation of the central theorem in Van Veelen (2009), which claims that inclusive fitness gives the correct prediction for games with generalized equal gains from switching (or, in other words, when fitness effects are additive). If we furthermore also assume that relatedness is constant during selection - which is a reasonable assumption in a setting with kin recognition - then inclusive fitness even becomes a parameter that determines the speed as well as the direction of selection. For games with unequal gains from switching, inclusive fitness can give the wrong prediction. With equal gains however, not only the sign, but also even the value of inclusive fitness becomes meaningful.

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.

Cooperation enhanced by the 'survival of the fittest' rule in prisoner's dilemma games on complex networks

Prevalence of cooperation within groups of selfish individuals is puzzling in that it contradicts with the basic premise of natural selection, whereby we introduce a model of strategy evolution taking place on evolving networks based on Darwinian 'survival of the fittest' rule. In the present work, players whose payoffs are below a certain threshold will be deleted and the same number of new nodes will be added to the network to maintain the constant system size. Furthermore, the networking effect is also studied via implementing simulations on four typical network structures. Numerical results show that cooperators can obtain the biggest boost if the elimination threshold is fine-tuned. Notably, this coevolutionary rule drives the initial networks to evolve into statistically stationary states with a broad-scale degree distribution. Our results may provide many more insights for understanding the coevolution of strategy and network topology under the mechanism of nature selection whereby superior individuals will prosper and inferior ones be eliminated.

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.

Cooperation, norms, and revolutions: a unified game-theoretical approach

Background

Cooperation is of utmost importance to society as a whole, but is often challenged by individual self-interests. While game theory has studied this problem extensively, there is little work on interactions within and across groups with different preferences or beliefs. Yet, people from different social or cultural backgrounds often meet and interact. This can yield conflict, since behavior that is considered cooperative by one population might be perceived as non-cooperative from the viewpoint of another.

Methodology and Principal Findings

To understand the dynamics and outcome of the competitive interactions within and between groups, we study game-dynamical replicator equations for multiple populations with incompatible interests and different power (be this due to different population sizes, material resources, social capital, or other factors). These equations allow us to address various important questions: For example, can cooperation in the prisoner's dilemma be promoted, when two interacting groups have different preferences? Under what conditions can costly punishment, or other mechanisms, foster the evolution of norms? When does cooperation fail, leading to antagonistic behavior, conflict, or even revolutions? And what incentives are needed to reach peaceful agreements between groups with conflicting interests?

Conclusions and Significance

Our detailed quantitative analysis reveals a large variety of interesting results, which are relevant for society, law and economics, and have implications for the evolution of language and culture as well.

Phase transitions to cooperation in the prisoner's dilemma

Game theory formalizes certain interactions between physical particles or between living beings in biology, sociology, and economics and quantifies the outcomes by payoffs. The prisoner's dilemma (PD) describes situations in which it is profitable if everybody cooperates rather than defects (free rides or cheats), but as cooperation is risky and defection is tempting, the expected outcome is defection. Nevertheless, some biological and social mechanisms can support cooperation by effectively transforming the payoffs. Here, we study the related phase transitions, which can be of first order (discontinuous) or of second order (continuous), implying a variety of different routes to cooperation. After classifying the transitions into cases of equilibrium displacement, equilibrium selection, and equilibrium creation, we show that a transition to cooperation may take place even if the stationary states and the eigenvalues of the replicator equation for the PD stay unchanged. Our example is based on adaptive group pressure, which makes the payoffs dependent on the endogenous dynamics in the population. The resulting bistability can invert the expected outcome in favor of 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.

Evolutionary games on graphs and the speed of the evolutionary process

In this paper, we investigate evolutionary games with the invasion process updating rules on three simple non-directed graphs: the star, the circle and the complete graph. Here, we present an analytical approach and derive the exact solutions of the stochastic evolutionary game dynamics. We present formulae for the fixation probability and also for the speed of the evolutionary process, namely for the mean time to absorption (either mutant fixation or extinction) and then the mean time to mutant fixation. Through numerical examples, we compare the different impact of the population size and the fitness of each type of individual on the above quantities on the three different structures. We do this comparison in two specific cases. Firstly, we consider the case where mutants have fixed fitness r and resident individuals have fitness 1. Then, we consider the case where the fitness is not constant but depends on games played among the individuals, and we introduce a ‘hawk–dove’ game as an example.

Population structure induces a symmetry breaking favoring the emergence of cooperation

The evolution of cooperation described in terms of simple two-person interactions has received considerable attention in recent years, where several key results were obtained. Among those, it is now well established that the web of social interaction networks promotes the emergence of cooperation when modeled in terms of symmetric two-person games. Up until now, however, the impacts of the heterogeneity of social interactions into the emergence of cooperation have not been fully explored, as other aspects remain to be investigated. Here we carry out a study employing the simplest example of a prisoner's dilemma game in which the benefits collected by the participants may be proportional to the costs expended. We show that the heterogeneous nature of the social network naturally induces a symmetry breaking of the game, as contributions made by cooperators may become contingent on the social context in which the individual is embedded. A new, numerical, mean-field analysis reveals that prisoner's dilemmas on networks no longer constitute a defector dominance dilemma—instead, individuals engage effectively in a general coordination game. We find that the symmetry breaking induced by population structure profoundly affects the evolutionary dynamics of cooperation, dramatically enhancing the feasibility of cooperators: cooperation blooms when each cooperator contributes the same cost, equally shared among the plethora of games in which she participates. This work provides clear evidence that, while individual rational reasoning may hinder cooperative actions, the intricate nature of social interactions may effectively transform a local dilemma of cooperation into a global coordination problem.

Humans contribute to a broad range of cooperative endeavors. In many of them, the amount or effort contributed often depends on the social context of each individual. Recent evidence has shown how modern societies are grounded in complex and heterogeneous networks of exchange and cooperation, in which some individuals play radically different roles and/or interact more than others. We show that such social heterogeneity drastically affects the behavioral dynamics and promotes cooperative behavior, whenever the social dilemma perceived by each individual is contingent on her/his social context. The multiplicity of roles and contributions induced by realistic population structures is shown to transform an initial defection dominance dilemma into a coordination challenge or even a cooperator dominance game. While locally defection may seem inescapable, globally there is an emergent new dilemma in which cooperation often prevails, illustrating how collective cooperative action may emerge from myopic individual selfishness.

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.

A mechanism of dynamical interactions for two-person social dilemmas

We propose a new mechanism of interactions between game-theoretical agents in which the weights of the connections between interacting individuals are dynamical, payoff-dependent variables. Their evolution depends on the difference between the payoff of the agents from a given type of encounter and their average payoff. The mechanism is studied in the frame of two models: agents distributed on a random graph, and a mean field model. Symmetric and asymmetric connections between the agents are introduced. Long time behavior of both systems is discussed for the Prisoner's Dilemma and the Snow Drift games.

Social network reciprocity as a phase transition in evolutionary cooperation

In evolutionary dynamics the understanding of cooperative phenomena in natural and social systems has been the subject of intense research during decades. We focus attention here on the so-called "lattice reciprocity" mechanisms that enhance evolutionary survival of the cooperative phenotype in the prisoner's dilemma game when the population of Darwinian replicators interact through a fixed network of social contacts. Exact results on a "dipole model" are presented, along with a mean-field analysis as well as results from extensive numerical Monte Carlo simulations. The theoretical framework used is that of standard statistical mechanics of macroscopic systems, but with no energy considerations. We illustrate the power of this perspective on social modeling, by consistently interpreting the onset of lattice reciprocity as a thermodynamical phase transition that, moreover, cannot be captured by a purely mean-field approach.

Toward evolutionary graphs with two sexes: a kin selection analysis of a sex allocation problem

Evolutionary graphs are used to model the effects of spatial and social structure in social evolutionary problems (e.g. evolutionary games). Recent work has highlighted the fact that evolution on graphs can be understood using kin selection theory. This paper shows how one can use kin selection to study evolutionary graphs inhabited by a diploid sexual organism by means of a simple example. Specifically, we study the well-known sex allocation problem of how best to divide a fixed amount of effort between the production of sons on the one hand and the production of daughters on the other. Like many previous studies, we identify equal investment in sons and daughters as the only phenotype favoured by selection. Our analysis also highlights the advantages and disadvantages of applying kin selection to the study of evolutionary graphs.

Prisoner's dilemma on a stochastic nongrowth network evolution model

We investigate the evolution of cooperation on a nongrowth dynamic network model with a death-birth dynamics based on tournament selection. In the limit of large population size, the equilibrium cooperator density is well described by our mean field approximations and inversely related to the average degree in the system. Small populations are also examined and found to deviate considerably from their expected mean field behavior. An expanded replicator equation incorporating Gaussian fluctuations in the strategy densities is then constructed, with its output agreeing well with our simulation data for all sizes. We also briefly comment on the role of strategy mutation in sustaining polymorphic populations in small systems.

Evolutionary prisoner's dilemma game on Newman-Watts networks

Maintenance of cooperation was studied for a two-strategy evolutionary prisoner's dilemma game where the players are located on a one-dimensional chain and their payoff comes from games with the nearest- and next-nearest-neighbor interactions. The applied host geometry makes it possible to study the impacts of two conflicting topological features. The evolutionary rule involves some noise affecting the strategy adoptions between the interacting players. Using Monte Carlo simulations and the extended versions of dynamical mean-field theory we determined the phase diagram as a function of noise level and a payoff parameter. The peculiar feature of the diagram is changed significantly when the connectivity structure is extended by extra links as suggested by Newman and Watts.

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.

Mixed evolutionary strategies imply coexisting opinions on networks

An evolutionary battle-of-the-sexes game is proposed to model the opinion formation on networks. The individuals of a network are partitioned into different classes according to their unaltered opinion preferences, and their factual opinions are considered as the evolutionary strategies, which are updated with the birth-death or death-birth rules to imitate the process of opinion formation. The individuals finally reach a consensus in the dominate opinion or fall into (quasi)stationary fractions of coexisting mixed opinions, presenting a phase transition at the critical modularity of the multiclass individuals' partitions on networks. The stability analysis on the coexistence of mixed strategies among multiclass individuals is given, and the analytical predictions agree well with the numerical simulations, indicating that the individuals of a community (or modular) structured network are prone to form coexisting opinions, and the coexistence of mixed evolutionary strategies implies the modularity of networks.

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.

Promotion of cooperation by payoff noise in a 2x2 game

A series of numerical simulations of a 2x2 symmetric game on a network examined whether payoff matrix noise promotes cooperation, as reported initially by Perc [New J. Phys. 8, 22 (2006)]. Agents have no memory (they offer cooperation, C, or defection, D). We assume that the network is time invariable. The effect of payoff matrix noise (PMN) is measured by a simulated payoff difference between a normal network game and a network game with PMN. The effect of PMN appears only when a local strategy adaptation is implemented (for example, a network game with imitation dynamics). The influence of PMN becomes more significant with a larger stochastic deviation, and less significant in a larger degree network. One reason for PMN's effectiveness is the local strategy adaptation mechanism, which helps both the preservation and fixation of C agents, and not that the payoff matrix noise makes a dilemma game into a Trivial (dilemma-free) game.

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.

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.

Upstream reciprocity and the evolution of gratitude

If someone is nice to you, you feel good and may be inclined to be nice to somebody else. This every day experience is borne out by experimental games: the recipients of an act of kindness are more likely to help in turn, even if the person who benefits from their generosity is somebody else. This behaviour, which has been called 'upstream reciprocity', appears to be a misdirected act of gratitude: you help somebody because somebody else has helped you. Does this make any sense from an evolutionary or a game theoretic perspective? In this paper, we show that upstream reciprocity alone does not lead to the evolution of cooperation, but it can evolve and increase the level of cooperation if it is linked to either direct or spatial reciprocity. We calculate the random walks of altruistic acts that are induced by upstream reciprocity. Our analysis shows that gratitude and other positive emotions, which increase the willingness to help others, can evolve in the competitive world of natural selection.

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.

Stochastic payoff evaluation increases the temperature of selection

We study stochastic evolutionary game dynamics in populations of finite size. Moreover, each individual has a randomly distributed number of interactions with other individuals. Therefore, the payoff of two individuals using the same strategy can be different. The resulting "payoff stochasticity" reduces the intensity of selection and therefore increases the temperature of selection. A simple mean-field approximation is derived that captures the average effect of the payoff stochasticity. Correction terms to the mean-field theory are computed and discussed.