Evolutionary games in finite inviscid populations

Last week, we saw how to deal with two-strategy games in finite inviscid populations. Unfortunately, two strategy games are not adequate to model many of the interactions we might be interested in. In particular, we cannot use Antal et al. (2009a) to look at bifurcations and finitary/stochastic effects in tag-based models of ethnocentrism, at least not without some subtle tricks. In this post we are going to look at a more general approach for any n-strategy game developed by Antal et al. (2009b). We will apply these tools to look at a new problem for the paper, but an old problem for the blog: ethnocentrism.

Antal et al. (2009b) consider a large but finite population of size N and a game A with n strategies. For update rule, they focus on the frequency dependent Moran process, although their results also hold for Wright-Fisher, and pairwise comparison (Fermi rule). Unlike the previous results for two-strategy games, the present work is applicable only in the limit of weak selection. Mutations are assumed to be uniform with probability u: a mutant is any one of the n strategies with equal probabilities. However, in section 4.2, the authors provide a cute argument for approximating non-uniform but parent-independent mutation rates by repeating strategies in proportion to the likelihood of mutation into them. Much like the two-strategy case, the authors derive separate equations for low and high mutation rates, and then provide a way to interpolate between the two extremes for intermediate mutation rates.

The mathematics proceeds through a perturbation analysis. The basic idea is to solve for the distribution of strategies in the drift (no selection) model, and then to gradually dial up the selection to perturb the distribution slightly into the weak selection regime. The authors use this to arrive at the following to conditions for low, and high mutation for strategy k to be favored:

\begin{aligned}  L_k & = \frac{1}{n}\sum_{i = 1}^{n}(a_{kk} + a_{ki} - a_{ik} - a_{ii}) > 0 \\  H_k & = \frac{1}{n^2}\sum_{i,j = 1}^n(a_{kj} - a_{ij}) > 0  \end{aligned}

There is an intuitive story to help understand these two conditions. In the case of low mutation, the population is usually just two strategies until one of them fixes. So for L_k the terms that matter are the pairwise interactions between the strategies, and since the most decisive (and entropy rich) case is near the 50-50 split in the two strategies, self interactions (a_{kk}) and other-strategy interactions (a_{ki}) happen with the same frequency. I think this is where the discrepancy with Antal et. al (2009a) that we will see later sneaks in. A correction factor of \frac{N - 2}{N} should be added in front of the the self-interaction terms, but I digress.

For the high mutation case, all the strategies are present in the population with about the same frequency at the same time. We need to look at the transitions from this population to get our first order terms. In that case, the focal individual’s fitness is f_k = \frac{1}{n} \sum_{j = 1}^n a_{kj} (since all opponents are equally likely; once again, I believe a correction term is in order), and the average fitness is \frac{1}{n} \sum_{i = 1}^n f_i. The difference of these two terms produces H_k.

In order to interpolate, we have the following condition for strategy i to be more common than j for intermediate mutation rates u:

L_i + uNH_i > L_j + uNH_j

How does this disagree with the two-strategy results of Antal et al. (2009a)? The present paper reproduces the condition of risk-dominance, with C dominating D if 1 > V - U, but does not produce the small N correction of \frac{N - 2}{N} > V - U. This would be mitigated with the observations I made earlier, but the approach of the perturbation analysis would have to be modified carefully.

The perturbation method can be extended to mixed strategies, as is done by Tarnita et al. (2009). In that case, we just replace the summation by integrals, to get:

\begin{aligned}  L_p & = \frac{1}{||S_n||}\int_{S_n}(p^TAp + p^TAq - q^TAp - q^TAq) dq > 0 \\  H_p & = \frac{1}{||S_n||^2}\int_{S_n} \int_{S_n} (p^TAq - r^TAq) dq dr > 0  \end{aligned}

Where S_n is the n-vertex simplex with volume ||S_n|| = \frac{\sqrt{n}}{(n - 1)!}. It is nice to know that the results generalize to mixed strategies, but not as important tool as the pure strategy variant. I will concentrate on pure strategies, although mixed might be good to revisit to study evolution of agency.

Antal et al. (2009b) showcase their method with three case studies: (i) cooperators, defectors, and loners, (ii) reversing the rank of strategies by mutation, and (iii) cooperators, defectors, and tit-for-tat. The first is the most interesting for me, since it shows how adding an irrelevant strategy, can reverse the dominance of the other two. I will present their example in a more general context for all cooperate-defect games. We will introduce an irrelevant strategy L, where irrelevance means that both C and D get the same payoff X from interacting with L and L gets Y from them. The self interaction payoff for L can differ, and we can set it to Z:

\begin{pmatrix}  1 & U & X \\  V & 0 & X \\  Y & Y & Z  \end{pmatrix}

The authors consider the particular case of V = 9/8 and U = -1/8, and X = Y = Z = -1/4. We can apply the general results to get (for small mutations):

\begin{aligned}  L_C & = \frac{1}{3}(2 + U - V + X - Y - Z) \\  L_D & = \frac{1}{3}(V - U - 1 + X - Y - Z) \\  L_L & = \frac{1}{3}(2(Y - Z) - 1)  \end{aligned}

We can look at at the condition for C to dominate D for small mutations (L_C > L_C) to get \frac{3}{2} > V - U. If we had used M different irrelevant strategies (or just dialed up the proportion of mutations to an irrelevant strategy) then \frac{3}{2} would be replaced by 1 + \frac{M}{2}. This creates a new strip of cooperation which reaches into the Prisoner’s dilemma region (drawn in blue):

When we switch to large mutations, the region disappears and we recover the standard 1 > V - U rule. Note that this example means that, for this analysis, we cannot ignore competing strategies even if they are strictly dominated.

Ethnocentrism in tag-based models

We will consider a strategy space of K tags, with an agent of each tag being either a humanitarian (cooperate with all), ethnocentric (cooperate with same-tag), traitorous (cooperate with oot-tags), or selfish. For the game, we will look at the usual cost-benefit representation of Prisoner’s dilemma. Note that the L and H values will be the withing a single strategy of different tags, so we only need to compute four of each:

\begin{aligned}  L_{H} & = -c \\  L_{E} & = \frac{K - 1}{K}b - \frac{1}{K}c \\  L_{T} & = -\frac{K - 1}{K}b + \frac{1}{K}c \\  L_{S} & = c  \end{aligned}

This divides the dynamics into two regions, when \frac{K - 1}{K + 1} > \frac{c}{b} then E > S > H > T, otherwise we have S > E > T > H. In other words, for large enough K or small enough c/b, ethnocentrism can be the dominant strategy in the population. This condition is in perfect agreement with the Traulsen & Nowak (2007) results we saw earlier. Although in that case, there were no H or T agents. If we remove H & T from the current analysis, we will still get the same condition for ethnocentric dominance even though we will calculate different L values.

For large mutations, the advantage of ethnocentrics disappears completely, and we get:

\begin{aligned}  H_{H} & = -\frac{c}{2} \\  H_{E} & = \frac{K - 2}{2K}c \\  H_{T} & = -\frac{K - 2}{2K}c  \\  H_{S} & = \frac{c}{2}  \end{aligned}

Which for K \geq 2 results in the ordering S > E \geq T > H. So if we have mutations that change tag and strategy together (as they do in this case) then higher mutation rates disadvantage the population, and if we let M = uN be the expected number of mutants per generation, then we can see that ethnocentric cooperation is possible only if M < (K - 1)\frac{b}{c} - (K + 1) or rewritten as \frac{K - 1}{M + K + 1} > \frac{c}{b}.

References

Antal, T., Nowak, M.A., & Traulsen, A. (2009a). Strategy abundance in games for arbitrary mutation rates Journal of Theoretical Biology, 257 (2), 340-344.

Antal T, Traulsen A, Ohtsuki H, Tarnita CE, & Nowak MA (2009b). Mutation-selection equilibrium in games with multiple strategies. Journal of Theoretical Biology, 258 (4), 614-22 PMID: 19248791

Tarnita, C.E., Antal, T., Nowak, M.A. (2009) Mutation-selection equilibrium in games with mixed strategies. Journal of Theoretical Biology 26(1): 50-57.

Traulsen A, & Nowak MA (2007). Chromodynamics of cooperation in finite populations. PLoS One, 2 (3).

About these ads

About Artem Kaznatcheev
From the ivory tower of the School of Computer Science and Department of Psychology at McGill University, I marvel at the world through algorithmic lenses. My specific interests are in quantum computing, evolutionary game theory, modern evolutionary synthesis, and theoretical cognitive science. Previously I was at the Institute for Quantum Computing and Department of Combinatorics & Optimization at the University of Waterloo and a visitor to the Centre for Quantum Technologies at the National University of Singapore.

One Response to Evolutionary games in finite inviscid populations

  1. Pingback: EGT Reading Group 36 – 40, G+ and StackExchange | 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

Follow

Get every new post delivered to your Inbox.

Join 2,065 other followers