# Pairwise games as a special case of public goods

Usually, when we are looking at public goods games, we consider an agent interacting with a group of n other agents. In our minds, we often imagine n to be large, or sometimes even take the limit as n goes to infinity. However, this isn’t the only limit that we should consider when we are grooming our intuition. It is also useful to scale to pairwise games by setting n = 1. In the case of a non-linear public good game with constant cost, this results in a game given by two parameters $\frac{\Delta f_0}{c}, \frac{\Delta f_1}{c}$ — the difference in the benefit of the public good from having 1 instead of 0 and 2 instead of 1 contributor in the group, respectively; measured in multiples of the cost c. In that case, if we want to recreate any two-strategy pairwise cooperate-defect game with the canonical payoff matrix $\begin{pmatrix}1 & U \\ V & 0 \end{pmatrix}$ then just set $\frac{\Delta f_0}{c} = 1 + U$ and $\frac{\Delta f_1}{c} = 2 + V$. Alternatively, if you want a free public good (c = 0) then use $\Delta f_0 = U$ and $\Delta f_1 = 1 - V$. I’ll leave verifying the arithmetic as an exercise for you, dear reader.

In this post, I want to use this sort of n = 1 limit to build a little bit more intuition for the double public good games that I built recently with Robert Vander Velde, David Basanta, and Jacob Scott to think about acid-mediated tumor invasion. In the process, we will get to play with some simplexes to classify the nine qualitatively distinct dynamics of this limit and write another page in my open science notebook.

Let us recall our utility functions from the earlier post, remembering that U(- +) can be eliminated because it is strictly dominated by U(- -):

\begin{aligned} U(--) & = \sum_{n_1 + n_2 + n_3 = n} {n \choose n_1, n_2, n_3} x_1^{n_1}x_2^{n_2}x_3^{n_3} m_{n_1 + 1} \\ U(++) & = \sum_{n_1 + n_2 + n_3 = n} {n \choose n_1, n_2, n_3} x_1^{n_1}x_2^{n_2}x_3^{n_3} ( m_{n_1} + f_{n_2 + 1}) - c \\ U(+-) & = \sum_{n_1 + n_2 + n_3 = n} {n \choose n_1, n_2, n_3} x_1^{n_1}x_2^{n_2}x_3^{n_3} ( m_{n_1} + f_{n_2}) \end{aligned}

Where – – are anaerobic (thus acid-secreting) cells that don’t produce VEGF, and the other two are aerobic with + + producing VEGF and + – only using oxygen but not producing VEGF.

Looking at the n = 1 case, our utility functions (or the cells’ fitnesses, if you prefer) simplify to:

\begin{aligned} U(--) & = x_1m_2 + (x_2 + x_3)m_1 \\ U(++) & = x_1(m_1 + f_1) + x_2(m_0 + f_2) + x_3(m_0 + f_1) - c \\ U(+-) & = x_1(m_1 + f_0) + x_2(m_0 + f_1) + x_3(m_0 + f_0) \end{aligned}

Which can be rewritten in payoff matrix form (renormalized by subtracting $m_1$ from all lines) as:

$\begin{pmatrix} \Delta m_1 & 0 & 0 \\ f_1 - c & f_2 - \Delta m_0 - c & f_1 - \Delta m_0 - c \\ f_0 & f_1 - \Delta m_0 & f_0 - \Delta m_0 \end{pmatrix}$

To recreate the qualitative features of our original description of acid, we want $\Delta m_0 > \Delta m_1$. For oxygen as a public good, we want it to be positive and monotonically increasing ($0 < f_0 < f_1 < f_2$) and saturating ($\Delta f_0 > \Delta f_1$ > 0).

From looking at the equations, we can notice several things right away:

1. U(- -) is strictly dominated by U(+ +) if $\Delta m_0 < f_1 - c$, otherwise
2. U(+ +) is strictly dominated by U(- -) if $\Delta m_1 > f_2 - c$.
3. U(- -) is strictly dominated by U(+ -) if $\Delta m_0 < f_0$, otherwise
4. U(+ -) is strictly dominated by U(- -) if $\Delta m_1 > f_1$.
5. U(+ +) is strictly dominated by U(+ -) if $\Delta f_0 < c$, otherwise
6. U(+ -) is strictly dominated by U(+ +) if $\Delta f_1 > c$.

Since we are more interested in cases where no strategy is strictly dominated, we can concentrate on the cases where $\Delta f_1 < c < \Delta f_0$ and $\Delta m_0 > f_1 - c > f_0$ and $\Delta m_1 < f_2 - c < f_1$. The first of these conditions results in the simplex edge between ++ and +- having Hawk-Dove dynamics and thus an attracting equilibrium point on that edge with an equilibrium proportion of ++ given by $q^* = \frac{\Delta f_0 - c}{\Delta f_0 - \Delta f_1}$. Combined with all our other inequalities, q* has a useful property: $f_1 - c < f_0 + q^*\Delta f_0 < f_2 - c$. Finally, if $\Delta m_0 > f_0 + q^*\Delta f_0$ then – – can invade a population made up completely of + + and + – and so the equilibrium is a saddle-point, otherwise it is stable.

Let’s look at the games on the other two edges:

$\begin{pmatrix}\Delta m_1 & 0 \\ f_1 - c & f_2 - \Delta m_0 - c \end{pmatrix}, \begin{pmatrix} \Delta m_1 & 0 \\ f_0 & f_0 - \Delta m_0 \end{pmatrix}$

From this we can conclude that:

1. If $\Delta m_1 > f_1 - c$ then – – is evolutionary stable against + +.
2. If $\Delta m_0 < f_2 - c$ then + + is evolutionary stable against – –.
3. If $\Delta m_1 > f_0$ then – – is evolutionary stable against + –.
4. If $\Delta m_0 < f_0$ then + – is evolutionary stable against – –, but this contradicts a previous condition that $\Delta m_0 > f_1 - c > f_0$.

This gives us the 6 distinct edge-profiles of the simplex. In fact, 2 of them are equivalent: by relabeling (- -, + +, + -) as (+ -, – -, + +) we can move from the $\Delta m_0 < f_2 - c$ and $\Delta m_1 < f_0$ profile to the $\Delta m_0 > f_2 - c$ and $f_0 < \Delta m_1 < f_1 - c$ profile. By consulting Bomze (1983,1995) and playing with the inequalities that we’ve derived so far, we can see that there are 9 distinct regimes possible depending on the values of $\Delta m_0$ and $\Delta m_1$. The simplexes for the qualitative nature of these dynamics are gives below:

The 9 possible dynamic regimes for the n = 1 limit of the double public good game for acid-mediated tumor invasion. The possible parameter settings for $\Delta m_0$ are varied vertically, and horizontally for $\Delta m_1$. Each of the 9 simplexes has the same coordinates, with the top vertex corresponding to all – –, left to all + +, and right to all + –. Solid white circles correspond to stable equilibrium points, and unfilled white circles correspond to unstable equilibria or saddle-points. The black numbers, correspond to the numbers of dynamic regimes from figure 6 of Bomze (1983); -36 means the 36th dynamics with flow reversal. Note that I made a write-o on the blackboard and the purple text in the top right corner should read $\Delta m_1$ just like the blue and cyan.

From the above, we can see that:

• if $\Delta m_0 < f_0 + q^* \Delta f_0$ and $\Delta m_1 < f_1 - c$ then no matter where the cancer starts, its dynamics will converge to a polyclonal tumor expressing all three of – –, + +, and + –. During the convergence, we will see cyclic behavior.
• If $\Delta m_1 > f_1 - c$ then it will be possible for the tumour to converge to a homogeneous state made of only – – cells — not producing VEGF or using oxygen — but
• this happens for any initial conditions only if $\Delta m_0 < f_0 + q^*\Delta f_0$;
• otherwise if $\Delta m_0 > f_0 + q^*\Delta f_0$ then there are two basins of attraction with the top basin leading to all – – but the bottom one leading to a fully aerobic but still polyclonal tumor with q* of the cells producing VEGF and the rest only benefiting from the delivered oxygen.
• If $\Delta m_0 > f_2 - c$ and $f_0 < \Delta m_1 < f_1 - c$ then we will have probably the strangest case, with two basins of attraction. One bottom basin will result in a completely aerobic but heterogeneous in VEGF tumour as in the previous point. The top basin, however, will result in a heterogeneous tumour with a mix of anerobic cells and aerobic VEGF producers, but no aerobic VEGF non-producers.
• In all other cases, all initial configurations will lead to an aerobic but heterogeneous in VEGF tumour.

I am not sure which of these possible equilibria are clinically desirable, but I would guess that the completely polyclonal tumour of the first point is the worst possible. On the other hand, a completely aerobic tumour — even if heterogeneous in VEGF production — seems manageable if there is some external way to cut off its oxygen supply. Although this sort of treatment would require a more involved analysis since cutting off the oxygen supply would change $f_0, f_1, f_2$ and thus the game dynamics. Finally, a completely homogeneous tumour of – – although undergoing the Warburg shift would be tempting to treat with a targeted therapy due to having a single opponent instead of two or three. Of course, I am hoping that Robert, David, Jake, or you, dear reader, will pitch in with more biological considerations.

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

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

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.

### 11 Responses to Pairwise games as a special case of public goods

1. Jon Awbrey says:

I often think of capitalism as a kind of invasive tumor.

2. James N Rose says:

Have you ever read/considered the ‘decision making’ theory of Vladimir Lefebvre? Or the extended complication of dis-information ? Or the extended complication of “adequate vs required” win-state criteria? Or the introduction of data loss that erodes or modifies your entire prior math-lineage basis?

3. “I am not sure which of these possible equilibria are clinically desirable, but I would guess that the completely polyclonal tumour of the first point is the worst possible.”

I think it depends, glycolytic cells might be more invasive. Polyclonal (in terms of these subclones) tumors might not be that bad if treatments can be used to shift the equilibrium periodically and consequently create population bottlenecks in each subpopulation (this in turn would reduce diversity within them and make drug resistant clones less plentiful).

4. Since we have a matrix (for n=1 of course), might it be worth using the ON-transform on it to see how important space might be?

• I wouldn’t bother right now. At least not until after we understood the 9 regimes that we already have. We already have a very wide range of possibilities, ON transform is just going to widen and complicate them without suggesting any new question that we should ask. I am not a fan of adding complications without a clear motivation for why.

Also, given that we are playing with oxygenation, the more important aspects of space is how the game changes (or the ambient levels of oxygen change) as we move towards and away from blood-vessels. This is not something that the ON-transform is equipped to handle. This might be fun to play with in a spherical tumour model later.

5. Do you know of any public goods games that when boiled down to pairwise games have a fundamentally different result? Since voluntary public goods games boil down to RPS, etc. it seems there aren’t too many fundamental differences (in terms of results).

• That is a good question, Robert. I am not 100% sure of the answer, but I’ll leave some thoughts here.

First, I am not sure if the “boiling down to pairwise games” is a standard procedure. I thought it was original to me, but if lots of others have done it explicitly then do leave some references!

As for fundamental differences, it really depends on what you consider to be fundamental and on how inclusive you make “pairwise games”. For me, the goal in this post was to reduce to a matrix game, in particular. Matrix games are easy to work with, but with that ease comes a limitation in expressiveness. In particular, matrix games are easy to analyze because finding their equilibrium is just the solution of a system of linear equations. But this is also the limitations, it means that you either have no internal fixed point, a single internal fixed point, or a bigger linear subspace. You cannot have two unconnected internal fixed points, for example.

This means results like Archetti’s two strategy non-linear games that have two internal fixed points (one stable and one unstable) are not expressible as the solution of a two strategy matrix game.

However, the above is a limitation of the linearity (different from linear PG, same name unfortunately) of matrix-gameness and not a limitation pair-wiseness. Since you could consider pairwise interactions that are not representable by a matrix game. In that case, pairwise replicator dynamics are fully general, and any other replicator dynamics will fall under them. However, you can leave replicator dynamics to make the group size relevant. One way is to look at group structure explicitly:

Killingback, T., Bieri, J., & Flatt, T. (2006). Evolution in group-structured populations can resolve the tragedy of the commons. Proceedings of the Royal Society B: Biological Sciences, 273(1593), 1477-1481.

and the other is something like the ecological public-good:

Hauert, C., Wakano, J. Y., & Doebeli, M. (2008). Ecological public goods games: cooperation and bifurcation. Theoretical Population Biology, 73(2), 257.

As I mention in the above-linked post, I think that both of those extract cooperation using the same mechanism: interaction group size dipping below the multiplicative factor of the (linear) public good. Just to state that you need the ability to vary interaction group size, so you would not be able to get that from pairwise games.

I hope that helps!

This site uses Akismet to reduce spam. Learn how your comment data is processed.