Evolving multiplayer networks: Modelling the evolution of cooperation in a mobile population

Karan Pattni; Mark Broom; Jan Rychtář

doi:10.3934/dcdsb.2018191

Article Contents

2018, Volume 23, Issue 5: 1975-2004. Doi: 10.3934/dcdsb.2018191

This issue Previous Article Dynamical systems associated with adjacency matrices Next Article On bounding exact models of epidemic spread on networks

Evolving multiplayer networks: Modelling the evolution of cooperation in a mobile population

1.
Department of Mathematics, City, University of London, 10 Northampton Square, London, EC1V 0HB, UK
2.
Department of Mathematics and Statistics, The University of North Carolina at Greensboro, Greensboro, NC 27412, USA

* Corresponding author: Karan Pattni (karan.pattni.1@city.ac.uk).
* Corresponding author: Karan Pattni (karan.pattni.1@city.ac.uk).

Received: January 31, 2017

Revised: April 30, 2017

Early access: May 2018

Published: May 2018

Abstract Full Text(HTML) Figure(14) / Table(3) Related Papers Cited by

Abstract

We consider a finite population of individuals that can move through a structured environment using our previously developed flexible evolutionary framework. In the current paper the behaviour of the individuals follows a Markov movement model where decisions about whether they should stay or leave depends upon the group of individuals they are with at present. The interaction between individuals is modelled using a public goods game. We demonstrate that cooperation can evolve when there is a cost associated with movement. Combining the movement cost with a larger population size has a positive effect on the evolution of cooperation. Moreover, increasing the exploration time, which is the amount of time an individual is allowed to explore its environment, also has a positive effect. Unusually, we find that the evolutionary dynamics used does not have a significant effect on these results.

Keywords:

Mathematics Subject Classification: 91A22, 60J10, 92D15.

Citation:

Full Text(HTML)

Figure 1. This plot shows the best response staying propensities for 1 type $C_i$ individual playing against $N-1$ type $C_j$ individuals. Parameter set 1 is used with $\lambda = 0.2$ and $i, j\in \{0.01, 0.02, \ldots, 0.99\}$. The intersection point of the plots gives the unique strategy which is a best response to itself, i.e. the unique cooperator resident Nash equilibrium staying propensity $\gamma_R$, which is somewhere between $0.3$ and $0.4$. This value is similar to the one obtained using the iterative method (see Figure 2). The values from the current figure are approximate only because of the jagged nature of the lines; these occur because of the very large number of simulations that would be necessary to obtain a smooth version (the figure uses 10000 simulations for each combination). The figure is used to illustrate the uniqueness of the solution only.

Download: Full-size image PowerPoint slide

Figure 2. These plots show the effect of movement cost on the evolution of cooperation using parameter set 1. The left (centre) plot shows the staying propensities $\delta_R = 0.99$ ($\gamma_R$) for resident defectors (cooperators) and $\gamma_M$ ($\delta_M$) for a mutant cooperator (defector) used to invade the resident population. In the right plot, we have the fixation probability of a mutant cooperator $C_{\gamma_M}$ (defector $D_{\delta_M}$) against $N-1$ resident defectors $D_{0.99}$ (cooperators $C_{\gamma_R}$).

Download: Full-size image PowerPoint slide

Figure 3. Plots created using parameter set 2. The exploration time $T$ has been decreased from 10 to 5.

Download: Full-size image PowerPoint slide

Figure 4. Plots created using parameter set 3. The exploration time $T$ has been increased from 10 to 25.

Download: Full-size image PowerPoint slide

Figure 5. Plots created using parameter set 4. The population size has been increased from 10 to 20.

Download: Full-size image PowerPoint slide

Figure 6. Plots have been created using parameter set 5. The plots here are against the reward to cost ratio $v/c$ such that $c = 0.04.$

Download: Full-size image PowerPoint slide

Figure 7. Plots have been created using parameter set 6. The plots here are against the reward to cost ratio $v/c$ such that $c = 0.09$.

Download: Full-size image PowerPoint slide

Figure 8. This plot shows the best response cooperator staying propensity (solid line, value shown on the x-axis) versus the range of defector staying propensities on the y-axis, and the best response defector staying propensity (dashed line, value shown on the y-axis) versus the range of cooperator staying propensities (on the x-axis) for $N/2$ cooperators and $N/2$ defectors. Parameter set 1 is used with $\lambda = 0.2$ and the staying propensities are chosen from the set $\{0.01, 0.02, \ldots, 0.99\}$. The best response staying propensities cross at one point only, which is thus the unique Nash equilibrium, where $\gamma\approx 0.7$ and $\delta\approx0.5$. These values are similar to those obtained using the iterative method described earlier (see Figure 9). As before, the values from the current figure are approximate only because of the jagged nature of the lines; the figure is used to illustrate the uniqueness of the solution only.

Download: Full-size image PowerPoint slide

Figure 9. These plots show the effect of movement cost $\lambda$ on the evolution of cooperation and are created using parameter set 1. The plot on the left shows the Nash equilibrium staying propensity $\gamma$ for cooperators and $\delta$ for defectors in a mixed population where there are $N/2$ individuals of each type. The plot in the centre shows the fixation probability of each type from the mixed state with $N/2$ individuals of each type. The plot on the right shows the fixation probability of a mutant cooperator $C_\gamma$ (defector $D_\delta$) in a population of $N-1$ resident defectors $D_\delta$ (cooperators $C_\gamma$).

Download: Full-size image PowerPoint slide

Figure 10. Plots created using parameter set 2. Plots are as in Figure 9 with exploration time $T$ decreased from $10$ to $5$.

Download: Full-size image PowerPoint slide

Figure 11. Plots created using parameter set 3. Plots are as in Figure 9 with exploration time $T$ increased from $10$ to $25$.

Download: Full-size image PowerPoint slide

Figure 12. Plots created using parameter set 4. Plots are as in Figure 9 with population size $N$ increased from $10$ to $20$.

Download: Full-size image PowerPoint slide

Figure 13. Plots created using parameter set 5. Plots are as in Figure 9 but $\lambda$ is fixed and reward to cost ratio $v/c$ varied such that $c = 0.04$.

Download: Full-size image PowerPoint slide

Figure 14. Plots created using parameter set 5. Plots are as in Figure 9 but $\lambda$ is fixed and reward to cost ratio $v/c$ varied such that $c = 0.09$.

Download: Full-size image PowerPoint slide

Table 1. Notation used in the paper.

Table of Notation
Notation	Definition	Description
$N$	$\in \mathbb{Z}^+$	Population size.
$M$	$\in \mathbb{Z}^+$	Number of places.
$I_n$		Individual $n$.
$P_m$		Place $m$.
$m_{n, t}$	$\in\{1, \ldots, M\}$	Place where $I_n$ is at time $t$.
${\bf{m}}_t$	$ = [m_{n, t}]_{n = 1}^N$	Population distribution at time $t$.
${\bf{m}}_{<t}$	$ = ({\bf{m}}_{t-1}, \ldots, {\bf{m}}_0)$	Population distribution history.
${p_t}(\bf{m}\left\| {{{\bf{m}}_{ < t}}} \right.)$	$\in[0, 1]$	Probability population has distribution ${\bf{m}}$ at time $t$ given history ${\bf{m}}_{<t}$.
$\pi_t$	$\in[0, 1]$	Population distribution probability function (PDPF).
$P({\bf{m}}_{<t})$	$\in[0, 1]$	Probability that population has history ${\bf{m}}_{<t}$.
$\pi_{n, t}$	$\in[0, 1]$	Individual distribution probability function (IDPF).
$f_{n, t}$	$ \ge 0$	Fitness contribution of $I_n$ at time $t$.
$F_{n, t}$	$>0$	Fitness of $I_n$ at time $t$.
$\mathcal{G}_{n}$	$\subset\{1, 2\ldots, N\}$	Direct group: group that $I_n$ is in.
$w_{i, j, t}$	$\ge 0$	Replacement weight that $I_i$ replaces $I_j$ at time $t$.
${\bf{W}}_t$	$ = [w_{i, j, t}]_{i, j = 1, \ldots, N}$	Weighted adjacency matrix of evolutionary graph.
$u_{i, j, t}$	$\ge 0$	Replacement weight contribution that $I_i$ assigns to $I_j$ at time $t$.
$A, B$		Two types of individuals in the population.
$\mathcal{S}$	$\subset\{1, 2, \ldots, N\}$	Population state, $n\in \mathcal{S}$ if $I_n$ has type $A$.
$\mathcal{N}$	$ = \{1, 2, \ldots, N\}$	State consisting of all type $A$ individuals.
$P_{\mathcal{S}\mathcal{S}'}$	$\in [0, 1]$	Probability of transitioning from $\mathcal{S}$ to $\mathcal{S}'$.
$\rho^A_\mathcal{S}$	$\in[0, 1]$	Fixation probability of type $A$ when the initial state is $\mathcal{S}$.
$\mathfrak{r}_{ij}$	$ \in [0, 1]$	Probability that $I_i$ replaces $I_j$.
$h_n$	$\in [0, 1]$	Probability that $I_n$ stays.
$\alpha_n$	$\in[0, 1]$	Staying propensity: probability that individual $I_n$ stays when alone.
$C\ (D)$		Cooperator and defector interactive strategy.
$\beta_C\ (\beta_D)$	$\in \mathbb{R}$	Benefit of being with a cooperator (defector).
$S$	$\in (0, 1)$	Sensitivity shown to group members.
$v$	$>0$	Reward as a multiple of background fitness.
$c$	$\in [0, 1)$	Cost as a multiple of background fitness.
$R_{n}$	$\ge 0$	Payoff to $I_n$.
$\lambda$	$ \in [0, \min(R_n))$	Movement cost.
$T$	$\in \mathbb{Z}^+$	Exploration time.
$C_\alpha\ (D_\alpha)$		Cooperator (defector) with staying propensity $\alpha$.
$\gamma\ (\delta)$	$\in[0, 1]$	Nash equilibrium staying propensity of cooperator (defector).

| Show Table

DownLoad: CSV

Table 2. Dynamics defined using the replacement weights and fitnesses as in [45]. In each case, B (D) is appended to the name of the dynamics if selection happens in the birth (death) event. For BDB and BDD dynamics $\mathfrak{r}_{ij} = b_{i}d_{ij}$, for DBD and DBB dynamics $\mathfrak{r}_{ij} = d_{j}b_{ij}$.

Dynamics
BDB	$\displaystyle b_i = \frac{ F_i }{\sum_{n} F_n }, \ d_{ij}= \frac{w_{ij} }{\sum_{n} w_{in} }$	BDD	$\displaystyle b_i= \frac{1}{N}, \ d_{ij}= \frac{ w_{ij}F_j^{-1} }{\sum_{n} w_{in}F_n^{-1} }$
DBD	$\displaystyle d_j= \frac{ F_j^{-1}}{ \sum_{n} F_n^{-1} }, \ b_{ij}= \frac{ w_{ij} }{\sum_{n} w_{nj} }$	DBB	$\displaystyle d_j= \frac{ 1 }{ N }, \ b_{ij}= \frac{ w_{ij}F_i }{\sum_{n} w_{nj}F_n }$
LB	$\displaystyle\mathfrak{r}_{ij} =\frac{ w_{ij}F_i}{\sum_{n, k} w_{nk} F_n}$	LD	$\displaystyle \mathfrak{r}_{ij} =\frac{ w_{ij}F_j^{-1} }{\sum_{n, k} w_{nk} F_k^{-1} }$

| Show Table

DownLoad: CSV

Table 3. Parameters used for the simulations. The other parameters are fixed such that we have a complete structure with each individual having its own home, $\beta_C = 1$, $\beta_D = -1$, $S = 0.03$ and the dynamics used are BDB.

Parameter Set	1	2	3	4	5	6
$N$	10	10	10	20	10	10
$T$	10	5	25	10	10	10
$\lambda$	Variable	Variable	Variable	Variable	0.20	0.20
$c$	0.04	0.04	0.04	0.04	0.04	0.09
$v$	0.40	0.40	0.40	0.4	Variable	Variable

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	C. Aktipis, Know when to walk away: Contingent movement and the evolution of cooperation, Journal of Theoretical Biology, 231 (2004), 249-260. doi: 10.1016/j.jtbi.2004.06.020.
[2]	C. Aktipis, Is cooperation viable in mobile organisms? Simple walk away rule favors the evolution of cooperation in groups, Evolution and Human Behavior, 32 (2011), 263-276. doi: 10.1016/j.evolhumbehav.2011.01.002.
[3]	B. Allen and M. Nowak, Games on graphs, EMS Surveys in Mathematical Sciences, 1 (2014), 113-151. doi: 10.4171/EMSS/3.
[4]	B. Allen and C. Tarnita, Measures of success in a class of evolutionary models with fixed population size and structure, Journal of Mathematical Biology, 68 (2014), 109-143. doi: 10.1007/s00285-012-0622-x.
[5]	T. Antal and I. Scheuring, Fixation of strategies for an evolutionary game in finite populations, Bulletin of Mathematical Biology, 68 (2006), 1923-1944. doi: 10.1007/s11538-006-9061-4.
[6]	M. Archetti and I. Scheuring, Coexistence of cooperation and defection in public goods games, Evolution, 65 (2011), 1140-1148. doi: 10.1111/j.1558-5646.2010.01185.x.
[7]	M. Archetti and I. Scheuring, Review: Game theory of public goods in one-shot social dilemmas without assortment, Journal of Theoretical Biology, 299 (2012), 9-20. doi: 10.1016/j.jtbi.2011.06.018.
[8]	M. Broom, C. Cannings and G. Vickers, Multi-player matrix games, Bulletin of Mathematical Biology, 59 (1997), 931-952. doi: 10.1007/BF02460000.
[9]	M. Broom, C. Lafaye, K. Pattni and J. Rychtář, A study of the dynamics of multi-player games on small networks using territorial interactions, Journal of Mathematical Biology, 71 (2015), 1551-1574. doi: 10.1007/s00285-015-0868-1.
[10]	M. Broom and J. Rychtář, An analysis of the fixation probability of a mutant on special classes of non-directed graphs, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 464 (2008), 2609-2627. doi: 10.1098/rspa.2008.0058.
[11]	M. Broom and J. Rychtář, A general framework for analysing multiplayer games in networks using territorial interactions as a case study, Journal of Theoretical Biology, 302 (2012), 70-80. doi: 10.1016/j.jtbi.2012.02.025.
[12]	M. Broom and J. Rychtář, Ideal cost-free distributions in structured populations for general payoff functions, Dynamic Games and Applications, 8 (2018), 79-92. doi: 10.1007/s13235-016-0204-4.
[13]	M. Bruni, M. Broom and J. Rychtář, Analysing territorial models on graphs, Involve, a Journal of Mathematics, 7 (2014), 129-149. doi: 10.2140/involve.2014.7.129.
[14]	M. Bukowski and J. Miekisz, Evolutionary and asymptotic stability in symmetric multi-player games, International Journal of Game Theory, 33 (2004), 41-54. doi: 10.1007/s001820400183.
[15]	M. Cavaliere, S. Sedwards, C. E. Tarnita, M. A. Nowak and A. Csikász-Nagy, Prosperity is associated with instability in dynamical networks, Journal of Theoretical Biology, 299 (2012), 126-138. doi: 10.1016/j.jtbi.2011.09.005.
[16]	X. Chen, A. Szolnoki and M. Perc, Risk-driven migration and the collective-risk social dilemma Physical Review E, 86 (2012), 036101. doi: 10.1103/PhysRevE.86.036101.
[17]	R. Cong, B. Wu, Y. Qiu and L. Wang, Evolution of cooperation driven by reputation-based migration PLoS One, 7 (2012), e35776. doi: 10.1371/journal.pone.0035776.
[18]	G. W. Constable and A. J. McKane, Population genetics on islands connected by an arbitrary network: An analytic approach, Journal of Theoretical Biology, 358 (2014), 149-165. doi: 10.1016/j.jtbi.2014.05.033.
[19]	P. Domenici, R. Batty, T. Similä and E. Ogam, Killer whales (orcinus orca) feeding on schooling herring (clupea harengus) using underwater tail-slaps: Kinematic analyses of field observations, Journal of Experimental Biology, 203 (2000), 283-294.
[20]	M. Enquist and O. Leimar, The evolution of cooperation in mobile organisms, Animal Behaviour, 45 (1993), 747-757. doi: 10.1006/anbe.1993.1089.
[21]	I. Erovenko and J. Rychtář, The evolution of cooperation in one-dimensional mobile populations, Far East Journal of Applied Mathematics, 95 (2016), 63-88.
[22]	J. A. Fletcher and M. Doebeli, A simple and general explanation for the evolution of altruism, Proceedings of the Royal Society of London B: Biological Sciences, 276 (2009), 13-19. doi: 10.1098/rspb.2008.0829.
[23]	F. Fu, C. Hauert, M. A. Nowak and L. ~Wang, Reputation-based partner choice promotes cooperation in social networks, Physical Review E, 78 (2008), 026117.
[24]	C. Gokhale and A. Traulsen, Evolutionary games in the multiverse, Proceedings of the National Academy of Sciences, 107 (2010), 5500-5504. doi: 10.1073/pnas.0912214107.
[25]	C. Gokhale and A. Traulsen, Evolutionary multiplayer games, Dynamic Games and Applications, 4 (2014), 468-488. doi: 10.1007/s13235-014-0106-2.
[26]	W. Hamilton, Extraordinary sex ratios, Science, 156 (1967), 477-488. doi: 10.1126/science.156.3774.477.
[27]	R. Ibsen-Jensen, K. Chatterjee and M. A. Nowak, Computational complexity of ecological and evolutionary spatial dynamics, Proceedings of the National Academy of Sciences, 112 (2015), 15636-15641. doi: 10.1073/pnas.1511366112.
[28]	S. Karlin and H. Taylor, A First Course in Stochastic Processes, London, Academic Press, 1975.
[29]	A. Li, M. Broom, J. Du and L. Wang, Evolutionary dynamics of general group interactions in structured populations, Physical Review E, 93 (2016), 022407, 7pp. doi: 10.1103/PhysRevE.93.022407.
[30]	A. Li, B. Wu and L. Wang, Cooperation with both synergistic and local interactions can be worse than each alone, Scientific Reports, 4 (2014), 1-6. doi: 10.1038/srep05536.
[31]	E. Lieberman, C. Hauert and M. Nowak, Evolutionary dynamics on graphs, Nature, 433 (2005), 312-316. doi: 10.1038/nature03204.
[32]	W. Maciejewski and G. Puleo, Environmental evolutionary graph theory, Journal of Theoretical Biology, 360 (2014), 117-128. doi: 10.1016/j.jtbi.2014.06.040.
[33]	N. Masuda, Directionality of contact networks suppresses selection pressure in evolutionary dynamics, Journal of Theoretical Biology, 258 (2009), 323-334. doi: 10.1016/j.jtbi.2009.01.025.
[34]	J. Maynard Smith, The theory of games and the evolution of animal conflicts, Journal of Theoretical Biology, 47 (1974), 209-221. doi: 10.1016/0022-5193(74)90110-6.
[35]	J. Maynard Smith, Evolution and the Theory of Games, Cambridge University Press, 1982.
[36]	J. Maynard Smith and G. R. Price, The logic of animal conflict, Nature, 246 (1973), 15-18. doi: 10.1038/246015a0.
[37]	P. Moran, Random processes in genetics, in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 54, Cambridge Univ Press, (1958), 60-71. doi: 10.1017/S0305004100033193.
[38]	P. Moran, The Statistical Processes of Evolutionary Theory, Clarendon Press, Oxford, 1962.
[39]	M. Nowak, Evolutionary Dynamics, Exploring the Equations of Life Harward University Press, Cambridge, Mass, 2006.
[40]	H. Ohtsuki, C. Hauert, E. Lieberman and M. Nowak, A simple rule for the evolution of cooperation on graphs and social networks, Nature, 441 (2006), 502-505. doi: 10.1038/nature04605.
[41]	H. Ohtsuki, M. Nowak and J. Pacheco, Breaking the symmetry between interaction and replacement in evolutionary dynamics on graphs, Physical Review Letters, 98 (2007), 108106.
[42]	J. M. Pacheco, A. Traulsen and M. A. Nowak, Active linking in evolutionary games, Journal of Theoretical Biology, 243 (2006), 437-443. doi: 10.1016/j.jtbi.2006.06.027.
[43]	J. M. Pacheco, A. Traulsen and M. A. Nowak, Coevolution of strategy and structure in complex networks with dynamical linking, Physical Review Letters, 97 (2006), 258103. doi: 10.1103/PhysRevLett.97.258103.
[44]	G. Palm, Evolutionary stable strategies and game dynamics for n-person games, Journal of Mathematical Biology, 19 (1984), 329-334. doi: 10.1007/BF00277103.
[45]	K. Pattni, M. Broom, J. Rychtář and L. J. Silvers, Evolutionary graph theory revisited: When is an evolutionary process equivalent to the moran process? in Proc. R. Soc. A, The Royal Society, 471 (2015), 20150334, 19 pp. doi: 10.1098/rspa.2015.0334.
[46]	M. Perc, J. Gómez-Gardeñes, A. Szolnoki, L. M. Floría and Y. Moreno, Evolutionary dynamics of group interactions on structured populations: A review, Journal of The Royal Society Interface, 10 (2013), 20120997. doi: 10.1098/rsif.2012.0997.
[47]	M. Perc and A. Szolnoki, Coevolutionary games-a mini review, BioSystems, 99 (2010), 109-125. doi: 10.1016/j.biosystems.2009.10.003.
[48]	P. Shakarian and P. Roos, Fast and Deterministic Computation of Fixation Probability in Evolutionary Graphs, Technical report, DTIC Document, 2012.
[49]	P. Shakarian, P. Roos and A. Johnson, A review of evolutionary graph theory with applications to game theory, Biosystems, 107 (2012), 66-80. doi: 10.1016/j.biosystems.2011.09.006.
[50]	T. Similä, Sonar observations of killer whales (orcinus orca) feeding on herring schools, Aquatic Mammals, 23 (1997), 119-126.
[51]	G. Szabó and G. Fath, Evolutionary games on graphs, Physics Reports, 446 (2007), 97-216. doi: 10.1016/j.physrep.2007.04.004.
[52]	M. van Veelen and M. Nowak, Multi-player games on the cycle, Journal of Theoretical Biology, 292 (2012), 116-128. doi: 10.1016/j.jtbi.2011.08.031.
[53]	B. Voorhees and A. Murray, Fixation probabilities for simple digraphs in Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., The Royal Society, 469 (2013), 20120676, 18pp. doi: 10.1098/rspa.2012.0676.
[54]	J. Wang, B. Wu, D. Ho and L. Wang, Evolution of cooperation in multilevel public goods games with community structures, EPL (Europhysics Letters), 93 (2011), 58001.
[55]	B. Wu, A. Traulsen and C. S. Gokhale, Dynamic properties of evolutionary multi-player games in finite populations, Games, 4 (2013), 182-199. doi: 10.3390/g4020182.
[56]	B. Wu, J. Arranz, J. Du, D. Zhou and A. Traulsen, Evolving synergetic interactions Journal of The Royal Society Interface 13 (2016), 20160282. doi: 10.1098/rsif.2016.0282.
[57]	T. Wu, F. Fu, Y. Zhang and L. Wang, Expectation-driven migration promotes cooperation by group interactions, Physical Review E, 85 (2012), 066104. doi: 10.1103/PhysRevE.85.066104.
[58]	L. Zhou, A. Li and L. Wang, Evolution of cooperation on complex networks with synergistic and discounted group interactions, EPL (Europhysics Letters) 110 (2015), 60006. doi: 10. 1209/0295-5075/110/60006.