Diversity working together: cancer, immune system, and microbiome →

Memes, compound strategies, and factoring the replicator equation

December 3, 2014 by Artem Kaznatcheev 16 Comments

When you work with evolutionary game theory for a while, you end up accumulating an arsenal of cute tools and tricks. A lot of them are obvious once you’ve seen them, but you usually wouldn’t bother looking for them if you hadn’t know they existed. In particular, you become very good friends with the replicator equation. A trick that I find useful at times — and that has come up recently in my on-going project with Robert Vander Veldge, David Basanta, and Jacob Scott — is nesting replicator dynamics (or the dual notion of factoring the replicator equation). I wanted to share a relatively general version of this trick with you, and provide an interpretation of it that is of interest to people — like me — who care about the interaction of evolution in learning. In particular, we will consider a world of evolving agents where each agent is complex enough to learn through reinforcement and pass its knowledge to its offspring. We will see that in this setting, the dynamics of the basic ideas — or memes — that the agents consider can be studied in a world of selfish memes independent of the agents that host them.

Factoring the replicator equation

If all you want to do is look but not touch then the replicator equation is rather pleasant:

$\dot{x_i} = x_i(f_i - \langle f \rangle)$

where $x_i$ is the proportion of your i-th basic (pure) strategy, $f_i$ is its fitness given the presence of all the other strategies (so typically a function of $\vec{x}$ ), and $\langle f \rangle = \sum_{i = 1}^n x_i f_i$ is the average fitness of all n strategies. However, once you’ve picked some specific functions for the $f_i$ , the n – 1 equations (we eliminate one because $\sum_{i = 1}^n x_i = 1$ and this is preserved by replicator dynamics) we just wrote down tend to get hairy. In practice, the $f_i$ you pick for specific games have various symmetries that this way of writing the dynamic system tends to obscure. Sometimes you can make these symmetries become useful for you by nesting replicator dynamics within replicator dynamics.

Let me be more precise.

Partition our n strategies into m sets $S_1, ..., S_j, ... , S_m$ such that each strategy appears in exactly one set (we can also do this with each strategy having a weight in all or some of the sets, with total mass 1, but it is a straightforward generalization that I will leave to the reader). To find the unique j such that $i \in S_j$ , I will define [i] := j. Now we will think of each set as a compound strategy j that is present in the population with proportion $Y_j = \sum_{i \in S_j} x_i$ . This compound strategy j is like a mixed strategy that with probability $y_{ij} = \frac{x_i}{Y_j}$ plays the i-th basic strategy. This should also explain the factoring terminology, since by rearranging, we have $x_i = y_{i[i]}Y_{[i]}$ Writing down the replicator dynamics for this gives us something with fewer equations:

$\dot{Y_j} = Y_j(F_j - \langle F \rangle)$

where $F_j$ is the is the fitness of the j-th compound strategy, given as you would expect for a mixed-strategy by $F_j = \sum_{i \in S_J} y_{ij}f_i$ . This has taken us down to m – 1 equations, but of course, each of the compound strategies now has its own internal dynamics which we will specify by another replicator equation for each j:

$\dot{y_{ij}} = y_{ij}(f_i - \langle f \rangle_j)$

where everything is as you would expect from previous notation, except $\langle f \rangle_j = \sum_{i \in S_j} y_i f_i$ is the average fitness over the set of basic strategies within our compound strategy. This gives us another $|S_j| - 1$ equations for each j and unsurprisingly when we look at all these equations $m - 1 + \big( \sum_{j = 1}^n |S_j| - 1 \big) = n - 1$ , we have the same number as in the unfactored case. What might come as a surprise — at least if I had refrained from giving away the punchline in my naming — is that the dynamics of these systems are exactly the same. To verify this — after noticing that $F_j = \langle f \rangle_j$ and $\langle F \rangle = \sum_j Y_j F_j = \sum_j Y_j \sum_{i \in S_j} y_{ij} f_i = \sum_j \sum_{i \in S_j} x_i f_i = \langle f \rangle$ — we just need a few lines of arithmetic:

$\begin{aligned} \dot{x_i} & = \frac{d}{dt}(y_{i[i]}Y_{[i]}) = \dot{y_{i[i]}}Y_{[i]} + y_{i[i]}\dot{Y_{[i]}} \\ & = y_{i[i]}Y_{[i]}(f_i - \langle f \rangle_{[i]}) + y_{i[i]}Y_{[i]}(F_{[i]} - \langle F \rangle) \\ &= x_i(f_i - \langle f \rangle) \end{aligned}$

Of course, knowing this factoring result will not necessarily help you, since sometimes there is no simplifying structure to extract by factoring your equations. However, it is a useful result to know, and I just wanted to sketch it here for reference. I won’t provide specific applications of this result in this post, but I’ll use it in a few forthcoming posts. However, there are still some general things of note.

Eliminating the simplex

If your game only has two strategies then there is nothing to factor. Let’s look at the next simplest case: three strategies. Normally, if you have three strategies, you can start to draw a pretty simplex, either on paper, your blackboard, or with a Mathematica package like Dynamo. If you are interested — as I often am — in the qualitative dynamics then you can even turn to Bomze (1983, 1995) for a classification of the 47 possible dynamic regimes. This might be too many regimes to look through or you might hate triangles. Alternatively, you might also like the elegant logistic-like form of 2 strategy replicator dynamics. In that case, factoring is the thing for you.

Suppose your original dynamics are given by:

$\begin{aligned} \dot{x_1} & = x_1(f_1 - (x_1f_1 + x_2f_2 + (1 - x_1 - x_2)f_3)) \\ \dot{x_2} & = x_2(f_2 - (x_1f_1 + x_2f_2 + (1 - x_1 - x_2)f_3)) \end{aligned}$

Let’s factor it into two groups $x_1$ and $x_2,x_3$ and let $p = x_1$ and $(1 - p)q = x_2$ then by applying the previous section we get the factored form:

$\begin{aligned} \dot{p} &= p(1 - p)(f_1 - (qf_2 + (1 - q)f_3)) \\ \dot{q} &= q(1 - q)(f_2 - f_3) \end{aligned}$

If your game then happens to have some nice structure like the function $f_2 - f_3$ being independent of p — as might be the case, for example, if strategy 1 is some sort of defector and strategy 2 are different kinds of cooperators; I’ll provide a concrete example with two public goods game in a future post — then your equation for q becomes completely decoupled from your equation for p. In such cases, the dynamics are much easier to analyze in this representation.

Re-interpreting replicator dynamics

I could leave the factorization as a cute and occasionally useful mathematical trick, but the draw for storytelling is too much for me to resist. It is much more fun to think of the compound strategies not as mere terminology or way to name sub-populations, but as agents in their own right that are playing a specific mixed strategy. The nice thing is that Bush & Mosteller’s (1951; see also Cross, 1973) model of reinforcement learning, when applied to playing games and looked at in the continuous time limit, is equivalent to replicator dynamics (Borgers & Sarin, 1997). Thus, the nested $y_{ij}$ replicator dynamics can be seen as the individual learning of complex agents. To connect to the top-level $Y_j$ replicator dynamics we need not just individual complex agents but a population of complex agents. However, we need the individual learning to not be lost, so we have to consider an inheritance mechanism like the posterior (or theory) passing considered in cultural ratchet theories (Beppu & Griffiths, 2009; Tennie et al., 2009).

Thus, we can think of the $y_{ij}Y_j$ factored equation as describing a population of complex agents of m different types, with an agent of type j playing a mixed strategy over the set $S_j$ of pure strategies. After each interaction, the agent updates its beliefs about the quality of its pure strategies according to Bush & Mosteller’s (1951) reinforcement learning. Each agent reproduces in proportion to their payoff, and upon reproduction passes on its knowledge on the effectiveness of its strategies to its offspring. The fact that the factored equation describes the same dynamics as the unfactored $x_i$ equations, means that we can also ignore the agents and just think about this as a world of memes competing against each other — just like we can often ignore individual organisms and just think about a world of competing genes. Unfortunately, to achieve this effect we had to ignore subjective representations and other factors that can distinguish learning and evolution.

But, It is still fun to imagine such a world of selfish memes. I suspect it would look something like this:

References

Beppu, A., & Griffiths, T. L. (2009). Iterated learning and the cultural ratchet. In Proceedings of the 31st Annual Conference of the Cognitive Science Society (pp. 2089-2094). Austin, TX: Cognitive Science Society.

Bomze, I. M. (1983). Lotka-Volterra equation and replicator dynamics: a two-dimensional classification. Biological Cybernetics, 48(3): 201-211.

Bomze, I. M. (1995). Lotka-Volterra equation and replicator dynamics: new issues in classification. Biological Cybernetics, 72(5): 447-453.

Börgers, T., & Sarin, R. (1997). Learning through reinforcement and replicator dynamics Journal of Economic Theory, 77 (1), 1-14 DOI: 10.1006/jeth.1997.2319

Bush, R. R., & Mosteller, F. (1951). A mathematical model for simple learning. Psych. Rev., 58: 313-323.

Cross, J.G. (1973). A stochastic learning model of economic behavior. Quart. J. Econ., 87: 239-266.

Tennie, C., Call, J., & Tomasello, M. (2009). Ratcheting up the ratchet: on the evolution of cumulative culture. Philosophical Transactions of the Royal Society B: Biological Sciences, 364(1528): 2405-2415.

Filed under Analytic, Models, Preliminary, Technical Tagged with cognitive science, economics, fitness ontology, learning, replicator dynamics, video

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.