Spatializing the Go-vs-Grow game with the Ohtsuki-Nowak transform

Recently, I’ve been thinking a lot about small projects to get students started with evolutionary game theory. One idea that came to mind is to look at games that have been analyzed in the inviscid regime then ‘spatialize’ them and reanalyze them. This is usually not difficult to do and provides some motivation to solving for and making sense of the dynamic regimes of a game. And it is not always pointless, for example, our edge effects paper (Kaznatcheev et al, 2015) is mostly just a spatialization of Basanta et al.’s (2008a) Go-vs-Grow game together with some discussion.

Technically, TheEGG together with that paper have everything that one would need to learn this spatializing technique. However, I realized that my earlier posts on spatializing with the Ohtsuki-Nowak transform might a bit too abstract and the paper a bit too terse for a student who just started with EGT. As such, in this post, I want to go more slowly through a concrete example of spatializing an evolutionary game. Hopefully, it will be useful to students. If you are a beginner to EGT that is reading this post, and something doesn’t make sense then please ask for clarification in the comments.

I’ll use the Go-vs-Grow game as the example. I will focus on the mathematics, and if you want to read about the biological or oncological significance then I encourage you to read Kaznatcheev et al. (2015) in full.

Transform the game

First things first, let’s write down the game matrix that we are considering:

\bordermatrix{ ~ & \text{INV} & \text{AG} \cr  \text{INV} & \frac{1}{2}b + \frac{1}{2}(b - c) & b - c \cr  \text{AG} &	b & \frac{1}{2}b \cr  }

Here, the two strategies are invasive (INV) and autonomous growth (AG). We can consider as each player choosing one of these two strategies. Player 1 picks the row, and player 2 picks the column. The resulting matrix entry is the payoff for Player 1.

Now we can go to Ohtsuki & Nowak (2006) or — even easier — my old blog post, and look up the spatializing transform. This will change the game matrix we described above into a new matrix corresponding to the effective game of playing Go-vs-Grow on a random graph.

Given an arbitrary game matrix A one can compute the Ohtsuki-Nowak (ON) transform as follows:

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

where \vec{1} is the all ones vector, \vec{\Delta} is a column vector containing the diagonal of the game matrix A = [a_{ij}] (i.e. \vec{\Delta}_i = a_{ii}), \vec{\Delta}^T is its transpose (a row vector), and k > 2 is the number of neighbours that each agent has.

In the case of the Go-vs-Grow game, \vec{\Delta}^T = (b - c/2,\; b/2). Thus, the second summand of the transform is:

\begin{aligned}  \frac{1}{k-2}(\vec{\Delta}\vec{1}^T - \vec{1}\vec{\Delta}^T) & = \frac{1}{k-2}(\begin{pmatrix}b - c/2 \\ b/2\end{pmatrix}\begin{pmatrix}1 & 1\end{pmatrix} - \begin{pmatrix}1 \\ 1\end{pmatrix} \begin{pmatrix}b - c/2 & b/2\end{pmatrix}) \\  & = \frac{1}{k-2}(\begin{pmatrix}b - c/2 & b - c/2 \\ b/2 & b/2\end{pmatrix} - \begin{pmatrix}b - c/2 & b/2 \\ b - c/2 & b/2\end{pmatrix}) \\  & = \frac{1}{k-2}\begin{pmatrix} 0 & b/2 - c/2 \\ c/2 - b/2 & 0 \end{pmatrix} \\  & = \begin{pmatrix} 0 & \frac{b - c}{2(k - 2)} \\ -\frac{b - c}{2(k - 2)} & 0 \end{pmatrix}  \end{aligned}

Repeating similar arithmetic — a little faster this time — for the third summand:

\begin{aligned}  \frac{1}{(k + 1)(k-2)}(A - A^T) & = \frac{1}{(k + 1)(k-2)}(\begin{pmatrix}b - c/2 & b - c \\ b & b/2\end{pmatrix} - \begin{pmatrix}b - c/2 & b \\ b - c & b/2\end{pmatrix}) \\  & = \begin{pmatrix}0 & -\frac{c}{(k + 1)(k-2)} \\ \frac{c}{(k + 1)(k-2)} & 0\end{pmatrix}  \end{aligned}

Putting everything together, we get:

\begin{aligned}  \text{ON}_k(\begin{pmatrix}b - c/2 & b - c \\ b & b/2\end{pmatrix})   & = \begin{pmatrix}b - c/2 & b - c \\ b & b/2\end{pmatrix}   + \begin{pmatrix} 0 & \frac{b - c}{2(k - 2)} \\ -\frac{b - c}{2(k - 2)} & 0 \end{pmatrix}  + \begin{pmatrix}0 & -\frac{c}{(k + 1)(k-2)} \\ \frac{c}{(k + 1)(k-2)} & 0\end{pmatrix} \\  & = \begin{pmatrix}  b - \frac{\displaystyle c}{\displaystyle 2}   & b\frac{\displaystyle 2k - 3}{\displaystyle 2(k - 2)} - c\frac{\displaystyle 2k^2 - k - 1}{\displaystyle 2(k - 2)(k + 1)} \\  b\frac{\displaystyle 2k - 5}{\displaystyle 2(k - 2)} + c\frac{\displaystyle k + 3}{\displaystyle 2(k - 2)(k + 1)}   & \frac{\displaystyle b}{\displaystyle 2}  \end{pmatrix}.  \end{aligned}

Where I left the arithmetic of having all fractions with a common denominator and grouping as an exercise for the reader.

Analyze the transformed game

Now that we have transformed the game, we have a new game matrix to analyze. Its analysis follows the same procedure as for any other 2 strategy game. This analysis is only slightly more complicated than for the untransformed Go-vs-Grow game due to the more complicated entries in the transformed matrix.

Let’s remind ourselves how to do such an analysis in general given an arbitary game matrix:

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

Assuming, for simplicity, that R > P. (We could simplify further if we wanted, but let’s stick to this represantion for clarity.)

If the proportion of the first strategy is x (and thus the proportion of the second strategy is 1 – x) then this results in the following two payoff functions (U) for the first strategy (C) and second strategy (D):

\begin{aligned}  U(C) &= xR + (1 - x)S \\  U(D) &= xT + (1 - x)P  \end{aligned}

Now, whenever U(C) > U(D), the first strategy will be doing better so its proportion x in the population will increase; and vice-versa, if U(C) < U(D) then the second strategy will be doing better so x will decrease. At equilibrium, we would need to have U(C) = U(D). Let’s use this condion to solve for what value x would need to be at equilibrium (if one exists):

\begin{aligned}  xR + (1 - x)S & = xT + (1 - x)P \\  x(R - S) + S &= x(T - P) + P \\  x(R - S - T + P) = P - S \\  x = \frac{P - S}{R - S - T + P}  \end{aligned}

We can also use these fitness functions to check if either C or D are an evolutionary stable strategy. For C to qualify, it needs to not be invadable by a rare mutant D; i.e. we need U(C) > U(D) at x = 1. By plugging x = 1 into our utility functions, we see that this happens when R > T. Similarily for D to be evolutionary stable, we need U(D) > U(C) at x = 0, which translates into P > S.

If neither C nor D are evolutionary stable then R < T and P < S, thus R – S – T + P = (P – S) + (R – T) <P – S < 0; so the equilibrium x exists. On the other hand, if both C and D are evolutionary stable then R > T and P > S then R – S – T + P > P – S > 0, and so the equilibrium x exists. Therefore, 4 regimes are possible: either one of C or D is evolutionary stable; both are unstable and the population converges to the stable equilibrium x; or both are stable and the population bifurcates around the unstable equilibrium x.

Let’s use this to analyze our transformed game. First, we check that P > R holds for our game. This is clearly the case whenever b > c, so let us focus on that regime (that also happens to be the only biologically interesting case). INV will be evolutionary stable whenever we have R > T:

\begin{aligned}  b - \frac{\displaystyle c}{\displaystyle 2} & > b\frac{\displaystyle 2k - 5}{\displaystyle 2(k - 2)} + c\frac{\displaystyle k + 3}{\displaystyle 2(k - 2)(k + 1)}  \\  & \vdots \\  \frac{k + 1}{k^2 + 1} & > \frac{c}{b}  \end{aligned}

On the other hand, AG will be evolutionary stable whenever we have P > S:

\begin{aligned}  \frac{b}{2} & > b\frac{\displaystyle 2k - 3}{\displaystyle 2(k - 2)} - c\frac{\displaystyle 2k^2 - k - 1}{\displaystyle 2(k - 2)(k + 1)} \\  & \vdots \\  \frac{c}{b} & > \frac{k + 1}{2k + 1}  \end{aligned}

Where in both cases I have skipped the arithmetic used to simplify these inequalities.

Notice that since k > 2, we always have k^2 + 1 > 2k + 1. Thus, INV and AG can’t both be evolutionary stable. In other words, when (k + 1)/(k^2 + 1) < c/b < (k + 1)/(2k + 1), both strategies are unstable and there is an internal stable fixed point at a proportion x of INV cells given by:

\begin{aligned}  x & = \frac{P - S}{R - S - T + P} \\  & \vdots \\  & = \frac{b - 2c}{b - c} + {1}{k - 2} - \frac{2c}{(k + 1)(k - 2)(b - c)}  \end{aligned}

Thus, we found three dynamical regimes for the spatialized INV-AG game. Either one or the other (but not both) is evolutionary stable, or they co-exists. Which happens depends on c/b and k, as summarized in figure 2 of Kaznatcheev et al. (2015). Reproduced below:

If you found this excericse fun, dear reader, then I recommend testing your comprehension by repeating the same strategy but with your favourite three-strategy game like INV-AG-GLY (Basanta et al., 2008b)

References

Basanta, D., Hatzikirou, H., & Deutsch, A. (2008a). Studying the emergence of invasiveness in tumours using game theory. The European Physical Journal B, 63(3): 393-397.

Basanta, D., Simon, M., Hatzikirou, H., & Deutsch, A. (2008b). Evolutionary game theory elucidates the role of glycolysis in glioma progression and invasion. Cell Proliferation, 41(6): 980-7

Kaznatcheev, A., Scott, J. G., & Basanta, D. (2015). Edge effects in game-theoretic dynamics of spatially structured tumours. Journal of The Royal Society Interface, 12(108), 20150154.

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

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.

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