Memes, compound strategies, and factoring the replicator equation

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.

Advertisements

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.

15 Responses to Memes, compound strategies, and factoring the replicator equation

  1. Reblogged this on CancerEvo and commented:
    Artem (with help from Robert Vander Velde and yours truly) has been working on a new model where three different types of players produce and consume two different types of public goods. Here he describes a neat trick to better handle this.

  2. Pingback: Cataloging a year of blogging: cancer and biology | Theory, Evolution, and Games Group

  3. Pingback: Double public goods games and acid-mediated tumor invasion | Theory, Evolution, and Games Group

  4. “if strategy 1 is some sort of defector and strategy 2 are different kinds of cooperators”

    I think this is a typo, strategy 1 and 2 are cooperators and 3 is a defector (at least in the scenario proposed), correct?

    • I don’t propose any scenario in this post. The post is suppose to stand largely on its own, so don’t let the similarity of letter choices here to the choices I made in our work mislead you. The main point is that if the dependence on p is eliminated (which actually doesn’t quiet happen in our work anymore, given that pesky 1 – p in the denominator) then the factored equation is very easy to analyze.

  5. Pingback: Symmetry in tag-based games & invariants under replicator dynamics | Theory, Evolution, and Games Group

  6. Pingback: From linear to nonlinear payoffs in the double public goods game | Theory, Evolution, and Games Group

  7. Pingback: Evolutionary dynamics of cancer in the bone | Theory, Evolution, and Games Group

  8. Pingback: Cataloging a year of blogging | Theory, Evolution, and Games Group

  9. Pingback: Lotka-Volterra, replicator dynamics, and stag hunting bacteria | Theory, Evolution, and Games Group

  10. Pingback: Acidity and vascularization as linear goods in cancer | Theory, Evolution, and Games Group

  11. Pingback: Hamiltonian systems and closed orbits in replicator dynamics of cancer | Theory, Evolution, and Games Group

  12. Pingback: Argument is the midwife of ideas (and other metaphors) | Theory, Evolution, and Games Group

  13. Pingback: Cataloging a year of cancer blogging: double goods, measuring games & resistance | Theory, Evolution, and Games Group

  14. Pingback: Ontology of player & evolutionary game in reductive vs effective theory | 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