Evolutionary games in set structured populations

We have previously discussed the importance of population structure in evolutionary game theory, and looked at the Ohtsuki-Nowak transform for analytic studies of games on one of the simplest structures — random regular graphs. However, there is another extremely simple structure to consider: a family of inviscid sets. We can think of each agent as belonging to one or more sets and interacting with everybody that shares a set with them. If there is only one set then we are back to the case on a completely inviscid population. If we associate a set with each edge in a graph and restrict them to have constant size then we have standard evolutionary graph theory. However, it is more natural to allow sets to grow larger if their members have high fitness.

Tarnita et al. (2009) consider a population of N individuals and M sets, where each individual can belong to K of the sets. Strategy and set membership are heritable (with mutation probabilities u and v, respectively), and interactions are only with agents that share a set (if two agents share more than one set then they interact more than once). However, reproduction is inviscid: a random individual is selected to die and everybody competes to replace them with a child. This set-dependent interaction, makes the model equivalent to the earliest models of ethnocentrism, but the model is not equivalent to more modern approaches to ethnocentrism. Since sets cannot reproduce and migration (through mutation) between sets is purely random, the model also cannot capture group selection. However, cooperation for the Prisoners’ dilemma still emerges in this model, if we have:

\frac{b}{c} \geq \frac{K}{M - K}(\nu + 2) + \frac{M}{M - K}\frac{\nu^2 + 3\nu + 3}{\nu(\nu + 2)}

Where \nu = 2Nv is the population-scaled set mutation rate, even when this is zero we get cooperation when \frac{b}{c} \geq \frac{3}{2} + \frac{7K}{2(M - K)}. Alternatively, to simplify we can take the limit of M >> K = 1 to get:

\frac{b}{c} \geq 1 + \frac{1}{\nu}(1 + \frac{1}{\nu + 2}) + \frac{\nu + 2}{M}

If we allow the maximum number of sets (M = N) and take the further limit of large populations N >> 2 then this becomes a very simple:

\frac{b}{c} \geq 1 + 2v

Finally, in the supplementary materials, the authors derive a very nice relationship for evolution of cooperation on arbitrary cooperate-defect games given by a payoff matrix \begin{pmatrix}1 & U \\ V & 0\end{pmatrix} of:

\sigma \geq V - U

where \sigma is a structural constant given by:

\sigma = \frac{1 + \nu + \mu}{3 + \nu + \mu)}\frac{K(\nu^2 + 2\nu + \nu\mu) + M(3 + 2\nu + \mu}{K(\nu^2 + 2\nu + \nu\mu) + M(1 + \mu)}

Which in the limit of small population-scaled strategy mutation (\mu = 0), and M >> K becomes:

\sigma = 1 + \nu + \frac{\nu(\nu + 1)}{\nu + 3}

Since the structural constant is always greater than 1, and since we typically care about large \nu, it is more enlightening to look at the reciprocal that in the limit of large \nu >> 3 becomes:

\frac{1}{\sigma - 1} = \frac{1}{2\nu}

And simplifies the general equation for cooperation to emerge to:

1 + 2\nu \geq V - U

Which can be seen as a relaxation of the classic game theory concept of risk-dominance.

ResearchBlogging.orgTarnita, C., Antal, T., Ohtsuki, H., & Nowak, M. (2009). Evolutionary dynamics in set structured populations Proceedings of the National Academy of Sciences, 106 (21), 8601-8604 DOI: 10.1073/pnas.0903019106


About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.

3 Responses to Evolutionary games in set structured populations

  1. Pingback: Quasi-magical thinking and superrationality for Bayesian agents | Theory, Evolution, and Games Group

  2. Pingback: Cataloging a year of blogging: applications of evolutionary game theory | Theory, Evolution, and Games Group

  3. Pingback: Hadza hunter-gatherers, social networks, and models of cooperation | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s