Introduction to evolving cooperation

Since 2009, I’ve had a yearly routine of guest lecturing for Tom’s Cognitive Science course. The way I’ve structured the class was by assigning videos to watch before the lecture so that I could build on them. Last year, I started posting the video ahead of time on the blog: my 2009 TEDxMcGill talk, Robert Wright’s evolution of compassion, and Howard Rheingold’s new power of collaboration. However, instead of just presenting a link with very little commenatry, this time I decided to write a transcript with my talk that I seeded with references and links for the curious. The text is not an exact recreation of the words, but a pretty close fit that is meant to serve as a gentle introduction to the evolution of cooperation.

Earlier today, we heard about the social evolution of language and to a certain extent we heard about the emergence and evolution of zero. We even heard about our current economic affairs and such. I am going to talk about all of these things and, in particular, continue the evolutionary theme and talk about the evolution of cooperation in society and elsewhere.

We’ve all come across ideas of the greater good, altruism, cooperation or the sacrifice of an individual for the good of others. In biology, we have an analogous concept where we look at the willingness of certain individuals to give up some of their reproductive potential to increase the reproductive potential of others. This paradoxical concept in the social sciences is grappled with by philosophers, sociologists, and political scientists. In the biological context, it is obviously an important question to biologists.

Now, the question really becomes as to how and why does this cooperation emerge? First, we are going to look at this from the biological point of view, connect it to the social sciences, and then to everything else.

Currently, biology is really shaped by Darwin, Wallace and their theory of evolution by natural selection. It is a unifying theme and tie of modern biology. The interesting feature of biology is that it is an explicitly competitive framework: organisms compete against other organisms for their reproduction. Our question becomes: how does cooperation emerge in such a competitive environment?

We know this cooperation does emerge because it is essential for all the complexity we see. It is essential for single cells to come together into multi-cellular organisms, for the emergence of ant colonies, and even human society. We want to study this and try to answer these questions. But how do you create a competitive environment in a mathematical framework? We borrow from game theory the idea of Prisoner’s dilemma, or in my case I prefer the Knitter’s dilemma. This is one of many possible models of a competitive environment, and the most used in the literature.

In the Knitter’s dilemma there are two players. One of them is Alice. Alice produces yarn, but she doesn’t have any needles, and she wants to sew a sweater. In the society that she lives, knitting sweaters is frowned upon, so she can’t go ask for needles publicly. Bob, on the other hand, produces needles but not yarn. He also wants to sew a sweater. So they decide: “okay, lets go out into the woods late at night, bring briefcases with our respected goods and trade”.

Alice has a dilemma: should she include yarn in her briefcase (indicated by the green briefcase in the figure below)? Or should she not (signified by the red)? If Bob includes needles (first column), and Alice includes yarn then she gets the benefit b of going home and knitting a sweater, but she does pay a small cost c for giving away some of her yarn. Alternatively, if Bob brings needles, but she’s tricky and doesn’t bring her yarn then she gets all the benefit of going home and making a sweater without paying even the marginal cost of giving away some of her yarn. If Bob brings an empty briefcase (second column), and Alice brings yarn as she said she would then Alice pays a small cost in giving some of her yarn away without benefit of being able to make a sweater. Alternatively, if she also brings an empty briefcase then they just met in the middle of the night, traded empty briefcases, and everybody goes back with the no payoff.

Knitter's dilemma

It seems that no matter what Bob does, it is better for Alice to bring an empty briefcase, what we call defection, than to cooperate by bringing a full briefcase. This sets up the basic idea of a competitive environment. The rational strategy, or the Nash equilibrium, for this game is for both individuals to defect and bring empty briefcases. However, from outside the game we can see that if they both do what they said they would and cooperate then they are both better of. That is captured by the Pareto optimum in green.

Of course, as mentioned earlier by Andy, we cannot always expect people to be rational and make all these decisions based on reasoning. Evolutionary game theory comes from the perspective of modeling Alice and Bob as simple agents that have a trait that is passed down to their offspring. This is shown below by green circles for players that cooperate and red circles for ones that don’t. In the standard model, we will pair them off randomly and they will play the game. So a green and a green is two cooperators; they both went home and made a sweater. Two reds both went empty handed. After interaction we disseminate them through the population and let them reproduce according to how the game affected their potential. Higher for people that received a large benefit, and lower chance to reproduce to people who only paid costs. We cycle this for a while, and what we observe is more and more red emerging. All the green cooperation starts to go away. This captures the basic intuition that a competitive environment breeds defection.

Of course, you and I can think of some ways to overcome this dilemma. Evolutionary game theorists have also been there and thought of it (Nowak, 2006). They thought of three models of how to avoid it. The first is Hamilton’s (1964) kin selection: Bob’s actually your uncle, and you’re willing to work with him. You’ll bring the yarn as you said you would. Alternatively, you’ve encountered Bob many times before and he has always included needles in his briefcase. You are much more willing to work with him. This is Trivers’ (1971) direct reciprocity, and you’ll include your yarn. Finally, indirect reciprocity (Nowak & Sigmund, 1998): you’ve heard that Bob is an honest man that always brings needles as he says he will. So you are much more likely to cooperate with him.

All these things seem pretty simple to us, but if we’re an amoeba floating around in some soup (and microbes do play games; Lenski & Velicer 2001) then it’s not quiet as obvious that we can do any of these things. Recognizing kin, remembering past interactions, or social constructs like reputation become very difficult. Hence, I look at the more primitive methods such as spatial/network reciprocity or viscosity.

Earlier, Paul mentioned that if we have a turbulent environment it becomes very hard for us to live. Hence the idea that we introduce some structure into our environment. We populate all our agents inside a small grid where they can interact with their neighbors and reproduce into neighboring squares.

Alternatively, we can borrow an idea from the selfish gene approach to evolution called the green-beard effect. This was introduced by Hamilton (1964) & Dawkins’ Selfish Gene. This is a gene that produces three phenotypical effects: (1) it produces an arbitrary marker which we call the beard (or in our case circles and squares), (2) it allows you to recognize this trait in others, not their strategy just the trait/beard, and (3) it allows you to change your strategy depending on what trait/beard you observe. As before, you can cooperate or defect with other circles, or if you meet a square then you can also chose to cooperate or defect. You have four possible strategies that are drawn in the figure below. In human culture, cooperating with those that are like you (i.e. other circles) and defecting against those that are squares is the idea of ethnocentrism. Here we bring back the social context a little bit by looking at this as a simple model of human evolution, too.

We can combine the two models, by looking at little circles and squares of different colors inside a grid, and seeing how the population will evolve with time. The results we observe are that we do see cooperation emerge, but sadly it is an ethnocentric sort of cooperation. We can see it from the below graph where the y-axis is proportion of cooperative interactions: the higher up you are in the graph, the more cooperation is happening, so the better it is. In the blue model we have agents that can distinguish between circles and squares living inside a spatial lattice. In the green we see a model with spatial structure, but no cognitive ability to adjust based on tags. In the red and the yellow you can see models where there is no spatial structure, or there is no ability to recognize people based on if they are a circle or a square. In these restricted models cooperation does not consistently emerge. Although in the tags with no space model in yellow there is occasional bifurcation of cooperation highlighted by the black circle and arrow.

Annotated reproduction of figure from Kaznatcheev & Shultz 2011

Proportion of cooperation versus evolutionary cycle for four different conditions. In blue is the standard H&A model; green preserves local child placement but eliminates tags; yellow has tags but no local child placement; red is both inviscid and tag-less. The lines are from averaging 30 simulations for each condition, and thickness represents standard error. Figure appeared in Kaznatcheev & Shultz (2011).

This gives us a suggestion of how evolution could have shaped the way we are today, and how evolution could have shaped the common trend of ethnocentrism in humans. The model doesn’t propose ways to overcome ethnocentrism, but one thing it does is at least create cooperation among scientists who use it. In particular, the number of different fields (represented in one of my favorite xkcd comics, below) that use these sort of models.

Sociologists and political scientists use these models for peace building and conflict resolution (eg. Hammond & Axelrod, 2006). In this case cooperation would be working towards peace, and defection could be sending a mortar round into the neighboring village. Psychologists look at games like the Prisoner’s dilemma (or the Knitter’s dilemma in my case) and say “well, humans tend to cooperate in certain settings. Why is that? Can we find an evolutionary backing for that?” In our running example by looking at ethnocentrism (eg. Shultz, Hartshorn, & Kaznathceev, 2009). Biologists look at how the first molecules came together to form life, or how single cells started to form multi-cellular organisms. Even in cancer research (eg. Axelrod, Axelrod, & Pienta, 2006) and the spread of infectious disease such as the swine flu (eg. Read & Keeling, 2003). Even chemists and physicists use this as a model of self-organizing behavior and a toy model of non-linear dynamics (eg. Szabo & Fath, 2007). Of course, it comes back to computer scientists and mathematicians, who use this for studying network structure and distributive computing. The reason all these fields can be unified by the mathematical idea underlying evolution seems kind of strange. The reason this can happen is because of the simple nature of evolution. Evolution can occur in any system where information is copied in a noisy environment. Thus, all these fields can cooperate together in working on finding answers to the emergence and evolution of cooperation. Hopefully, starting with the scientists working together on these questions, we can get people around the world to also cooperate.

References

Axelrod, R., Axelrod, D. E., & Pienta, K. J. (2006). Evolution of cooperation among tumor cells. Proceedings of the National Academy of Sciences, 103(36), 13474-13479.

Hamilton, W. D. (1964). The Genetical Evolution of Social Behavior. Journal of Theoretical Biology 7 (1): 1–16.

Hammond, R. A., & Axelrod, R. (2006). The evolution of ethnocentrism. Journal of Conflict Resolution, 50(6), 926-936.

Kaznatcheev, A., & Shultz, T.R. (2011). Ethnocentrism Maintains Cooperation, but Keeping One’s Children Close Fuels It. Proceedings of the 33rd Annual Conference of the Cognitive Science Society, 3174-3179

Lenski, R. E., & Velicer, G. J. (2001). Games microbes play. Selection, 1(1), 89-96.

Nowak MA (2006). Five rules for the evolution of cooperation. Science (New York, N.Y.), 314 (5805), 1560-3 PMID: 17158317

Nowak, M. A., & Sigmund, K. (1998). Evolution of indirect reciprocity by image scoring. Nature, 393(6685), 573-577.

Read, J. M., & Keeling, M. J. (2003). Disease evolution on networks: the role of contact structure. Proceedings of the Royal Society of London. Series B: Biological Sciences, 270(1516), 699-708.

Shultz, T. R., Hartshorn, M., & Kaznatcheev, A. (2009). Why is ethnocentrism more common than humanitarianism. In Proceedings of the 31st annual conference of the cognitive science society (pp. 2100-2105).

Szabo, G., & Fath, G. (2007). Evolutionary games on graphs. Physics Reports, 446 (4-6), 97-216

Trivers, R. L. (1971). The evolution of reciprocal altruism. Quarterly review of biology, 35-57.

Ohtsuki-Nowak transform for replicator dynamics on random graphs

We have seen that the replicator equation can be a useful tool in understanding evolutionary games. We’ve already used it for a first look at perception and deception, and the cognitive cost of agency. However, the replicator equation comes with a number of inherent assumptions and limitations. The limitation Hisashi Ohtsuki and Martin Nowak wanted to address in their 2006 paper “The replicator equation on graphs” is the assumption of a totally inviscid population. The goal is to introduce a morsel of spatial structure, while still retaining the analytic tractability and easy-of-use of replicator dynamics.

Replicator dynamics assume that every individual in population is equally likely to interact with every other individual in the population. However, in most settings the possible interactions are not as simple. Usually, there is some sort of structure to the population. The way we usually model structure, is by representing individuals as vertexes in a graph, and if two vertexes are adjacent (connected by an edge) then the two individuals can interact. For replicator dynamics the model would be a complete graphs. Ohtsuki and Nowak consider a structure which is a bit more complicated: a random k-regular graph.

There are several ways to think about random k-regular graphs. We call a graph k-regular if every vertex has exactly k edges incident on it (and thus, exactly k neighbors). If we consider a sample from the uniform distribution over all k-regular graphs then we get a random k-regular graph. Of course, this is an inefficient approach, but captures the main statistical qualities of these graphs. To see how to efficiently generate a graph, take a look at Marcel’s post on generating random k-regular graphs.

With the spatial structure in place, the next important decision is the update or evolutionary dynamics to use. Ohtsuki & Nowak (2006) consider four different rules: birth-death (BD), death-birth (DB), imitation (IM), and pairwise comparison (PC). For BD, player is chosen for reproduction in proportion to fitness and the offspring replaces a neighbor chosen uniformly at random. In DB, a focal agent is chosen uniformly at random and is replaced by one of his neighbors, who are sampled randomly in proportion to fitness. IM is the same as DB, except the focal agents counts as one of its own neighbors. For PC, both the focal individual and his partner are chosen uniformly at random, but the focal agent replaces his partner with probability that depends (according to the Fermi rule) on their payoff difference, otherwise the partner replaces the focal individual.

Throughout the paper, fitness is calculated in the limit of weak selection. To account for the spatial structure, the authors use pair-approximation. This method is perfect for Bethe lattice and accurate for any graph that is locally tree like. Thankfully, random graphs are locally tree like (out to distance on the order of \log n) and hence the analysis is reasonable for large n. However, most real-world networks tend to have high clustering coefficients, and thus are not tree-like. For such networks, the Ohtsuki-Nowak transform would be a bad choice, but still a step closer than the completely inviscid replicator dynamics.

The stunning aspect of the paper, is that in the limit of very large populations they get an exceptionally simple rule. Give a game matrix A, you just have to compute the Ohtsuki-Nowak transform A' = \text{ON}_{k,\nu}(A) and then you recover the dynamics of your game by simply looking at the replicator equation with A'. In will present the authors in slightly different notation than their paper, in order to stress the most important qualitative aspects of the transform. That the purpose I need to define the column vector \Delta which is the diagonal of the game matrix A = [a_{ij}], i.e. \Delta_i = a_{ii}. The transform becomes:

\text{ON}_{k,\nu}(A) = A + \frac{1}{k-2}(\Delta\vec{1}^T - \vec{1}\Delta^T) + \frac{\nu}{k - 2}(A - A^T)

Where \vec{1} is the all ones vector; thus \Delta\vec{1}^T (\vec{1}\Delta^T) is a matrix with diagonal elements repeated to fill each row (column). I call the last element (\nu) the neighborhood update parameter. Ohtsuki & Nowak show that for birth-death and pairwise comparison \nu = 1, for imitation it is \nu = \frac{3}{k + 3}, for death-birth \nu = \frac{1}{k + 1}. I used this suggestive notation, because I think the transform can be refined to allow all values of \nu between 1 and \frac{1}{k + 1}. In particular, I think the easiest way to achieve this is by selecting between BD and DB with some probability at each update step.

My other reason for rewriting in this condensed form is to gain an intuition for each term of the sum. The first term is the original game, and is expected to be there with some summation because we are doing a small perturbation in the limit of weak selection, thus a linear correction to A is not surprising. The second term contains a difference of only diagonal elements between the focal agent and the competing strategy. Thus, the second term is local-aggregation terms and it is not surprising to see it lose strength as k increases and the focal agent has a smaller and smaller effect on its neighborhood. Ohtsuki & Nowak think of the third term as an assortment factor, however this intuition is lost on me. Hilbe (2011) studies the replicator equation with finite sampling, and achieves the same modification (with some massaging) as the third term of ON_{k,\nu}(A) which we will discuss in a future post. Thus, I find it better to think of the third term as a finite sampling term. It is then clear why the term decreases from BD to DB: the sampling neighborhood for calculating fitness is quadratically larger in the latter update rule.

As case studies, Ohtsuki & Nowak (2006) apply their transform to the prisoner’s dilemma, snowdrift, coordination, and rock-paper scissors games. I refer the interested reader to the original paper for the latter example and I will deal with the former three at once by looking at all cooperate-defect games:

\begin{aligned}  \text{ON}_{k,\nu}( \begin{pmatrix} 1 & U \\ V & 0 \end{pmatrix} )  & = \begin{pmatrix} 1 & U \\ V & 0 \end{pmatrix} + \frac{1}{k - 2} \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} + \frac{\nu}{k - 2} \begin{pmatrix} 0 & U - V \\ V - U & 0 \end{pmatrix} \\  & = \begin{pmatrix} 1 & X \\ Y & 0 \end{pmatrix}  \end{aligned}

Where X-Y is a new coordinate system given by the linear transform:

\begin{pmatrix}X \\ Y \end{pmatrix} = \frac{1}{k - 2}\begin{pmatrix}k - 2 + \nu & - \nu \\ - \nu & k - 2 + \nu \end{pmatrix} \begin{pmatrix} U \\ V \end{pmatrix} + \frac{1}{k - 2}\begin{pmatrix}1 \\ - 1\end{pmatrix}

The effects of this coordinate transform on UV-space can be seen in the figure above for k = 3. The green region is where cooperation is the only evolutionary stable strategy, the red is where defection is the only ESS. The uncoloured regions have a fixed point of C-D dynamics; in the top right region of game space, the point is an attractor, in the bottom left it is a point of bifurcation. We can see that BD cannot create cooperation in the PD game, while DB creates a small slither on white where cooperation can co-exist with defection. In both conditions, we can see large effects for the Hawk-Dove game. In the non-transformed game, the only type of equilibria in HD is an attractive fixed point where cooperators and defectors co-exists. However, under both the BD and DB dynamics, regions of full cooperator and full defector dominance appear in the HD game. Similar for coordination games, usually there is only bifurcation around a fixed point, but under both BD and DB regions of all cooperators and all defectors appear. Thus, spatial structure can resolve the coordination equilibrium selection dilemma for some game parameters.

ResearchBlogging.org

Hilbe, C. (2011). Local replicator dynamics: a simple link between deterministic and stochastic models of evolutionary game theory. Bull Math Biol, 73: 2068-2097.

Ohtsuki H, & Nowak MA (2006). The replicator equation on graphs. Journal of Theoretical Biology, 243 (1), 86-97 PMID: 16860343

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).

Risk-dominance and a general evolutionary rule in finite populations

In coordination games, the players have to choose between two possible strategies, and their goal is to coordinate their choice without communication. In a classic game theory setting, coordination games are the prototypical setting for discussing the problem of equilibrium selection: if a game has more than one equilibrium then how do the players know which one to equilibrate on? The standard solution concept for this is the idea of a risk dominance. If you were playing a symmetric coordination game:

\begin{pmatrix}R & S \\ T & P \end{pmatrix}

where R > T and P > S, then how would you chose your strategy not knowing what your opponent is going to do? Since the two pure strategy Nash equilibria are the top left and bottom right corner, you would know that you want to end up coordinating with your partner. However, given no means to do so, you could assume that your partner is going to pick one of the two strategies at random. In this case, you would want to maximize your expected payoff. Assuming that each strategy of your parner is equally probably, simple arithmetic would lead you to conclude that you should chose the first strategy (first row, call it C) given the condition:

R + S > T + P

Congratulations, through your reasoning you have arrived at the idea of a risk dominant strategy. If the above equation is satisfied then C is risk dominant over D (the second strategy choice), more likely to be selected, and the ‘better’ Nash equilibrium.

Since many view evolutionary game theory as a study of equilibrium selection, it is not surprising to see risk-dominance appear in evolution. In particular, if the risk dominance condition is met, then (for a coordination game and replicator dynamics) C will have a larger basin of attraction than D. If we pick initial levels of cooperators at random, then in your well-mixed and extremely large population, the risk-dominant strategy will dominate the population more often. If you are feeling adventurous, then I recommend as exercise to calculate the exact probability of C dominating in this setting.

From our experience with ethnocentrism and discrete populations, we know that replicator dynamics is not the end of the story. The second step is to consider finite inviscid populations where we can’t ignore dynamical stochasticity. Kandari et al. (1993) studies this setting and for a population of size N concluded that C would be a more likely than D if:

R(N - 2) + SN > TN + P(N - 2)

Nowak et al. (2004) looked at this problem from the biological perspective of Moran processes. In a Moran process, there is no mutation, and thus the conclusion of dynamics is the absorbing state of either all C or all D. The quantity of interest becomes the fixation probability: the fixation probability of C is the probability that a single C mutant invades (leads to an all C absorbing state) a population of all D (vice-virsa for
fixation of D). Nowak et al. (2004) found that the fixation probability of C (in the weak selection limit) is higher than that of D in a population of N agents if and only if the above equation is satisfied.

Antal et al. (2009) concluded this research program. They showed that the above condition was necessary for the case of arbitrary mutations, a wide range of evolutionary processes, and any two player, two strategy game. It is true for pair-comparison (Fermi rule), exponential Moran processes, and weak-selection Moral processes with arbitrary mutation rates. In general, any update process that satisfies the two requirements: (i) additive payoffs, and (ii) evolutionary dynamics depend only on the payoff differences.

Let us visualize this result. As we learnt in a previous post we know that a two strategy cooperate-defect games do not need 4 parameters to specify, and can be rewritten with just two. The symmetry arguments we applied before preserve the authors’ result, so let’s apply the transformation:

\begin{pmatrix}R & S \\ T & P \end{pmatrix} \Rightarrow \begin{pmatrix}1 & U \\ V & 0 \end{pmatrix}

This lets us simplify the risk-dominance and finite population rules to:

1 > V - U \quad \text{and} \quad \frac{N - 2}{N} > V - U

Now it clear why we discussed risk-dominance before diving into finite populations. As the population size gets arbitrarily large (N \rightarrow \infty), our finite population rule reduces to risk-dominance and replicator dynamics. In the other extreme case is N = 2 (can’t have a game with smaller populations) the rule becomes U > V.

In the above picture of U-V space, we can see the two extreme conditions. In the green region, C is more likely than D for any population size, and in the blue it is true in the limit of infinite population. For particular N > 2 you get a different division line in the blue region parallel to the two current ones. Give a specific game in the blue region, you can calculate the threshold:

N^* = \frac{2}{1 - (V - U)}

For games in the blue region, if your population exceeds the N^* threshold then C with be more likely than D.

For those interested in the mathematical details, I recommend sections 2.3 and 4 of Antal et al. (2009). In particular, I enjoy their approach in section 2.3 of showing that when the game is on the dividing line then we have a symmetric distribution around N/2 and due to the well-behaved nature of deformations of the game matrix we can extend to the non knife-edge case. The only missing study in Antal et al. (2009) is a study of the second moment of the population. In regions 5, 9, and 10 we expect a bimodal distribution, and in 2-4 and 6-8 a unimodal. Can we use the probability of mutation to bound the distance between the peaks in the former, and the variance of the peak in the latter? Another exercise for the highly enthusiastic reader.

References

Antal, T., Nowak, M.A., & Traulsen, A. (2009). Strategy abundance in games for arbitrary mutation rates Journal of Theoretical Biology, 257 (2), 340-344 DOI: 10.1016/j.jtbi.2008.11.023

Kandori, M., Mailath, G.J., & Rob, R. (1993). Learning, mutation, and long run equilibria in games. Econometrica 61(1): 29-56.

Nowak, M.A., Sasak, A., Taylor, C., & Fudenberg, D. (2004). Emergence of cooperation and evolutionary stability in finite populations. Nature 428: 646-650.

EGT Reading Group 31 – 35

One of the main goals of TheEGG blog is to accompany the EGT Reading Group that I launched at McGill University in 2010. Last week, we had our 35th meeting. As such, this post is a reference to the papers we read since the last update (21-30).

2012
October 10 Roca, C.P., Cuesta, J.A., & Sanchez, A. [2009] “Evolutionary game theory: Temporal and spatial effects beyond replicator dynamics“. Physics of Life Reviews 6(4): 208-249.
September 19 Romero-Campero, F.J., Pérez-Jiménez, M.J. [2008] “A Model of the Quorum Sensing System in Vibrio fischeri Using P Systems.” Artificial Life 14(1): 95-109.
August 30 Karr, J.R., Sanghvi, J.C., Macklin, D.N., Gutschow, M.V., Jacobs, J.M., Bolival, B., Assad-Garcia, N., Glass, J.I., & Covert, M.W. [2012] “A whole-cell computational model predicts phenotype from genotype.” Cell, 150, 389-401 [Part 2]
August 23 Karr, J.R., Sanghvi, J.C., Macklin, D.N., Gutschow, M.V., Jacobs, J.M., Bolival, B., Assad-Garcia, N., Glass, J.I., & Covert, M.W. [2012] “A whole-cell computational model predicts phenotype from genotype.” Cell, 150, 389-401 [Part 1]
July 5 Fu, F., Tarnita, C.E., Christakis, N.A., Wang, L.,Rand, D.G., & Nowak, M.A. [2012] “Evolution of in-group favoritism.” Sci Rep. 2: 460.

Unfortunately we are not keeping up our optimal pace of one reading group per week, but we are continuing to meet semi-regularly. If you would like to participate, either in person, by G+ Hangout/skype, or just to get paper updated, then comment or send me an email and I will add you to the mailing list. If you have suggestions for papers that we should read and/or review on TheEGG then comment on this post with your ideas.

Slides for Roca, Cuesta & Sanchez’s EGT: Temporal and spatial effects beyond replicator dynamics

Last Wednesday, October 10th, 2012 we discussed Roca, Cuesta & Sanchez (2009) Evolutionary games theory: Temporal and spatial effects beyond replicator dynamics. The hope was to have a review as amazing as Szabo & Fath (2007), and we divided the work in a similar way.

  • Thomas Shultz presented Section 2: Basic concepts and results of evolutionary game theory.
  • Marcel Montrey presented Section 4: Structured populations.

I covered section 3 (The effects of different time scales) but without slides; I am still a fan of the blackboard. Tom’s slides provide an exposition of the basic model of the replicator equation, and closely follow Nowak’s Evolutionary Dynamics. I recommend these slides if you need a quick reminder. Unfortunately, the rest of the paper did not build on the equation (as you would expect from title) but provided (mostly) simulation based alternatives. Section 3 discussed the observation that having a different number of interactions per generation sets the speed of evolution. Evolution is fast is there are few interactions per generation, and slow otherwise. Fast evolution leads to more noise in the population, making it harder to stay in shallow optima. Unfortunately, they do not present cases where this results in a change of optima, like the low pairings we saw in Riolo, Cohen & Axelrod (2001). In his slides, Marcel does a great job of stressing the key insight RCS09 provide in section 4: the importance of update rules. The authors focus exclusively on simulation work, and point out the inconsistencies that can arise from seemingly minor changes in update rules. For the rest of the discussion of spatial structure, they do not go beyond Szabo & Fath and Marcel’s spatial structure post.

In all honesty, I was expecting a more analytic treatment from this Physics of Life Review, and was disappointed about the disconnect from the greatest strength of replicator dynamics: the intuitiveness of an analytic toolkit.

ResearchBlogging.org Carlos P. Roca, José A. Cuesta, & Angel Sánchez (2009). Evolutionary game theory: Temporal and spatial effects beyond replicator dynamics Physics of Life Reviews, 6, 208-249 arXiv: 0911.1720v1

Start of ethnocentric cooperation

Szabo & Fath attribute the first study of evolution of tag-based cooperation to Hales (2000); an unfortunate attribution for two reasons. First, Hales (2000) used tags in a way that is significantly different from the modern treatment. Instead of interacting with people regardless of tag, and then making a decision to cooperate or defect based on tag, the agents decided to interact or not based on tag. In Hales (2000), agents interact only with others of the same tag, thus it is simpler to think of the tags as loci on which agents live. This approach is more consistent with patch-structured or island models of the sort used by Taylor (1992). Cooperation in patch-structured models with limited dispersal was already well understood in biology by the time of Hales (2000). It was a lack of identification that these tags were patches and Hales publishing in computer science not biology that lead to the duplication of efforts. Second, if we admit this theme of tag-dependent interaction, then the first papers should be attributed to Holland (1993) & Riolo (1997). Holland (1993) outlined the mechanism in general and showed how to study it computationally, but did not run simulations. Riolo (1997) studied the mechanism through computer simulation (and some crude analytic approximations) for both iterated and single-shot prisoner’s dilemma. However, I prefer to think of these models as patches with limited dispersal and so do not consider them as the start of the current treatment of tag-based cooperation.

For me, the founding paper on ethnocentric cooperation is Riolo, Cohen & Axelrod (2001). Each agent is represented by two traits, a real number tag in [0,1] and a tolerance. The agents interact at random and a focal agent cooperates with every partner that has a tag within tolerance of the focal agent’s tag. Even with zero tolerance, an agent still cooperates with others of identical tag: an unconditional defector (or selfish agent in our terminology) is impossible. Therefore, the emergence of cooperation is not a surprising result but it is not the only result.

Population dynamics for the first 500 generations of a typical run. (a) is the proportion of cooperative interactions, and (b) is the average tolerance of the population. This is figure 1 from Riolo, Cohen, and Axelrod (2001), reproduced with permission from Nature Publishing Group.

The above figure shows the results of a typical run. In the top panel we have the proportion of cooperative interactions, and in the bottom — average tolerance. Note the cyclic behavior emphasized by the dotted lines. The population is initially populated by few agents of similar tag and low tolerance. This population is a phenotype-space (or tag) cluster and grows rapidly through cooperative interactions inside the cluster. As the cluster dominates the population, the selective pressure on low tolerance is relaxed and the cluster starts to do a random walk through tolerance space. Since there is a lower-bound on the tolerance (can’t be less than 0), the average starts to slowly increase. As the tolerance increases, a low tolerance mutant of slightly different tag appears. This focal mutant is within the large tolerance of the cluster, but most of the cluster’s agents are outside the focal agent’s tolerance. Thus, the focal agent defects from the cluster that continues to cooperate with him, feeding fitness to the focal’s progeny. As the focal agent’s low-tolerance progeny starts to grow, the rate of cooperation and tolerance drops in the population. When the focal mutant’s progeny grows to dominate the population, the cycle repeats. This cycle between emergence of cooperative tag-clusters and invasion by less tolerant defectors has been named chromodynamics by Jansen & van Baalen (2006).

Traulsen & Schuster (2003) were the first to carefully study this oscillatory behavior through an analytic treatment of a minimal variant of the RCA model. This paper was important not only for the aditional clarity it brought to chromodynamics, but also in its move towards discrete tags. Traulsen & Schuster eliminated the two real parameters of tag and tolerance, by having only two tags (Red & Blue) and two tolerances (0 and 1). In other words, they looked at a model with just ethnocentrics and humanitarians and paved the way for future work like our familiar Hammond & Axelrod model.

Beyond the oscillations, the RCA model displays a strange temporal structure effect. In the simulation, there are two events per generation that allow us to define a time-scale: interaction, and reproduction. Each generation is defined by a reproductive step, but before each reproductive step an agent is paired with some number of interaction partners at random to determine his fitness based on the interaction outcomes. As the number of pairing per generation is varied, we start to determine if evolution is fast or slow compared to interaction: fast if the number of pairing per generation is low, and slow otherwise. Usually, increasing the speed of evolution in this way only changes the noise and thus spread through phenotype-space of the population (Roca, Cuesta & Sanchez, 2009). In this case, however, a very high spread results in the impossibility of cooperation.

Mean proportion of cooperation versus number of pairing per generation. Generated with data from Table 1 of Riolo, Cohen, & Axelrod (2001).

The figure above shows the drastic transition in cooperation that happens between 2 and 3 pairings. Unfortunately, the authors do not carefully explain what causes this. Intuitively I expect that the fast evolution causes a very noisy fitness value at each generation, which promotes a diversity of tags and prevents a large cluster from forming. However, this needs to be tested in the model, and at first sight the small wiggle room (from 2 to 3) makes it seem difficult. However, we could consider fractional pairings like 2.1 by saying that with 90% probability an agent has twi pairings, and three with 10% probability. We might look at this more closely in a replication of the authors’ model in a future post.

References

Hales, D. (2000). Cooperation without space or memory: Tags, groups and the prisoner’s dilemma. In S. Moss & P. Davidsson (Eds.), Multi-Agent-Based Simulation, Lecture Notes in Artificial Intelligence (Vol. 1979, pp. 157-166). Berlin: Springer.

Holland, J. (1993). The effects of labels (tags) on social interactions. Santa Fe Institute Working Paper 93-10-064. Santa Fe, NM.
Jansen, V.A.A., & van Baalen, M. (2006). Altruism through beard chromodynamics. Nature, 440, 663-666.

Riolo, R. (1997). The effects of tag-mediated selection of partners in evolving populations playing the iterated prisoner’s dilemma. Santa Fe Institute Working Paper 97-02-016. Santa Fe, NM.

Riolo, R., Cohen, M., & Axelrod, R. (2001). Evolution of cooperation without reciprocity. Nature, 414 (6862), 441-443 DOI: 10.1038/35106555

Roca, C.P., Cuesta, J.A., & Sanchez, A. (2009). Evolutionary game theory: Temporal and spatial effects beyond replicator dynamics. Physics of Life Reviews 6, 208-249.

Taylor, P.D. (1992) Altruism in viscous populations – an inclusive fitness model. Evolutionary Ecology, 6(4), 352-356.

Traulsen, A., & Schuster, H.G. (2003). Minimal model for tag-based cooperation. Physical Review E, 046129.