1
|
Brewster DA, Nowak MA, Tkadlec J. Fixation times on directed graphs. PLoS Comput Biol 2024; 20:e1012299. [PMID: 39024375 PMCID: PMC11288448 DOI: 10.1371/journal.pcbi.1012299] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/12/2024] [Revised: 07/30/2024] [Accepted: 07/04/2024] [Indexed: 07/20/2024] Open
Abstract
Computing the rate of evolution in spatially structured populations is difficult. A key quantity is the fixation time of a single mutant with relative reproduction rate r which invades a population of residents. We say that the fixation time is "fast" if it is at most a polynomial function in terms of the population size N. Here we study fixation times of advantageous mutants (r > 1) and neutral mutants (r = 1) on directed graphs, which are those graphs that have at least some one-way connections. We obtain three main results. First, we prove that for any directed graph the fixation time is fast, provided that r is sufficiently large. Second, we construct an efficient algorithm that gives an upper bound for the fixation time for any graph and any r ≥ 1. Third, we identify a broad class of directed graphs with fast fixation times for any r ≥ 1. This class includes previously studied amplifiers of selection, such as Superstars and Metafunnels. We also show that on some graphs the fixation time is not a monotonically declining function of r; in particular, neutral fixation can occur faster than fixation for small selective advantages.
Collapse
Affiliation(s)
- David A. Brewster
- John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, Massachusetts, United States of America
| | - Martin A. Nowak
- Department of Mathematics, Harvard University, Cambridge, Massachusetts, United States of America
- Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, Massachusetts, United States of America
| | - Josef Tkadlec
- Department of Mathematics, Harvard University, Cambridge, Massachusetts, United States of America
- Computer Science Institute, Charles University, Prague, Czech Republic
| |
Collapse
|
2
|
Wang C, Perc M, Szolnoki A. Evolutionary dynamics of any multiplayer game on regular graphs. Nat Commun 2024; 15:5349. [PMID: 38914550 PMCID: PMC11196707 DOI: 10.1038/s41467-024-49505-5] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/23/2023] [Accepted: 06/05/2024] [Indexed: 06/26/2024] Open
Abstract
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.
Collapse
Affiliation(s)
- Chaoqian Wang
- Department of Computational and Data Sciences, George Mason University, Fairfax, VA, 22030, USA.
| | - Matjaž Perc
- Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška cesta 160, 2000, Maribor, Slovenia
- Community Healthcare Center Dr. Adolf Drolc Maribor, Vošnjakova ulica 2, 2000, Maribor, Slovenia
- Complexity Science Hub Vienna, Josefstädterstraße 39, 1080, Vienna, Austria
- Department of Physics, Kyung Hee University, 26 Kyungheedae-ro, Dongdaemun-gu, Seoul, Republic of Korea
| | - Attila Szolnoki
- Institute of Technical Physics and Materials Science, Centre for Energy Research, P.O. Box 49, H-1525, Budapest, Hungary
| |
Collapse
|
3
|
Wang C, Sun C. Zealous cooperation does not always promote cooperation in public goods games. CHAOS (WOODBURY, N.Y.) 2023; 33:2894476. [PMID: 37276560 DOI: 10.1063/5.0138258] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/09/2022] [Accepted: 05/22/2023] [Indexed: 06/07/2023]
Abstract
There is a conventional belief that prosocial behaviors cannot arise through selfish human nature, because defection always exploits cooperation to achieve a higher payoff at an individual level. Unyieldingly, some people hope to move society to cooperation through their zealous cooperation, regardless of payoffs. From the perspective of spatial evolutionary games, however, such zealous behavior is unnecessary because cooperation can emerge from selfish human nature by aggregating in evolution. Yet, to what extent can zealous cooperation induce others to cooperate? We assume a fraction of zealous agents in spatial public goods games who always cooperate. The results show that a moderate proportion of these zealous cooperators can diminish the cooperation level in the system, and cooperation is only promoted when zealots are many. Regarding spatial behaviors, the areas of zealous cooperation in a medium density can prevent evolutionary cooperation from passing through and aggregating. The phenomenon of zealous cooperation impeding cooperation becomes more pronounced when agents become less random and more selfish. This is because dotted zealous cooperation provides significant payoffs to neighboring defection, making them more solid in fitness. In this way, we also find that when zealous cooperators have low productivity, the neighbors receive fewer benefits by exploitation, thus allowing cooperation to spread. We also study replicator dynamics in unstructured populations where zealous cooperation always promotes cooperation, agreeing that zealous cooperation hindering cooperation is a spatial effect.
Collapse
Affiliation(s)
- Chaoqian Wang
- Department of Computational and Data Sciences, George Mason University, Fairfax, Virginia 22030, USA
| | - Chengbin Sun
- School of Economics and Management, Dalian University of Technology, Dalian 116024, China
| |
Collapse
|
4
|
Wang S, Chen X, Xiao Z, Szolnoki A, Vasconcelos VV. Optimization of institutional incentives for cooperation in structured populations. J R Soc Interface 2023; 20:20220653. [PMID: 36722070 PMCID: PMC9890111 DOI: 10.1098/rsif.2022.0653] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/05/2022] [Accepted: 01/03/2023] [Indexed: 02/02/2023] Open
Abstract
The application of incentives, such as reward and punishment, is a frequently applied way for promoting cooperation among interacting individuals in structured populations. However, how to properly use the incentives is still a challenging problem for incentive-providing institutions. In particular, since the implementation of incentive is costly, to explore the optimal incentive protocol, which ensures the desired collective goal at a minimal cost, is worthy of study. In this work, we consider the positive and negative incentives for a structured population of individuals whose conflicting interactions are characterized by a Prisoner's Dilemma game. We establish an index function for quantifying the cumulative cost during the process of incentive implementation, and theoretically derive the optimal positive and negative incentive protocols for cooperation on regular networks. We find that both types of optimal incentive protocols are identical and time-invariant. Moreover, we compare the optimal rewarding and punishing schemes concerning implementation cost and provide a rigorous basis for the usage of incentives in the game-theoretical framework. We further perform computer simulations to support our theoretical results and explore their robustness for different types of population structures, including regular, random, small-world and scale-free networks.
Collapse
Affiliation(s)
- Shengxian Wang
- School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, People’s Republic of China
- Faculty of Science and Engineering, University of Groningen, Groningen 9747 AG, The Netherlands
| | - Xiaojie Chen
- School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, People’s Republic of China
| | - Zhilong Xiao
- School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, People’s Republic of China
- School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, People’s Republic of China
| | - Attila Szolnoki
- Institute of Technical Physics and Materials Science, Centre for Energy Research, P.O. Box 49, Budapest 1525, Hungary
| | - Vítor V. Vasconcelos
- Computational Science Lab, Informatics Institute, University of Amsterdam, Amsterdam 1098XH, The Netherlands
- Institute for Advanced Study, University of Amsterdam, Amsterdam 1012 GC, The Netherlands
| |
Collapse
|
5
|
Abstract
In order to accommodate the empirical fact that population structures are rarely simple, modern studies of evolutionary dynamics allow for complicated and highly heterogeneous spatial structures. As a result, one of the most difficult obstacles lies in making analytical deductions, either qualitative or quantitative, about the long-term outcomes of evolution. The "structure-coefficient" theorem is a well-known approach to this problem for mutation-selection processes under weak selection, but a general method of evaluating the terms it comprises is lacking. Here, we provide such a method for populations of fixed (but arbitrary) size and structure, using easily interpretable demographic measures. This method encompasses a large family of evolutionary update mechanisms and extends the theorem to allow for asymmetric contests to provide a better understanding of the mutation-selection balance under more realistic circumstances. We apply the method to study social goods produced and distributed among individuals in spatially heterogeneous populations, where asymmetric interactions emerge naturally and the outcome of selection varies dramatically, depending on the nature of the social good, the spatial topology, and the frequency with which mutations arise.
Collapse
|
6
|
Su Q, McAvoy A, Mori Y, Plotkin JB. Evolution of prosocial behaviours in multilayer populations. Nat Hum Behav 2022; 6:338-348. [PMID: 34980900 DOI: 10.1038/s41562-021-01241-2] [Citation(s) in RCA: 5] [Impact Index Per Article: 2.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/29/2020] [Accepted: 10/22/2021] [Indexed: 01/16/2023]
Abstract
Human societies include diverse social relationships. Friends, family, business colleagues and online contacts can all contribute to one's social life. Individuals may behave differently in different domains, but success in one domain may engender success in another. Here, we study this problem using multilayer networks to model multiple domains of social interactions, in which individuals experience different environments and may express different behaviours. We provide a mathematical analysis and find that coupling between layers tends to promote prosocial behaviour. Even if prosociality is disfavoured in each layer alone, multilayer coupling can promote its proliferation in all layers simultaneously. We apply this analysis to six real-world multilayer networks, ranging from the socio-emotional and professional relationships in a Zambian community, to the online and offline relationships within an academic university. We discuss the implications of our results, which suggest that small modifications to interactions in one domain may catalyse prosociality in a different domain.
Collapse
Affiliation(s)
- Qi Su
- Department of Biology, University of Pennsylvania, PA, USA. .,Center for Mathematical Biology, University of Pennsylvania, PA, USA. .,Department of Mathematics, University of Pennsylvania, PA, USA.
| | - Alex McAvoy
- Center for Mathematical Biology, University of Pennsylvania, PA, USA. .,Department of Mathematics, University of Pennsylvania, PA, USA.
| | - Yoichiro Mori
- Department of Biology, University of Pennsylvania, PA, USA.,Center for Mathematical Biology, University of Pennsylvania, PA, USA.,Department of Mathematics, University of Pennsylvania, PA, USA
| | - Joshua B Plotkin
- Department of Biology, University of Pennsylvania, PA, USA.,Center for Mathematical Biology, University of Pennsylvania, PA, USA.,Department of Mathematics, University of Pennsylvania, PA, USA
| |
Collapse
|
7
|
McAvoy A, Rao A, Hauert C. Intriguing effects of selection intensity on the evolution of prosocial behaviors. PLoS Comput Biol 2021; 17:e1009611. [PMID: 34780464 PMCID: PMC8629389 DOI: 10.1371/journal.pcbi.1009611] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/04/2021] [Revised: 11/29/2021] [Accepted: 11/03/2021] [Indexed: 12/05/2022] Open
Abstract
In many models of evolving populations, genetic drift has an outsized role relative to natural selection, or vice versa. While there are many scenarios in which one of these two assumptions is reasonable, intermediate balances between these forces are also biologically relevant. In this study, we consider some natural axioms for modeling intermediate selection intensities, and we explore how to quantify the long-term evolutionary dynamics of such a process. To illustrate the sensitivity of evolutionary dynamics to drift and selection, we show that there can be a “sweet spot” for the balance of these two forces, with sufficient noise for rare mutants to become established and sufficient selection to spread. This balance allows prosocial traits to evolve in evolutionary models that were previously thought to be unconducive to the emergence and spread of altruistic behaviors. Furthermore, the effects of selection intensity on long-run evolutionary outcomes in these settings, such as when there is global competition for reproduction, can be highly non-monotonic. Although intermediate selection intensities (neither weak nor strong) are notoriously difficult to study analytically, they are often biologically relevant; and the results we report suggest that they can elicit novel and rich dynamics in the evolution of prosocial behaviors. Theoretical models of populations have been useful for assessing when and how traits spread, in large part because they are simple. Rather than being used to reproduce empirical data, these idealized models involve relatively few parameters and are utilized to gain a qualitative understanding of what promotes or suppresses a trait. For prosocial traits, which entail a cost to self to help another, one thing that mathematical models often suggest is that competition to reproduce must be localized, meaning an individual must be fitter than just a small subset of the population in order to produce an offspring. We show here that this finding is not robust. Such traits can indeed proliferate when there is global competition for reproduction, which we demonstrate by increasing the degree to which payoffs from games affect birth rates. Since this kind of “stronger selection” has also been observed empirically, we discuss how it is incorporated into theoretical models more broadly.
Collapse
Affiliation(s)
- Alex McAvoy
- Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania, United States of America
- Center for Mathematical Biology, University of Pennsylvania, Philadelphia, Pennsylvania, United States of America
- * E-mail:
| | - Andrew Rao
- Department of Economics, Harvard University, Cambridge, Massachusetts, United States of America
| | - Christoph Hauert
- Department of Mathematics, University of British Columbia, Vancouver, British Columbia, Canada
| |
Collapse
|
8
|
Liang H, Cui Y, Ren X, Wang X. Almost sure exponential stability of two-strategy evolutionary games with multiplicative noise. Inf Sci (N Y) 2021. [DOI: 10.1016/j.ins.2021.08.091] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/20/2022]
|
9
|
Hauert C, Doebeli M. Spatial social dilemmas promote diversity. Proc Natl Acad Sci U S A 2021; 118:e2105252118. [PMID: 34649992 PMCID: PMC8594579 DOI: 10.1073/pnas.2105252118] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Accepted: 07/19/2021] [Indexed: 11/18/2022] Open
Abstract
Cooperative investments in social dilemmas can spontaneously diversify into stably coexisting high and low contributors in well-mixed populations. Here we extend the analysis to emerging diversity in (spatially) structured populations. Using pair approximation, we derive analytical expressions for the invasion fitness of rare mutants in structured populations, which then yields a spatial adaptive dynamics framework. This allows us to predict changes arising from population structures in terms of existence and location of singular strategies, as well as their convergence and evolutionary stability as compared to well-mixed populations. Based on spatial adaptive dynamics and extensive individual-based simulations, we find that spatial structure has significant and varied impacts on evolutionary diversification in continuous social dilemmas. More specifically, spatial adaptive dynamics suggests that spontaneous diversification through evolutionary branching is suppressed, but simulations show that spatial dimensions offer new modes of diversification that are driven by an interplay of finite-size mutations and population structures. Even though spatial adaptive dynamics is unable to capture these new modes, they can still be understood based on an invasion analysis. In particular, population structures alter invasion fitness and can open up new regions in trait space where mutants can invade, but that may not be accessible to small mutational steps. Instead, stochastically appearing larger mutations or sequences of smaller mutations in a particular direction are required to bridge regions of unfavorable traits. The net effect is that spatial structure tends to promote diversification, especially when selection is strong.
Collapse
Affiliation(s)
- Christoph Hauert
- Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada;
- Department of Zoology, University of British Columbia, Vancouver, BC V6T 1Z4, Canada
| | - Michael Doebeli
- Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada
- Department of Zoology, University of British Columbia, Vancouver, BC V6T 1Z4, Canada
| |
Collapse
|
10
|
Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Fast and strong amplifiers of natural selection. Nat Commun 2021; 12:4009. [PMID: 34188036 PMCID: PMC8242091 DOI: 10.1038/s41467-021-24271-w] [Citation(s) in RCA: 10] [Impact Index Per Article: 3.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/01/2021] [Accepted: 06/10/2021] [Indexed: 02/06/2023] Open
Abstract
Selection and random drift determine the probability that novel mutations fixate in a population. Population structure is known to affect the dynamics of the evolutionary process. Amplifiers of selection are population structures that increase the fixation probability of beneficial mutants compared to well-mixed populations. Over the past 15 years, extensive research has produced remarkable structures called strong amplifiers which guarantee that every beneficial mutation fixates with high probability. But strong amplification has come at the cost of considerably delaying the fixation event, which can slow down the overall rate of evolution. However, the precise relationship between fixation probability and time has remained elusive. Here we characterize the slowdown effect of strong amplification. First, we prove that all strong amplifiers must delay the fixation event at least to some extent. Second, we construct strong amplifiers that delay the fixation event only marginally as compared to the well-mixed populations. Our results thus establish a tight relationship between fixation probability and time: Strong amplification always comes at a cost of a slowdown, but more than a marginal slowdown is not needed.
Collapse
Affiliation(s)
- Josef Tkadlec
- grid.38142.3c000000041936754XDepartment of Mathematics, Harvard University, Cambridge, MA 02138 USA
| | - Andreas Pavlogiannis
- grid.7048.b0000 0001 1956 2722Department of Computer Science, Aarhus University, Aabogade 34, 8200 Aarhus, Denmark
| | - Krishnendu Chatterjee
- grid.33565.360000000404312247Institute of Science and Technology Austria, Am Campus 1, 3400 Klosterneuburg, Austria
| | - Martin A. Nowak
- grid.38142.3c000000041936754XDepartment of Mathematics, Harvard University, Cambridge, MA 02138 USA
| |
Collapse
|
11
|
Aspiration dynamics generate robust predictions in heterogeneous populations. Nat Commun 2021; 12:3250. [PMID: 34059670 PMCID: PMC8166829 DOI: 10.1038/s41467-021-23548-4] [Citation(s) in RCA: 9] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/07/2020] [Accepted: 05/05/2021] [Indexed: 12/03/2022] Open
Abstract
Update rules, which describe how individuals adjust their behavior over time, affect the outcome of social interactions. Theoretical studies have shown that evolutionary outcomes are sensitive to model details when update rules are imitation-based but are robust when update rules are self-evaluation based. However, studies of self-evaluation based rules have focused on homogeneous population structures where each individual has the same number of neighbors. Here, we consider heterogeneous population structures represented by weighted networks. Under weak selection, we analytically derive the condition for strategy success, which coincides with the classical condition of risk-dominance. This condition holds for all weighted networks and distributions of aspiration levels, and for individualized ways of self-evaluation. Our findings recover previous results as special cases and demonstrate the universality of the robustness property under self-evaluation based rules. Our work thus sheds light on the intrinsic difference between evolutionary dynamics under self-evaluation based and imitation-based update rules. Social interaction outcomes can depend on the type of information individuals possess and how it is used in decision-making. Here, Zhou et al. find that self-evaluation based decision-making rules lead to evolutionary outcomes that are robust to different population structures and ways of self-evaluation.
Collapse
|
12
|
Huang F, Cao M, Wang L. Learning enables adaptation in cooperation for multi-player stochastic games. J R Soc Interface 2020; 17:20200639. [PMID: 33202177 DOI: 10.1098/rsif.2020.0639] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/08/2023] Open
Abstract
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.
Collapse
Affiliation(s)
- Feng Huang
- Center for Systems and Control, College of Engineering, Peking University, Beijing 100871, People's Republic of China.,Center for Data Science and System Complexity, Faculty of Science and Engineering, University of Groningen, Groningen 9747 AG, The Netherlands
| | - Ming Cao
- Center for Data Science and System Complexity, Faculty of Science and Engineering, University of Groningen, Groningen 9747 AG, The Netherlands
| | - Long Wang
- Center for Systems and Control, College of Engineering, Peking University, Beijing 100871, People's Republic of China
| |
Collapse
|
13
|
Social goods dilemmas in heterogeneous societies. Nat Hum Behav 2020; 4:819-831. [DOI: 10.1038/s41562-020-0881-2] [Citation(s) in RCA: 23] [Impact Index Per Article: 5.8] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/18/2019] [Accepted: 04/07/2020] [Indexed: 12/16/2022]
|
14
|
Abstract
Population structure affects the outcome of natural selection. These effects can be modeled using evolutionary games on graphs. Recently, conditions were derived for a trait to be favored under weak selection, on any weighted graph, in terms of coalescence times of random walks. Here we consider isothermal graphs, which have the same total edge weight at each node. The conditions for success on isothermal graphs take a simple form, in which the effects of graph structure are captured in the ‘effective degree’—a measure of the effective number of neighbors per individual. For two update rules (death-Birth and birth-Death), cooperative behavior is favored on a large isothermal graph if the benefit-to-cost ratio exceeds the effective degree. For two other update rules (Birth-death and Death-birth), cooperation is never favored. We relate the effective degree of a graph to its spectral gap, thereby linking evolutionary dynamics to the theory of expander graphs. Surprisingly, we find graphs of infinite average degree that nonetheless provide strong support for cooperation. The spatial structure of a population is often critical for the evolution of cooperation. Here, Allen and colleagues show that when spatial structure is represented by an isothermal graph, the effective number of neighbors per individual determines whether or not cooperation can evolve.
Collapse
|
15
|
Hindersin L, Wu B, Traulsen A, García J. Computation and Simulation of Evolutionary Game Dynamics in Finite Populations. Sci Rep 2019; 9:6946. [PMID: 31061385 PMCID: PMC6502801 DOI: 10.1038/s41598-019-43102-z] [Citation(s) in RCA: 24] [Impact Index Per Article: 4.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/22/2018] [Accepted: 04/11/2019] [Indexed: 11/23/2022] Open
Abstract
The study of evolutionary dynamics increasingly relies on computational methods, as more and more cases outside the range of analytical tractability are explored. The computational methods for simulation and numerical approximation of the relevant quantities are diverging without being compared for accuracy and performance. We thoroughly investigate these algorithms in order to propose a reliable standard. For expositional clarity we focus on symmetric 2 × 2 games leading to one-dimensional processes, noting that extensions can be straightforward and lessons will often carry over to more complex cases. We provide time-complexity analysis and systematically compare three families of methods to compute fixation probabilities, fixation times and long-term stationary distributions for the popular Moran process. We provide efficient implementations that substantially improve wall times over naive or immediate implementations. Implications are also discussed for the Wright-Fisher process, as well as structured populations and multiple types.
Collapse
Affiliation(s)
- Laura Hindersin
- Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, Plön, Germany
| | - Bin Wu
- School of Science, Beijing University of Posts and Telecommunications, Beijing, China
| | - Arne Traulsen
- Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, Plön, Germany.
| | - Julian García
- Faculty of Information Technology, Monash University, Melbourne, Australia
| |
Collapse
|
16
|
Fotouhi B, Momeni N, Allen B, Nowak MA. Evolution of cooperation on large networks with community structure. J R Soc Interface 2019; 16:20180677. [PMID: 30862280 PMCID: PMC6451403 DOI: 10.1098/rsif.2018.0677] [Citation(s) in RCA: 63] [Impact Index Per Article: 12.6] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/07/2018] [Accepted: 02/18/2019] [Indexed: 11/12/2022] Open
Abstract
Cooperation is a major factor in the evolution of human societies. The structure of social networks, which affects the dynamics of cooperation and other interpersonal phenomena, have common structural signatures. One of these signatures is the tendency to organize as groups. This tendency gives rise to networks with community structure, which are composed of distinct modules. In this paper, we study analytically the evolutionary game dynamics on large modular networks in the limit of weak selection. We obtain novel analytical conditions such that natural selection favours cooperation over defection. We calculate the transition point for each community to favour cooperation. We find that a critical inter-community link creation probability exists for given group density, such that the overall network supports cooperation even if individual communities inhibit it. As a byproduct, we present solutions for the critical benefit-to-cost ratio which perform with remarkable accuracy for diverse generative network models, including those with community structure and heavy-tailed degree distributions. We also demonstrate the generalizability of the results to arbitrary two-player games.
Collapse
Affiliation(s)
- Babak Fotouhi
- Program for Evolutionary Dynamics, Harvard University, Cambridge, MA, USA
- Institute for Quantitative Social Sciences, Harvard University, Cambridge, MA, USA
| | - Naghmeh Momeni
- Program for Evolutionary Dynamics, Harvard University, Cambridge, MA, USA
- Massachusetts Institute of Technology (MIT) - Sloan School of Management, Cambridge, MA, USA
| | - Benjamin Allen
- Program for Evolutionary Dynamics, Harvard University, Cambridge, MA, USA
- Center for Mathematical Sciences and Applications, Harvard University, Cambridge, MA, USA
- Department of Mathematics, Emmanuel College, Boston, MA, USA
| | - Martin A. Nowak
- Program for Evolutionary Dynamics, Harvard University, Cambridge, MA, USA
- Department of Mathematics, Harvard University, Cambridge, MA, USA
- Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, MA, USA
| |
Collapse
|
17
|
Richter H. Properties of network structures, structure coefficients, and benefit-to-cost ratios. Biosystems 2019; 180:88-100. [PMID: 30914346 DOI: 10.1016/j.biosystems.2019.03.005] [Citation(s) in RCA: 10] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/17/2018] [Revised: 02/24/2019] [Accepted: 03/21/2019] [Indexed: 12/31/2022]
Abstract
In structured populations the spatial arrangement of cooperators and defectors on the interaction graph together with the structure of the graph itself determines the game dynamics and particularly whether or not fixation of cooperation (or defection) is favored. For networks described by regular graphs and for a single cooperator (and a single defector) the question of fixation can be addressed by a single parameter, the structure coefficient. This quantity is invariant with respect to the location of the cooperator on the graph and also does not vary over different networks. We may therefore consider it to be generic for regular graphs and call it the generic structure coefficient. For two and more cooperators (or several defectors) fixation properties can also be assigned by structure coefficients. These structure coefficients, however, depend on the arrangement of cooperators and defectors which we may interpret as a configuration of the game. Moreover, the coefficients are specific for a given interaction network modeled as a regular graph, which is why we may call them specific structure coefficients. In this paper, we study how specific structure coefficients vary over interaction graphs and analyze how spectral properties of interaction networks relate to specific structure coefficients. We also discuss implications for the benefit-to-cost ratios of donation games.
Collapse
Affiliation(s)
- Hendrik Richter
- HTWK Leipzig University of Applied Sciences, Faculty of Electrical Engineering and Information Technology, Postfach 301166, D-04251 Leipzig, Germany.
| |
Collapse
|
18
|
Chen YT. Wright–Fisher diffusions in stochastic spatial evolutionary games with death–birth updating. ANN APPL PROBAB 2018. [DOI: 10.1214/18-aap1390] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/19/2022]
|
19
|
Allen B, McAvoy A. A mathematical formalism for natural selection with arbitrary spatial and genetic structure. J Math Biol 2018; 78:1147-1210. [PMID: 30430219 DOI: 10.1007/s00285-018-1305-z] [Citation(s) in RCA: 16] [Impact Index Per Article: 2.7] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/11/2018] [Revised: 10/29/2018] [Indexed: 12/22/2022]
Abstract
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.
Collapse
Affiliation(s)
- Benjamin Allen
- Department of Mathematics, Emmanuel College, Boston, MA, 02115, USA. .,Program for Evolutionary Dynamics, Harvard University, Cambridge, MA, 02138, USA.
| | - Alex McAvoy
- Program for Evolutionary Dynamics, Harvard University, Cambridge, MA, 02138, USA
| |
Collapse
|
20
|
Abstract
Contrary to the assumption that web browsers are designed to support the user, an examination of a 900,000 distinct PCs shows that web browsers comprise a complex ecosystem with millions of addons collaborating and competing with each other. It is possible for addons to "sneak in" through third party installations or to get "kicked out" by their competitors without user involvement. This study examines that ecosystem quantitatively by constructing a large-scale graph with nodes corresponding to users, addons, and words (terms) that describe addon functionality. Analyzing addon interactions at user level using the Personalized PageRank (PPR) random walk measure shows that the graph demonstrates ecological resilience. Adapting the PPR model to analyzing the browser ecosystem at the level of addon manufacturer, the study shows that some addon companies are in symbiosis and others clash with each other as shown by analyzing the behavior of 18 prominent addon manufacturers. Results may herald insight on how other evolving internet ecosystems may behave, and suggest a methodology for measuring this behavior. Specifically, applying such a methodology could transform the addon market.
Collapse
Affiliation(s)
- Sela Ferdman
- Department of Computer Science, University of Haifa, Haifa, Israel
| | - Einat Minkov
- Department of Information Systems, University of Haifa, Haifa, Israel
| | - Ron Bekkerman
- Department of Information and Knowledge Management, University of Haifa, Haifa, Israel
- * E-mail:
| | - David Gefen
- LeBow College of Business, Drexel University, Philadelphia, PA, United States of America
| |
Collapse
|
21
|
Allen B, Lippner G, Chen YT, Fotouhi B, Momeni N, Yau ST, Nowak MA. Evolutionary dynamics on any population structure. Nature 2017; 544:227-230. [PMID: 28355181 DOI: 10.1038/nature21723] [Citation(s) in RCA: 184] [Impact Index Per Article: 26.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/31/2016] [Accepted: 02/23/2017] [Indexed: 11/10/2022]
Abstract
Evolution occurs in populations of reproducing individuals. The structure of a population can affect which traits evolve. Understanding evolutionary game dynamics in structured populations remains difficult. Mathematical results are known for special structures in which all individuals have the same number of neighbours. The general case, in which the number of neighbours can vary, has remained open. For arbitrary selection intensity, the problem is in a computational complexity class that suggests there is no efficient algorithm. Whether a simple solution for weak selection exists has remained unanswered. Here we provide a solution for weak selection that applies to any graph or network. Our method relies on calculating the coalescence times of random walks. We evaluate large numbers of diverse population structures for their propensity to favour cooperation. We study how small changes in population structure-graph surgery-affect evolutionary outcomes. We find that cooperation flourishes most in societies that are based on strong pairwise ties.
Collapse
Affiliation(s)
- Benjamin Allen
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, USA.,Program for Evolutionary Dynamics, Harvard University, Cambridge, Massachusetts, USA.,Center for Mathematical Sciences and Applications, Harvard University, Cambridge, Massachusetts, USA
| | - Gabor Lippner
- Center for Mathematical Sciences and Applications, Harvard University, Cambridge, Massachusetts, USA.,Department of Mathematics, Northeastern University, Boston, Massachusetts, USA
| | - Yu-Ting Chen
- Program for Evolutionary Dynamics, Harvard University, Cambridge, Massachusetts, USA.,Center for Mathematical Sciences and Applications, Harvard University, Cambridge, Massachusetts, USA.,Department of Mathematics, University of Tennessee, Knoxville, Tennessee, USA
| | - Babak Fotouhi
- Program for Evolutionary Dynamics, Harvard University, Cambridge, Massachusetts, USA.,Institute for Quantitative Social Sciences, Harvard University, Cambridge, Massachusetts, USA
| | - Naghmeh Momeni
- Program for Evolutionary Dynamics, Harvard University, Cambridge, Massachusetts, USA.,Department of Electrical and Computer Engineering, McGill University, Montreal, Canada
| | - Shing-Tung Yau
- Center for Mathematical Sciences and Applications, Harvard University, Cambridge, Massachusetts, USA.,Department of Mathematics, Harvard University, Cambridge, Massachusetts, USA
| | - Martin A Nowak
- Program for Evolutionary Dynamics, Harvard University, Cambridge, Massachusetts, USA.,Department of Mathematics, Harvard University, Cambridge, Massachusetts, USA.,Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, Massachusetts, USA
| |
Collapse
|
22
|
Sample C, Allen B. The limits of weak selection and large population size in evolutionary game theory. J Math Biol 2017; 75:1285-1317. [DOI: 10.1007/s00285-017-1119-4] [Citation(s) in RCA: 19] [Impact Index Per Article: 2.7] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/24/2016] [Revised: 02/16/2017] [Indexed: 11/29/2022]
|
23
|
Wang X, Zhang L, Du X. The Effectiveness of Reward and Punishment in Spatial Social Games. INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE AND APPLICATIONS 2017. [DOI: 10.1142/s1469026817500079] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/18/2022]
Abstract
Punishment and reward are usually regarded as two potential mechanisms to explain the evolution of cooperation especially among multiple participators. However, the performance of these two scenarios in spatial environment needs to be discussed. To figure out this issue, we resort to the [Formula: see text]-player Iterated Snowdrift Dilemma (ISD) game and Iterated Prisoner’s Dilemma (IPD) game. More importantly, the evolution of punishment and reward in social network-structured populations has not been formally addressed. The numerical results show the equilibrium cooperation frequency can be influenced by cost-to-benefit ratio [Formula: see text], the punishment-to-benefit ratio [Formula: see text] and the reward-to-benefit ratio [Formula: see text]. And one intriguing observation is that under the same situation, the punishment is more effective than reward to the population. Then we further probe the effectiveness of neighborhood relationship to the cooperation, which is reflected by the random rewired probability [Formula: see text]. From the distribution of the four roles of the participator we can find that individuals can cooperate easily when they have close relationship. The results of this paper may be helpful to understand the cooperation in complex project or among industry–university–research cooperation project.
Collapse
Affiliation(s)
- Xiaoyang Wang
- Zhongshan Institute, University of Electronic Science and Technology of China, Zhongshan, Guangdong 528400, China
| | - Lei Zhang
- School of Physics and Engineering, Sun Yat-sen University, Guangzhou, Guangdong 510275, China
| | - Xiaorong Du
- School of Physics and Engineering, Sun Yat-sen University, Guangzhou, Guangdong 510275, China
| |
Collapse
|
24
|
Amplification on Undirected Population Structures: Comets Beat Stars. Sci Rep 2017; 7:82. [PMID: 28250441 PMCID: PMC5427850 DOI: 10.1038/s41598-017-00107-w] [Citation(s) in RCA: 25] [Impact Index Per Article: 3.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/17/2017] [Accepted: 02/06/2017] [Indexed: 11/08/2022] Open
Abstract
The fixation probability is the probability that a new mutant introduced in a homogeneous population eventually takes over the entire population. The fixation probability is a fundamental quantity of natural selection, and known to depend on the population structure. Amplifiers of natural selection are population structures which increase the fixation probability of advantageous mutants, as compared to the baseline case of well-mixed populations. In this work we focus on symmetric population structures represented as undirected graphs. In the regime of undirected graphs, the strongest amplifier known has been the Star graph, and the existence of undirected graphs with stronger amplification properties has remained open for over a decade. In this work we present the Comet and Comet-swarm families of undirected graphs. We show that for a range of fitness values of the mutants, the Comet and Comet-swarm graphs have fixation probability strictly larger than the fixation probability of the Star graph, for fixed population size and at the limit of large populations, respectively.
Collapse
|
25
|
Chen YT, McAvoy A, Nowak MA. Fixation Probabilities for Any Configuration of Two Strategies on Regular Graphs. Sci Rep 2016; 6:39181. [PMID: 28004806 PMCID: PMC5177945 DOI: 10.1038/srep39181] [Citation(s) in RCA: 13] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/16/2016] [Accepted: 11/18/2016] [Indexed: 11/08/2022] Open
Abstract
Population structure and spatial heterogeneity are integral components of evolutionary dynamics, in general, and of evolution of cooperation, in particular. Structure can promote the emergence of cooperation in some populations and suppress it in others. Here, we provide results for weak selection to favor cooperation on regular graphs for any configuration, meaning any arrangement of cooperators and defectors. Our results extend previous work on fixation probabilities of rare mutants. We find that for any configuration cooperation is never favored for birth-death (BD) updating. In contrast, for death-birth (DB) updating, we derive a simple, computationally tractable formula for weak selection to favor cooperation when starting from any configuration containing any number of cooperators. This formula elucidates two important features: (i) the takeover of cooperation can be enhanced by the strategic placement of cooperators and (ii) adding more cooperators to a configuration can sometimes suppress the evolution of cooperation. These findings give a formal account for how selection acts on all transient states that appear in evolutionary trajectories. They also inform the strategic design of initial states in social networks to maximally promote cooperation. We also derive general results that characterize the interaction of any two strategies, not only cooperation and defection.
Collapse
Affiliation(s)
- Yu-Ting Chen
- Program for Evolutionary Dynamics, Harvard University, Cambridge, MA 02138, USA
- Center of Mathematical Sciences and Applications, Harvard University, Cambridge, MA 02138, USA
- Department of Mathematics, University of Tennessee, Knoxville, TN 37996, USA
| | - Alex McAvoy
- Program for Evolutionary Dynamics, Harvard University, Cambridge, MA 02138, USA
- Department of Mathematics, University of British Columbia, 1984 Mathematics Road, Vancouver, BC, Canada V6T 1Z2
| | - Martin A. Nowak
- Program for Evolutionary Dynamics, Harvard University, Cambridge, MA 02138, USA
- Department of Mathematics, Harvard University, Cambridge, MA 02138, USA
- Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, MA 02138, USA
| |
Collapse
|