Symmetry in tag-based games & invariants under replicator dynamics

Mathematicians and physicists love finding symmetries. The reason is simple: symmetries make life easier. The situation is no different when studying the evolutionary dynamics of life. If the fitness functions of your organisms have some symmetry or other nice structure then you can usually exploit it to make analyzing your replicator equations easier. In this post, I want to show an example of this in tag-based models. This analysis is an essential base case when building more complicated models of ethnocentrism — like our work in the Hammond and Axelrod model — and I have been meaning to write about it for a while. This will give me a chance to show a concrete example where my method for factoring the replicator equation is useful, and how observing a straighforward symmetry can reduce the dimensionality of a problem. Maybe this exercise will also teach us something about the evolution of ethnocentrism.

So, what is a tag-based game? In complexity it is one step above the simplest models of evolutionary game theory. For the simplest models the agents’ strategies are fixed by their genetics and correspond to a constant behavior. Tag-based models lengthen the chain from gene to behavior by considering strategies that condition on an arbitrary tag or label of the interacting partner. Consider a focal agent Alice interaction with another agent Bob. If Alice and Bob have the same tag then Alice will do one constant behavior (her in-group behavior), and if Alice and Bob have a differing tag then Alice will do a second constant behavior (her out-group behavior); the two behaviors might be the same, but need not be. The possible organisms are then all the combinations of in-group behavior, out-group behavior, and tag. This introduces a combinatorial structure and that is what I will exploit.

From symmetry to invariant

For concreteness, consider a tag-based model where there are:

  • two possible in-group behaviors — call them C_\text{in} and D_\text{in},
  • two possible out-group behaviors — C_\text{out} and D_\text{out}, and
  • a finite numbers n of tags; if you need a concrete number then imagine n = 2.

If you wrote down the replicator equations at this point then you would 4n – 1 coupled ODEs. Translation: too much of a mess for me. Let us clean the mess up a bit with a factorization that isolates just the four strategies with tag k. Let s_k be the proportion of organisms with tag-k in the overall population. Now, we will name the four different behavioral profiles (or strategies) with tag-k according to our usual scheme:

  • Humanitarians are agents that have behaviors C_\text{in} and C_\text{out} — they cooperate with both the in- and out-group — and the proportion of them among the tag-k organisms is p^H_k. Thus, their fitness is f^H_k = f_k(C_\text{in}) + f_k(C_\text{out}) where f_k(\circ) is the utility or fitness effect for a focal agent of tag-k when using the constant behavior of the function’s argument “\quad\circ\quad“. Note that, in the general case, f_k returns a function that depends on the current state of the population.
  • Ethnocentrics: (C_\text{in}, D_\text{out})p^E_kf^E_k = f_k(C_\text{in}) + f_k(D_\text{out}).
  • Traitorous: (D_\text{in}, C_\text{out})p^T_kf^T_k = f_k(D_\text{in}) + f_k(C_\text{out}).
  • Selfish: (D_\text{in}, D_\text{out})p^S_kf^S_k = f_k(D_\text{in}) + f_k(D_\text{out})
  • .

As with all replicator dynamics, we have the conserved quantity p^H_k + p^E_k + p^T_k + p^S_k = 1. But these particular fitness functions have a further symmetry: f^H_k + f^S_k = f^E_k + f^T_k. This leads to the replicator dynamics internal to tag-k to have a further conserved quantity: \frac{d}{dt}(p^H_kp^S_k) = 0 = \frac{d}{dt}(p^E_kp^T_k). If you’re eager, dear reader, then I encourage you to verify this as an exercise.

This conservation means, for example, if we initialize our population with p^E_k(0)p^T_k(0) = \kappa then at all further time t, we will continue to have p^E_k(t)p^T_k(t) = \kappa. This will hold for each tag. Every increase in the proportion of ethnocentrics with a given tag is counterbalanced by a corresponding decrease in the proportion of traitorous agents with that tag and same with humanitarians and selfish agents. This is something I would not have guessed without looking for symmetries. It also throws a wrinkle into typical stories about which strategies “suppresses” which. Consider a typical situation where you initiate your dynamics — as is usual — with a uniform distribution over strategies, so p^H_k(0) = p^E_k(0) = p^T_k(0) = p^S_k(0). Now suppose that at a future time t you notice that p^E_k(t) > p^H_k(t) then it follows that p^T_k(t) < p^S_k(t) and observing that second relationship is as interesting as observing that p^H_k(t) + p^E_k(t) + p^T_k(t) + p^S_k(t) = 1 still. This also means that when we use an explanation like “ethnocentric directly suppress humanitarians”, in the inviscid model it would be causally indistinguishable from “selfish agents are harder to suppress than (or directly suppress) traitorous agents”. Which isn’t intuitively surprising, given that the difference between ethnocentrics and humanitarians is exactly the same as the difference between selfish and traitorous agents. But this is not something that we’ve discussed explicitly in our earlier work.

Factoring to reduce dimensionality

The biggest benefit of this conserved charge, however, is not in clarifying our explanatory narrative. Nor is it pointing out alternative explanations. The biggest benefit is that we can reduce the number of ODEs needed to fully describe the dynamics within tag-k. If we didn’t have our symmetry then we would need 3 coupled equations, but we can exploit the structure to reduce it to just 2 equations that are much more decoupled. The exact extent of the decoupling will depend on what we choose to be our game; i.e. the form of f_k(\circ). For most natural choices of f_k(\circ) — such as the ones I used in my previous work — the decoupling will be nearly complete.

Again, I will use my factoring trick. But instead of the usual nesting of factored equations — which would only simplify life if the initial conditions respect a similar symmetry to the dynamics — I will consider two independent factorings and then link them through the conserved charge. First, we will group humanitarians with ethnocentrics and traitors with selfish, to give us the dynamics for p^\text{in}_k := p^H_k + p^E_k. Second, we will instead group humanitarians with traitors and ethnocentrics with selfish, to give us the dynamics for p^\text{out}_k := p^H_k + p^T_k. See the figure below for a visualization of this factorization. The first grouping corresponds to the solid circles, and the second to the dashed.

A visualization of how the 4n strategies are partitioned The big square boxes correspond to the firs

A visualization of how the 4n strategies are partitioned. The big square boxes correspond to the first factorization, into the n tags. Inside each tag, I color-coded the 4 behavioral profiles: [H]umanitarian, [E]thnocentric, [T]raitorous, and [S]elfish. We factorize further in one of two ways: either into the solid circle grouping for p^\text{in}_k, or the dashed circle grouping for p^\text{out}_k.

Normally, p^\text{in}_k and p^\text{out}_k would not be sufficient to recover unambiguously all of p^H_k, p^E_k, p^T_k, p^S_k. But since p^E_kp^T_k = \kappa = p^E_k(0)p^T_k(0) is conserved and probabilities sum to one, we can invert the equations to get:

\begin{aligned}   p^E_k & \leftarrow \frac{\sqrt{(p^\text{in}_k - p^\text{out}_k)^2 + 4\kappa} - (p^\text{in}_k - p^\text{out}_k)}{2}, \\   p^H_k & \leftarrow p^\text{in}_k - p^E_k, \\  p^T_k & \leftarrow \frac{\kappa}{p^E_k}, \\  p^S_k & \leftarrow 1 - p^H_k - p^E_k - p^T_k.  \end{aligned}

Further, we can recombine our conserved quantities to notice other ones, like \Delta_k = p^H_kp^S_k - p^E_kp^T_k. This allows us to write down the equations governing p^\text{in}_k and p^\text{out}_k in an elegant form:

\begin{aligned}  \frac{dp^\text{in}_k}{dt} & = p^\text{in}_k(1 - p^\text{in}_k)(f_k(C_\text{in}) - f_k(D_\text{in})) + \Delta_k(f_k(C_\text{out}) - f_k(D_\text{out})), \\  \frac{dp^\text{out}_k}{dt} & = p^\text{out}_k(1 - p^\text{out}_k)(f_k(C_\text{out}) - f_k(D_\text{out})) + \Delta_k(f_k(C_\text{in}) - f_k(D_\text{in})).  \end{aligned}

These are true for any initial conditions, and any game structure f_k. In the case of initial conditions that respect the extra symmetry of \Delta = 0, as would be the case for a uniform start, then the equations become simple two-strategy replicator dynamics.

Of course, there is nothing special about tag-k and the equations hold for each tag. In general, with n tags, this results in a reduction of number of equations from 4n – 1 to 3n – 1. With 2n of them having the slightly deformed sigmoidal form of the above two equations and the other n – 1 describing the change in the proportion of the tags. The proportion of tags change according to the equation:

\frac{ds_k}{dt} = s_k(p^\text{in}_k f_k(C_\text{in}) + (1 - p^\text{in}_k) f_k(D_\text{in}) + p^\text{out}_k f_k(C_\text{out}) + (1 - p^\text{out}_k) f_k(D_\text{out}) - \langle f \rangle)

where \langle f \rangle is the average fitness of the whole population.

Of course, this is useful not only as a practical trick. It also lets you reason about the dynamics more easily. The decoupling tells you that the in-group strategy and the out-group strategy are evolving (to some extent) independently, and it tells you that the more natural representation of the population is not the proportion of humanitarians, ethnocentrics, traitorous, and selfish agents but the proportion of in-group cooperators and the proportion of out-group cooperators. For example, it helps to better understand my early work on probabilistic strategies in tag-based games, the representation I used for the videos, and why the simulations did not yield qualitatively different results from the deterministic strategies.

Analysis of internal equilibria becomes simpler in this representation. For example, if we just analyzed the in-group and out-group games separately, we would expect an internal equilibrium when f_k(C_\text{in}) = f_k(D_\text{in}) and f_k(C_\text{out}) = f_k(D_\text{out}) — remember, these are functions of the overall population — and this is exactly what we get for the whole dynamics, even when \Delta_k \neq 0 in the initial conditions. Unfortunately, when \Delta_k \neq 0, we get a slight wrinkle of having a potential extra equilibrium that we might not have expected from a simple separation. However, if our game f_k is linear in all the strategies, as is the case for the most commonly considered matrix games, then we know a second internal equilibrium cannot exist, and the wrinkle disappears.

I apologize for the birds-eye view and level of generality in this post, but I promise to make it worth your while in the coming weeks. In follow up posts, I will consider specific functional forms for f_k to (1) see when tags are stable, or when one tag sweeps the population; and (2) how finite sampling and spatial structure affects the robustness of ethnocentrism.


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.

2 Responses to Symmetry in tag-based games & invariants under replicator dynamics

  1. Pingback: Diversity of group tags under replicator dynamics | Theory, Evolution, and Games Group

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your 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