Bipartite graphs as models of population structures in evolutionary multiplayer games

By combining evolutionary game theory and graph theory, "games on graphs" study the evolutionary dynamics of frequency-dependent selection in population structures modeled as geographical or social networks. Networks are usually represented by means of unipartite graphs, and social interactions by two-person games such as the famous prisoner's dilemma. Unipartite graphs have also been used for modeling interactions going beyond pairwise interactions. In this paper, we argue that bipartite graphs are a better alternative to unipartite graphs for describing population structures in evolutionary multiplayer games. To illustrate this point, we make use of bipartite graphs to investigate, by means of computer simulations, the evolution of cooperation under the conventional and the distributed N-person prisoner's dilemma. We show that several implicit assumptions arising from the standard approach based on unipartite graphs (such as the definition of replacement neighborhoods, the intertwining of individual and group diversity, and the large overlap of interaction neighborhoods) can have a large impact on the resulting evolutionary dynamics. Our work provides a clear example of the importance of construction procedures in games on graphs, of the suitability of bigraphs and hypergraphs for computational modeling, and of the importance of concepts from social network analysis such as centrality, centralization and bipartite clustering for the understanding of dynamical processes occurring on networked population structures.     

The evolution of payoff matrices: providing incentives to cooperate

Most of the work in evolutionary game theory starts with a model of a social situation that gives rise to a particular payoff matrix and analyses how behaviour evolves through natural selection. Here, we invert this approach and ask, given a model of how individuals behave, how the payoff matrix will evolve through natural selection. In particular, we ask whether a prisoner's dilemma game is stable against invasions by mutant genotypes that alter the payoffs. To answer this question, we develop a two-tiered framework with goal-oriented dynamics at the behavioural time scale and a diploid population genetic model at the evolutionary time scale. Our results are two-fold: first, we show that the prisoner's dilemma is subject to invasions by mutants that provide incentives for cooperation to their partners, and that the resulting game is a coordination game similar to the hawk-dove game. Second, we find that for a large class of mutants and symmetric games, a stable genetic polymorphism will exist in the locus determining the payoff matrix, resulting in a complex pattern of behavioural diversity in the population. Our results highlight the importance of considering the evolution of payoff matrices to understand the evolution of animal social systems.     

Chaos, oscillation and the evolution of indirect reciprocity in n-person games

Evolution of cooperation among genetically unrelated individuals has been of considerable concern in various fields such as biology, economics, and psychology. The evolution of cooperation is often explained by reciprocity. Under reciprocity, cooperation can prevail in a society because a donor of cooperation receives reciprocation from the recipient of the cooperation, called direct reciprocity, or from someone else in the community, called indirect reciprocity. Nowak and Sigmund [1993. Chaos and the evolution of cooperation. Proc. Natl. Acad. Sci. USA 90, 5091-5094] have demonstrated that directly reciprocal cooperation in two-person prisoner's dilemma games with mutation of strategies can be maintained dynamically as periodic or chaotic oscillation. Furthermore, Eriksson and Lindgren [2005. Cooperation driven by mutations in multi-person Prisoner's Dilemma. J. Theor. Biol. 232, 399-409] have reported that directly reciprocal cooperation in n-person prisoner's dilemma games (n>2) can be maintained as periodic oscillation. Is dynamic cooperation observed only in direct reciprocity? Results of this study show that indirectly reciprocal cooperation in n-person prisoner's dilemma games can be maintained dynamically as periodic or chaotic oscillation. This is, to our knowledge, the first demonstration of chaos in indirect reciprocity. Furthermore, the results show that oscillatory dynamics are observed in common in the evolution of reciprocal cooperation whether for direct or indirect.     

The continuous prisoner's dilemma and the evolution of cooperation through reciprocal altruism with variable investment

Understanding the evolutionary origin and persistence of cooperative behavior is a fundamental biological problem. The standard "prisoner's dilemma," which is the most widely adopted framework for studying the evolution of cooperation through reciprocal altruism between unrelated individuals, does not allow for varying degrees of cooperation. Here we study the continuous iterated prisoner's dilemma, in which cooperative investments can vary continuously in each round. This game has been previously considered for a class of reactive strategies in which current investments are based on the partner's previous investment. In the standard iterated prisoner's dilemma, such strategies are inferior to strategies that take into account both players' previous moves, as is exemplified by the evolutionary dominance of "Pavlov" over "tit for tat." Consequently, we extend the analysis of the continuous prisoner's dilemma to a class of strategies in which current investments depend on previous payoffs and, hence, on both players' previous investments. We show, both analytically and by simulation, that payoff-based strategies, which embody the intuitively appealing idea that individuals invest more in cooperative interactions when they profit from these interactions, provide a natural explanation for the gradual evolution of cooperation from an initially noncooperative state and for the maintenance of cooperation thereafter.     

The different limits of weak selection and the evolutionary dynamics of finite populations

Evolutionary theory often resorts to weak selection, where different individuals have very similar fitness. Here, we relate two ways to introduce weak selection. The first considers evolutionary games described by payoff matrices with similar entries. This approach has recently attracted a lot of interest in the context of evolutionary game dynamics in finite populations. The second way to introduce weak selection is based on small distances in phenotype space and is a standard approach in kin-selection theory. Whereas both frameworks are interchangeable for constant fitness, frequency-dependent selection shows significant differences between them. We point out the difference between both limits of weak selection and discuss the condition under which the differences vanish. It turns out that this condition is fulfilled by the popular parametrization of the prisoner's dilemma in benefits and costs. However, for general payoff matrices differences between the two frameworks prevail.     

Game dynamics and evolutionary transitions

An evolutionary model based on the Taylor-Jonker game dynamics is presented. A set of strategies is compatible if there exists a dynamical equilibrium between its members and there is an evolutionary transition to another compatible set if new mutant strategies bring about a passage to another equilibrium. We apply these concepts to supergame strategies, which play repeatedly a given matrix game and at each time step choose their pure strategy according to the preceding moves of the opponent. We investigate the patterns of evolution in zero-sum games, games of partnership, the prisoner's dilemma and the hawkdove game.     

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

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

The evolution of reciprocity in sizable groups

Recently, several authors have investigated the evolution of reciprocal altruism using the repeated prisoner's dilemma game. These models suggest that natural selection is likely to favor behavioral strategies leading to reciprocal cooperation when pairs of individuals interact repeatedly in potentially cooperative situations. Using the repeated n-person prisoner's dilemma game, we consider whether reciprocal altruism is also likely to evolve when social interactions involve more individuals. We show that the conditions that allow the evolution of reciprocal cooperation become extremely restrictive as group size increases.     

Spatial effects in social dilemmas

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

Evolutionary games and population dynamics: maintenance of cooperation in public goods games

The emergence and abundance of cooperation in nature poses a tenacious and challenging puzzle to evolutionary biology. Cooperative behaviour seems to contradict Darwinian evolution because altruistic individuals increase the fitness of other members of the population at a cost to themselves. Thus, in the absence of supporting mechanisms, cooperation should decrease and vanish, as predicted by classical models for cooperation in evolutionary game theory, such as the Prisoner's Dilemma and public goods games. Traditional approaches to studying the problem of cooperation assume constant population sizes and thus neglect the ecology of the interacting individuals. Here, we incorporate ecological dynamics into evolutionary games and reveal a new mechanism for maintaining cooperation. In public goods games, cooperation can gain a foothold if the population density depends on the average population payoff. Decreasing population densities, due to defection leading to small payoffs, results in smaller interaction group sizes in which cooperation can be favoured. This feedback between ecological dynamics and game dynamics can generate stable coexistence of cooperators and defectors in public goods games. However, this mechanism fails for pairwise Prisoner's Dilemma interactions and the population is driven to extinction. Our model represents natural extension of replicator dynamics to populations of varying densities.     

Win-stay-lose-learn promotes cooperation in the spatial prisoner's dilemma game

Holding on to one's strategy is natural and common if the later warrants success and satisfaction. This goes against widespread simulation practices of evolutionary games, where players frequently consider changing their strategy even though their payoffs may be marginally different than those of the other players. Inspired by this observation, we introduce an aspiration-based win-stay-lose-learn strategy updating rule into the spatial prisoner's dilemma game. The rule is simple and intuitive, foreseeing strategy changes only by dissatisfied players, who then attempt to adopt the strategy of one of their nearest neighbors, while the strategies of satisfied players are not subject to change. We find that the proposed win-stay-lose-learn rule promotes the evolution of cooperation, and it does so very robustly and independently of the initial conditions. In fact, we show that even a minute initial fraction of cooperators may be sufficient to eventually secure a highly cooperative final state. In addition to extensive simulation results that support our conclusions, we also present results obtained by means of the pair approximation of the studied game. Our findings continue the success story of related win-stay strategy updating rules, and by doing so reveal new ways of resolving the prisoner's dilemma.     

Participation costs dismiss the advantage of heterogeneous networks in evolution of cooperation

Real social interactions occur on networks in which each individual is connected to some, but not all, of others. In social dilemma games with a fixed population size, heterogeneity in the number of contacts per player is known to promote evolution of cooperation. Under a common assumption of positively biased pay-off structure, well-connected players earn much by playing frequently, and cooperation once adopted by well-connected players is unbeatable and spreads to others. However, maintaining a social contact can be costly, which would prevent local pay-offs from being positively biased. In replicator-type evolutionary dynamics, it is shown that even a relatively small participation cost extinguishes the merit of heterogeneous networks in terms of cooperation. In this situation, more connected players earn less so that they are no longer spreaders of cooperation. Instead, those with fewer contacts win and guide the evolution. The participation cost, or the baseline pay-off, is irrelevant in homogeneous populations, but is essential for evolutionary games on heterogeneous networks.     

How is the equilibrium of continuous strategy game different from that of discrete strategy game?

Cooperation in the prisoner's dilemma (PD) played on various networks has been explained by so-called network reciprocity. Most of the previous studies presumed that players can offer either cooperation (C) or defection (D). This discrete strategy seems unrealistic in the real world, since actual provisions might not be discrete, but rather continuous. This paper studies the differences between continuous and discrete strategies in two aspects under the condition that the payoff function of the former is a linear interpolation of the payoff matrix of the latter. The first part of this paper proves theoretically that for two-player games, continuous and discrete strategies have different equilibria and game dynamics in a well-mixed but finite population. The second part, conducting a series of numerical experiments, reveals that such differences become considerably large in the case of PD games on networks. Furthermore, it shows, using the Wilcoxon sign-rank test, that continuous and discrete strategy games are statistically significantly different in terms of equilibria. Intensive discussion by comparing these two kinds of games elucidates that describing a strategy as a real number blunts D strategy invasion to C clusters on a network in the early stage of evolution. Thus, network reciprocity is enhanced by the continuous strategy.     

The structure of mutations and the evolution of cooperation

Evolutionary game dynamics in finite populations assumes that all mutations are equally likely, i.e., if there are n strategies a single mutation can result in any strategy with probability 1/n. However, in biological systems it seems natural that not all mutations can arise from a given state. Certain mutations may be far away, or even be unreachable given the current composition of an evolving population. These distances between strategies (or genotypes) define a topology of mutations that so far has been neglected in evolutionary game theory. In this paper we re-evaluate classic results in the evolution of cooperation departing from the assumption of uniform mutations. We examine two cases: the evolution of reciprocal strategies in a repeated prisoner's dilemma, and the evolution of altruistic punishment in a public goods game. In both cases, alternative but reasonable mutation kernels shift known results in the direction of less cooperation. We therefore show that assuming uniform mutations has a substantial impact on the fate of an evolving population. Our results call for a reassessment of the "model-less" approach to mutations in evolutionary dynamics.     

Resolving the iterated prisoner's dilemma: theory and reality

Pairs of unrelated individuals face a prisoner's dilemma if cooperation is the best mutual outcome, but each player does best to defect regardless of his partner's behaviour. Although mutual defection is the only evolutionarily stable strategy in one-shot games, cooperative solutions based on reciprocity can emerge in iterated games. Among the most prominent theoretical solutions are the so-called bookkeeping strategies, such as tit-for-tat, where individuals copy their partner's behaviour in the previous round. However, the lack of empirical data conforming to predicted strategies has prompted the suggestion that the iterated prisoner's dilemma (IPD) is neither a useful nor realistic basis for investigating cooperation. Here, we discuss several recent studies where authors have used the IPD framework to interpret their data. We evaluate the validity of their approach and highlight the diversity of proposed solutions. Strategies based on precise accounting are relatively uncommon, perhaps because the full set of assumptions of the IPD model are rarely satisfied. Instead, animals use a diverse array of strategies that apparently promote cooperation, despite the temptation to cheat. These include both positive and negative reciprocity, as well as long-term mutual investments based on 'friendships'. Although there are various gaps in these studies that remain to be filled, we argue that in most cases, individuals could theoretically benefit from cheating and that cooperation cannot therefore be explained with the concept of positive pseudo-reciprocity. We suggest that by incorporating empirical data into the theoretical framework, we may gain fundamental new insights into the evolution of mutual reciprocal investment in nature.     

Moving away from nasty encounters enhances cooperation in ecological prisoner's dilemma game

We study the role of migration in the evolution of cooperation. Individuals spatially located on a square lattice play the prisoner's dilemma game. Dissatisfied players, who have been exploited by defectors, tend to terminate interaction with selfish partners by leaving the current habitats, and explore unknown physical niches available surrounding them. The time scale ratio of game interaction to natural selection governs how many game rounds occur before individuals experience strategy updating. Under local migration and strong selection, simulation results demonstrate that cooperation can be stabilized for a wide range of model parameters, and the slower the natural selection, the more favorable for the emergence of cooperation. Besides, how the selection intensity affects cooperators' evolutionary fate is also investigated. We find that increasing it weakens cooperators' viability at different speeds for different time scale ratios. However, cooperation is greatly improved provided that individuals are offered with enough chance to agglomerate, while cooperation can always establish under weak selection but vanishes under very strong selection whenever individuals have less odds to migrate. Whenever the migration range restriction is removed, the parameter area responsible for the emergence of cooperation is, albeit somewhat compressed, still remarkable, validating the effectiveness of collectively migrating in promoting cooperation.     

Beyond the prisoner's dilemma: Toward models to discriminate among mechanisms of cooperation in nature

The iterated prisoner's dilemma game, or IPD, has now established itself as the orthodox paradigm for theoretical investigations of the evolution of cooperation; but its scope is restricted to reciprocity, which is only one of three categories of cooperation among unrelated individuals. Even within that category, a cooperative encounter has in general three phases, and the IPD has nothing to say about two of them. To distinguish among mechanisms of cooperation in nature, future theoretical work on the evolution of cooperation must distance itself from economics and develop games as a refinement of ethology's comparative approach.     

The evolution of altruism: game theory in multilevel selection and inclusive fitness

Although the prisoner's dilemma (PD) has been used extensively to study reciprocal altruism, here we show that the n-player prisoner's dilemma (NPD) is also central to two other prominent theories of the evolution of altruism: inclusive fitness and multilevel selection. An NPD model captures the essential factors for the evolution of altruism directly in its parameters and integrates important aspects of these two theories such as Hamilton's rule, Simpson's paradox, and the Price covariance equation. The model also suggests a simple interpretation of the Price selection decomposition and an alternative decomposition that is symmetrical and complementary to it. In some situations this alternative shows the temporal changes in within- and between-group selection more clearly than the Price equation. In addition, we provide a new perspective on strong vs. weak altruism by identifying their different underlying game structures (based on absolute fitness) and showing how their evolutionary dynamics are nevertheless similar under selection (based on relative fitness). In contrast to conventional wisdom, the model shows that both strong and weak altruism can evolve in periodically formed random groups of non-conditional strategies if groups are multigenerational. An integrative approach based on the NPD helps unify different perspectives on the evolution of altruism.     

Evolutionary escape from the prisoner's dilemma

The classic prisoner's dilemma model of game theory is modified by introducing occasional variations on the options available to players. Mutation and selection of game options reliably change the game matrix, gradually, from a prisoner's dilemma game into a byproduct mutualism one, in which cooperation is stable, and "temptation to defect" is replaced by temptation to cooperate. This result suggests that when there are many different potential ways of interacting, exploring those possibilities may make escape from prisoner's dilemmas a common outcome in the world. A consequence is that persistent prisoner's dilemma structures may be less common than one might otherwise expect.     

Evolution of interactions and cooperation in the spatial prisoner's dilemma game

We study the evolution of cooperation in the spatial prisoner's dilemma game where players are allowed to establish new interactions with others. By employing a simple coevolutionary rule entailing only two crucial parameters, we find that different selection criteria for the new interaction partners as well as their number vitally affect the outcome of the game. The resolution of the social dilemma is most probable if the selection favors more successful players and if their maximally attainable number is restricted. While the preferential selection of the best players promotes cooperation irrespective of game parametrization, the optimal number of new interactions depends somewhat on the temptation to defect. Our findings reveal that the "making of new friends" may be an important activity for the successful evolution of cooperation, but also that partners must be selected carefully and their number limited.