Structure coefficients and strategy selection in multiplayer games

Evolutionary dynamics of any multiplayer game on regular graphs

Multiplayer games on graphs are at the heart of theoretical descriptions of key evolutionary processes that govern vital social and natural systems. However, a comprehensive theoretical framework for solving multiplayer games with an arbitrary number of strategies on graphs is still missing. Here, we solve this by drawing an analogy with the Balls-and-Boxes problem, based on which we show that the local configuration of multiplayer games on graphs is equivalent to distributing k identical co-players among n distinct strategies. We use this to derive the replicator equation for any n-strategy multiplayer game under weak selection, which can be solved in polynomial time. As an example, we revisit the second-order free-riding problem, where costly punishment cannot truly resolve social dilemmas in a well-mixed population. Yet, in structured populations, we derive an accurate threshold for the punishment strength, beyond which punishment can either lead to the extinction of defection or transform the system into a rock-paper-scissors-like cycle. The analytical solution also qualitatively agrees with the phase diagrams that were previously obtained for non-marginal selection strengths. Our framework thus allows an exploration of any multi-strategy multiplayer game on regular graphs.

Fixation probabilities in evolutionary dynamics under weak selection

In evolutionary dynamics, a key measure of a mutant trait's success is the probability that it takes over the population given some initial mutant-appearance distribution. This "fixation probability" is difficult to compute in general, as it depends on the mutation's effect on the organism as well as the population's spatial structure, mating patterns, and other factors. In this study, we consider weak selection, which means that the mutation's effect on the organism is small. We obtain a weak-selection perturbation expansion of a mutant's fixation probability, from an arbitrary initial configuration of mutant and resident types. Our results apply to a broad class of stochastic evolutionary models, in which the size and spatial structure are arbitrary (but fixed). The problem of whether selection favors a given trait is thereby reduced from exponential to polynomial complexity in the population size, when selection is weak. We conclude by applying these methods to obtain new results for evolutionary dynamics on graphs.

Learning enables adaptation in cooperation for multi-player stochastic games

Interactions among individuals in natural populations often occur in a dynamically changing environment. Understanding the role of environmental variation in population dynamics has long been a central topic in theoretical ecology and population biology. However, the key question of how individuals, in the middle of challenging social dilemmas (e.g. the 'tragedy of the commons'), modulate their behaviours to adapt to the fluctuation of the environment has not yet been addressed satisfactorily. Using evolutionary game theory, we develop a framework of stochastic games that incorporates the adaptive mechanism of reinforcement learning to investigate whether cooperative behaviours can evolve in the ever-changing group interaction environment. When the action choices of players are just slightly influenced by past reinforcements, we construct an analytical condition to determine whether cooperation can be favoured over defection. Intuitively, this condition reveals why and how the environment can mediate cooperative dilemmas. Under our model architecture, we also compare this learning mechanism with two non-learning decision rules, and we find that learning significantly improves the propensity for cooperation in weak social dilemmas, and, in sharp contrast, hinders cooperation in strong social dilemmas. Our results suggest that in complex social-ecological dilemmas, learning enables the adaptation of individuals to varying environments.

Evolutionary multiplayer games on graphs with edge diversity

Evolutionary game dynamics in structured populations has been extensively explored in past decades. However, most previous studies assume that payoffs of individuals are fully determined by the strategic behaviors of interacting parties, and social ties between them only serve as the indicator of the existence of interactions. This assumption neglects important information carried by inter-personal social ties such as genetic similarity, geographic proximity, and social closeness, which may crucially affect the outcome of interactions. To model these situations, we present a framework of evolutionary multiplayer games on graphs with edge diversity, where different types of edges describe diverse social ties. Strategic behaviors together with social ties determine the resulting payoffs of interactants. Under weak selection, we provide a general formula to predict the success of one behavior over the other. We apply this formula to various examples which cannot be dealt with using previous models, including the division of labor and relationship- or edge-dependent games. We find that labor division can promote collective cooperation markedly. The evolutionary process based on relationship-dependent games can be approximated by interactions under a transformed and unified game. Our work stresses the importance of social ties and provides effective methods to reduce the calculating complexity in analyzing the evolution of realistic systems.

Fixation properties of multiple cooperator configurations on regular graphs

Whether or not cooperation is favored in evolutionary games on graphs depends on the population structure and spatial properties of the interaction network. The population structure can be expressed as configurations. Such configurations extend scenarios with a single cooperator among defectors to any number of cooperators and any arrangement of cooperators and defectors on the network. For interaction networks modeled as regular graphs and for weak selection, the emergence of cooperation can be assessed by structure coefficients, which can be specified for each configuration and each regular graph. Thus, as a single cooperator can be interpreted as a lone mutant, the configuration-based structure coefficients also describe fixation properties of multiple mutants. We analyze the structure coefficients and particularly show that under certain conditions, the coefficients strongly correlate to the average shortest path length between cooperators on the evolutionary graph. Thus, for multiple cooperators fixation properties on regular evolutionary graphs can be linked to cooperator path lengths.

Harsh environments: Multi-player cooperation with excludability and congestion

The common-enemy hypothesis of by-product mutualism proposes that organisms are more likely to cooperate when facing the common enemy of a harsher environment. Micro-foundations of this hypothesis have so far focused on the case where cooperation consists of the production of a pure public good. In this case, the effect of a harsher environment is ambiguous: not only a common-enemy effect is possible, but also an opposite, competing effect where the harsher environment reduces the probability of cooperation. This paper shows that unambiguous effects of a harsher environment are predicted when considering the realistic case where the collective good produced is excludable (in the sense that whether or not a player benefits from the collective good depends on whether or not he is contributing) and/or congestible (in the sense that the benefits the individual player obtains from the collective good are affected by the number of contributing players). In particular, the competing effect is systematically predicted for club goods, where defectors are excluded from the benefits of the collective good. A common-enemy effect is instead systematically predicted for charity goods, where cooperators are excluded from the benefits of the collective good. These effects are maintained for congestible club goods and for congestible charity goods. As the degree to which a collective good is excludable can be meaningfully compared across different instances of cooperation, these contrasting predictions for public good, charity goods and club goods yield testable hypotheses for the common-enemy hypothesis of by-product mutualism.

A mathematical formalism for natural selection with arbitrary spatial and genetic structure

We define a general class of models representing natural selection between two alleles. The population size and spatial structure are arbitrary, but fixed. Genetics can be haploid, diploid, or otherwise; reproduction can be asexual or sexual. Biological events (e.g. births, deaths, mating, dispersal) depend in arbitrary fashion on the current population state. Our formalism is based on the idea of genetic sites. Each genetic site resides at a particular locus and houses a single allele. Each individual contains a number of sites equal to its ploidy (one for haploids, two for diploids, etc.). Selection occurs via replacement events, in which alleles in some sites are replaced by copies of others. Replacement events depend stochastically on the population state, leading to a Markov chain representation of natural selection. Within this formalism, we define reproductive value, fitness, neutral drift, and fixation probability, and prove relationships among them. We identify four criteria for evaluating which allele is selected and show that these become equivalent in the limit of low mutation. We then formalize the method of weak selection. The power of our formalism is illustrated with applications to evolutionary games on graphs and to selection in a haplodiploid population.

The Red Queen and King in finite populations

In antagonistic symbioses, such as host-parasite interactions, one population's success is the other's loss. In mutualistic symbioses, such as division of labor, both parties can gain, but they might have different preferences over the possible mutualistic arrangements. The rates of evolution of the two populations in a symbiosis are important determinants of which population will be more successful: Faster evolution is thought to be favored in antagonistic symbioses (the "Red Queen effect"), but disfavored in certain mutualistic symbioses (the "Red King effect"). However, it remains unclear which biological parameters drive these effects. Here, we analyze the effects of the various determinants of evolutionary rate: generation time, mutation rate, population size, and the intensity of natural selection. Our main results hold for the case where mutation is infrequent. Slower evolution causes a long-term advantage in an important class of mutualistic interactions. Surprisingly, less intense selection is the strongest driver of this Red King effect, whereas relative mutation rates and generation times have little effect. In antagonistic interactions, faster evolution by any means is beneficial. Our results provide insight into the demographic evolution of symbionts.

Which facilitates the evolution of cooperation more, retaliation or persistence?

The existence of cooperation in this world is a mysterious phenomenon. One of the mechanisms that explain the evolution of cooperation is repeated interaction. If interactions between the same individuals repeat and individuals cooperate conditionally, cooperation can evolve. A previous study pointed out that if individuals have persistence (i.e., imitate its "own" behavior in the last move), cooperation can evolve. However, retaliation and persistence are not mutually exclusive decisions, but rather a trade-off in the decision making process of individuals. Players can refer to the opponent's behavior and if the actor and the opponent opted for the different alternative in the last move, conditional cooperators have to give up either retaliation or persistence. The previous study also investigated this, and has revealed that the individual should give more importance to retaliation than to persistence. However, this study has assumed that the errors in perception are absent. In this world, errors in perception are present, and trying to imitate the opponent player can sometimes end in failure. And, it might be that imitating the focal player, which definitely ends in success, is more beneficial than trying to imitate the opponent player, which can end in failure especially when the error rate in recognition is large. Here, this paper uses evolutionarily stable strategy (ESS) analysis and analyzes the stability for reactive strategies against the invasion by unconditional defectors in the iterated prisoner's dilemma game. And our analysis reveals that even if we take errors in perception into consideration, retaliation facilitates the evolution of cooperation more than persistence unexpectedly. In addition, we analyze the stability for reactive cooperators against the invasion by a strategy other than unconditional defectors. Moreover, we also analyze the deterministic model in which unconditional cooperators, unconditional defectors, and the reactive strategy at the same time.

Impact of migration on the multi-strategy selection in finite group-structured populations

For large quantities of spatial models, the multi-strategy selection under weak selection is the sum of two competition terms: the pairwise competition and the competition of multiple strategies with equal frequency. Two parameters σ₁ and σ₂ quantify the dependence of the multi-strategy selection on these two terms, respectively. Unlike previous studies, we here do not require large populations for calculating σ₁ and σ₂, and perform the first quantitative analysis of the effect of migration on them in group-structured populations of any finite sizes. The Moran and the Wright-Fisher process have the following common findings. Compared with well-mixed populations, migration causes σ₁ to change with the mutation probability from a decreasing curve to an inverted U-shaped curve and maintains the increase of σ₂. Migration (probability and range) leads to a significant change of σ₁ but a negligible one of σ₂. The way that migration changes σ₁ is qualitatively similar to its influence on the single parameter characterizing the two-strategy selection. The Moran process is more effective in increasing σ₁ for most migration probabilities and the Wright-Fisher process is always more effective in increasing σ₂. Finally, our findings are used to study the evolution of cooperation under direct reciprocity.

Ordering structured populations in multiplayer cooperation games

Spatial structure greatly affects the evolution of cooperation. While in two-player games the condition for cooperation to evolve depends on a single structure coefficient, in multiplayer games the condition might depend on several structure coefficients, making it difficult to compare different population structures. We propose a solution to this issue by introducing two simple ways of ordering population structures: the containment order and the volume order. If population structure is greater than population structure in the containment or the volume order, then can be considered a stronger promoter of cooperation. We provide conditions for establishing the containment order, give general results on the volume order, and illustrate our theory by comparing different models of spatial games and associated update rules. Our results hold for a large class of population structures and can be easily applied to specific cases once the structure coefficients have been calculated or estimated.

Unified and simple understanding for the evolution of conditional cooperators

Cooperation is a mysterious phenomenon which is observed in this world. The potential explanation is a repeated interaction. Cooperation is established if individuals meet the same opponent repeatedly and cooperate conditionally. Previous studies have analyzed the following four as characters of conditional cooperators mainly. (i) niceness (i.e., when a conditional cooperator meets an opponent in the first place, he (she) cooperates or defects), (ii) optimism (when a conditional cooperator meets an opponent in the past, but he (she) did not get access to information about the opponent's behavior in the previous round, he (she) cooperates or defects), (iii) generosity (even when a conditional cooperator knows that an opponent defected in the previous round, he (she) cooperates or defects) and (iv) retaliation (a conditional cooperator cooperates with a cooperator with a higher probability than with a defector). Previous works deal with these four characters mainly. However, these four characters basically have been regarded as distinct topics and unified understanding has not been done fully. Here we, by studying the iterated prisoner's dilemma game (in particular, additive games) and using evolutionarily stable strategy (ESS) analysis, find that when retaliation is large, the condition under which conditional cooperators are stable against the invasion by an unconditional defector is loose, while none of "niceness", "optimism", and "generosity" makes impact on the condition under which conditional cooperators are stable against an invasion by an unconditional defector. Furthermore, we show that we can understand "niceness", "optimism", and "generosity" uniformly by using one parameter indicating "cooperative", and when the conditional cooperators have large "retaliation" enough to resist an invasion by an unconditional defector, natural selection favors more "cooperative" conditional cooperators to invade the resident conditional cooperative strategy. Moreover, we show that these results are robust even when taking the existence of mistakes in behavior into consideration.

Evolutionary Games of Multiplayer Cooperation on Graphs

There has been much interest in studying evolutionary games in structured populations, often modeled as graphs. However, most analytical results so far have only been obtained for two-player or linear games, while the study of more complex multiplayer games has been usually tackled by computer simulations. Here we investigate evolutionary multiplayer games on graphs updated with a Moran death-Birth process. For cycles, we obtain an exact analytical condition for cooperation to be favored by natural selection, given in terms of the payoffs of the game and a set of structure coefficients. For regular graphs of degree three and larger, we estimate this condition using a combination of pair approximation and diffusion approximation. For a large class of cooperation games, our approximations suggest that graph-structured populations are stronger promoters of cooperation than populations lacking spatial structure. Computer simulations validate our analytical approximations for random regular graphs and cycles, but show systematic differences for graphs with many loops such as lattices. In particular, our simulation results show that these kinds of graphs can even lead to more stringent conditions for the evolution of cooperation than well-mixed populations. Overall, we provide evidence suggesting that the complexity arising from many-player interactions and spatial structure can be captured by pair approximation in the case of random graphs, but that it need to be handled with care for graphs with high clustering.

Cooperation can be defined as the act of providing fitness benefits to other individuals, often at a personal cost. When interactions occur mainly with neighbors, assortment of strategies can favor cooperation but local competition can undermine it. Previous research has shown that a single coefficient can capture this trade-off when cooperative interactions take place between two players. More complicated, but also more realistic, models of cooperative interactions involving multiple players instead require several such coefficients, making it difficult to assess the effects of population structure. Here, we obtain analytical approximations for the coefficients of multiplayer games in graph-structured populations. Computer simulations show that, for particular instances of multiplayer games, these approximate coefficients predict the condition for cooperation to be promoted in random graphs well, but fail to do so in graphs with more structure, such as lattices. Our work extends and generalizes established results on the evolution of cooperation on graphs, but also highlights the importance of explicitly taking into account higher-order statistical associations in order to assess the evolutionary dynamics of cooperation in spatially structured populations.

Structural symmetry in evolutionary games

In evolutionary game theory, an important measure of a mutant trait (strategy) is its ability to invade and take over an otherwise-monomorphic population. Typically, one quantifies the success of a mutant strategy via the probability that a randomly occurring mutant will fixate in the population. However, in a structured population, this fixation probability may depend on where the mutant arises. Moreover, the fixation probability is just one quantity by which one can measure the success of a mutant; fixation time, for instance, is another. We define a notion of homogeneity for evolutionary games that captures what it means for two single-mutant states, i.e. two configurations of a single mutant in an otherwise-monomorphic population, to be 'evolutionarily equivalent' in the sense that all measures of evolutionary success are the same for both configurations. Using asymmetric games, we argue that the term 'homogeneous' should apply to the evolutionary process as a whole rather than to just the population structure. For evolutionary matrix games in graph-structured populations, we give precise conditions under which the resulting process is homogeneous. Finally, we show that asymmetric matrix games can be reduced to symmetric games if the population structure possesses a sufficient degree of symmetry.