← Is Chaitin proving Darwin with metabiology?

Critique of Chaitin’s algorithmic mutation →

Ethnocentrism in finite inviscid populations

July 5, 2012 by Artem Kaznatcheev 4 Comments

In preparation for EGT Reading Group 31 and as a follow up to my previous post on inviscid ethnocentrism, I decided to look at Martin Nowak’s first paper on tag-based models (Traulsen & Nowak, 2007). For Arne Traulsen, this was the 3rd paper on ethnocentrism. Traulsen’s first publication (Traulsen & Shuster, 2003) provided a simplified analysis of the classic Riolo et al. (2001) and considered linked strategy-tag combinations (where one has to cooperate with the in-group), but showed that the analysis is possible with just two tags and not a continuum. Traulsen & Claussen (2004) considered a model closer to our familiar H&A model and showed the evolution of ethnocentrism in a spatial lattice. Trausen & Nowak (2007) follow Jansen & van Baalen (2006) in building a model in which cheaters (defectors against in-group; selfish agents in our terminology) are possible but no spatial structure is available. They move past Jansen & van Baalen (2006) by considering finite populations in which only two tags need to co-exist at a time.

The authors consider a model with a fixed number $N$ of agents. Each agent has one of $K$ possible tags, and interactions happen only within a tag. The agent can be either a cooperator (ethnocentric in our terminology) or defector (selfish in our terminology), allowing for a total of $2K$ phenotypes. The payoffs from random interactions are computed according to the standard b-c Prisoner’s dilemma game, with $b$ the benefit of receiving cooperation and $c$ the cost of providing the cooperation. The population is updated by selection two individuals uniformly at random and having the first adopt the strategy of the second (with some probability of mutation) with probability $(1 + e^{\beta(\pi_1 - \pi_2)})^{-1}$ where $\pi_1$ is the utility of the first individual, and $\pi_2$ — the second. The parameter $\beta$ corresponds to the strength of selection, and in the analytic model the regime of weak selection ( $\beta << \frac{1}{N}$ ) is considered.

The probability of mutating strategy while keeping tag fixed is given by $u$ , and the probability of mutating both strategy and tag at the same time is given by $v$ . With this Traulsen & Nowak arrive at their main result, cooperative behavior evolves if:

$\frac{b}{c} > 1 + 2\frac{u}{v}$

Note that this cooperative behavior is not permanent, but comes in tides of tolerance. Cooperators of a given tag dominate until invaded by a defector. So the prediction is meant to apply to long-term averages over many evolutionary cycles and not a stable absorbing state.

The authors instantiate their analytic approach in three concrete models. For the first, they consider a binary genotype of length $L + 1$ where the first bit gives the strategy and the remaining $L$ bits are the tag. They assume that any bit has a mutation probability $\mu$ , but do not allow double mutations in the tag. This gives the condition for cooperation:

$\frac{b}{c} > 1 + 2\frac{1 - \mu}{L\mu}$

Since their analysis is valid for only small mutation rates $\mu$ , this suggests a high $\frac{b}{c}$ . However, it is not clear to me why the authors didn’t simply allow an arbitrary number of mutations in the tag-coding region. This would give $u = \mu (1 - \mu)^L$ and $v = \mu(1 - (1 - \mu)^L)$ which provides a simpler condition of:

$\frac{b}{c} > 2\frac{1}{1 - (1 - \mu)^L} - 1$

Which in the limit of large $L$ (or more formally as $L \rightarrow \infty$ ) and small (relative to size of genome) mutations $\mu = \frac{x}{L}$ gives:

$\frac{b}{c} > 2\frac{1}{1 - e^{-x}} - 1$

Which means that cooperation evolves if the mean number of point-mutations per offspring $x$ is greater than $\ln(\frac{b + c}{b - c})$ .

For their second model, Traulsen & Nowak consider the more reasonable case with the parity of the first $n$ bits coding the strategy. The remaining bits, along with $L$ bits of overlap with the first $n$ , code the tag. Here, in the limit of one point-mutation per generation ( $\mu << \frac{1}{n}$ ) they arrive at the requirement for cooperation:

$\frac{b}{c} > \frac{2n - L}{L}$

Note that this scales to the trivial $b/c > 1$ for linked strategy-tag genes, thus recreating (in-spirit) the earlier results of Riolo et al. (2001) and Traulsen & Schuster (2003).

Traulsen & Nowak’s last model is of the greatest interest to me, since it resembles mutation in the H&A model. Here the authors consider equal mutation probability between any strategy-tag pair and with $K$ possible tags arrive at the condition:

$\frac{b}{c} > \frac{K + 1}{K - 1}$

This means we need $\frac{b}{c} > 3$ in the minimal case of 2 tags, and the requirements relax towards the trivial $\frac{b}{c} > 1$ as $K \rightarrow \infty$ . In my earlier preliminary results, I concentrated on 4 tags and $b/c = 4$ which is higher than the 5/3 required from Traulsen & Nowak’s results, and observed both tides of tolerance (periodic fluctuations in amount of cooperative interactions) and absorbing states of all-cooperation or all-defection. I also briefly showed that $b/c = 5/4$ bifurcates, and this can be even more clearly seen in the following graph of $b/c = 6/5$ with only two tags:

Proportion of cooperation versus evolutionary cycle of 30 simulations run for 3000 cycles. The benefit-to-cost ration is 1.2 and there are only two tags. Runs that had less than 5% cooperation (24 runs) in the last 500 cycles are traced by red lines; more than 95% cooperation (3 runs) by green; intermittent amounts (3 runs) are yellow. The black line represents the average of all 30 runs, no standard error is shown.

This is well outside the regime where Traulsen & Nowak predict cooperation. The model I use has a simpler selection rule and incorporates free-space in the inviscid population; it is not meant to question Traulsen & Nowak. However, it is nice to know that my preliminary results produce cooperative interactions outside of the known regions of mutation-driven ethnocentrism.

References

Jansen VAA, & van Baalen M (2006). Altruism through beard chromodynamics. Nature 440: 663–666.

Riolo RL, Cohen MD, & Axelrod R (2001). Evolution of cooperation without reciprocity. Nature 414: 441–443.

Traulsen A, & Claussen JC (2004). Similarity-based cooperation and spatial segregation. Phys Rev E 70: 046128.

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

Traulsen A, & Schuster HG (2003). Minimal model for tag-based cooperation. Phys Rev E 68: 046129.

Filed under Preliminary, Reviews, Technical Tagged with ethnocentrism, evolution of cooperation, Martin A. Nowak, prisoner's dilemma, Robert Axelrod

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.