Effective games from spatial structure

For the last week, I’ve been at the Institute Mittag-Leffler of the Royal Swedish Academy of Sciences for their program on mathematical biology. The institute is a series of apartments and a grand mathematical library located in the suburbs of Stockholm. And the program is a mostly unstructured atmosphere — with only about 4 hours of seminars over the whole week — aimed to bring like-minded researchers together. It has been a great opportunity to reconnect with old colleagues and meet some new ones.

During my time here, I’ve been thinking a lot about effective games and the effects of spatial structure. Discussions with Philip Gerlee were particularly helpful to reinvigorate my interest in this. As part of my reflection, I revisited the Ohtsuki-Nowak (2006) transform and wanted to use this post to share a cute observation about how space can create an effective game where there is no reductive game.

Suppose you were using our recent game assay to measure an effective game, and you got the above left graph for the fitness functions of your two types. On the x-axis, you have seeding proportion of type C and on the y-axis you have fitness. In cyan you have the measured fitness function for type C and in magenta, you have the fitness function for type D. The particular fitnesses scale of the y-axis is not super important, not even the x-intercept — I’ve chosen them purely for convenience. The only important aspect is that the cyan and magenta lines are parallel, with a positive slope, and the magenta above the cyan.

This is not a crazy result to get, compare it to the fitness functions for the Alectinib + CAF condition measured in Kaznatcheev et al. (2018) which is shown at right. There, cyan is parental and magenta is resistant. The two lines of best fit aren’t parallel, but they aren’t that far off.

How would you interpret this sort of graph? Is there a game-like interaction happening there?

Of course, this is a trick question that I give away by the title and set-up. The answer will depend on if you’re asking about effective or reductive games, and what you know about the population structure. And this is the cute observation that I want to highlight.

In the above figure, there is clearly an effective game happening. As the proportion of strategy B increases, both strategy A and strategy B benefit. In fact, if we look at just the fitness functions then the story of a public good or a benefit-cost prisoner’s dilemma game would be consistent with this graph. We can think of strategy B as paying a constant cost — the cost is the distance between the parallel lines — to produce a public good that benefits both type A and B cells equally — the benefit is the slope of the parallel lines.

If you were to write down the corresponding game matrix, you would get \begin{pmatrix}1 & 3 \\ -2 & 0 \end{pmatrix}. Where type D corresponds to the first row and column, and type C corresponds to the second row and column. From this, you’d see it isn’t a traditional benefit-cost Prisoner’s dilemma since you’d need benefit b = 2 and cost c = 3. While we usually think of traditional PDs as having b > c .

But this would still certainly feels like a textbook example of a non-cell-autonomous process; even if not the most standard one.

In fact, for the similar Alectinib + CAF condition shown at right, Kaznatcheev et al. (2018) make this conclusion. They say that the fitness functions in this condition (as well as several other ones that aren’t close to conforming to parallel lines) as non-cell-autonomous.

Unfrotuntaly, this is a conclusion about the effective games. And it doesn’t need to hold for the reductive game.

As I’ve discussed before (see Kaznatcheev, 2017; 2018), it can be difficult to infer reductive games from the measurement of effective games. Many different reductive games in different population structures can map to the same effective game. But if we have a particularly nice population structure then we can invert the reductive to effective abstraction, and uniquely infer the reductive game.

So let’s do that.

Let’s suppose that we know that the effective game we measured is actually implemented by a reductive game played on a random 3-regular graph with birth-death updating. I’m picking this population structure not because it is a common structure in nature, but just for the purpose of this illustration. I’m picking this population structure because the Ohtsuki-Nowak transform provides us with a way to map from reductive to effective games.

As I’ve derived before, in the case of two strategy games, the ON transform maps reductive games of the form \begin{pmatrix}1 & U \\ V & 0 \end{pmatrix} to effective games of the form \begin{pmatrix}1 & X \\ Y & 0\end{pmatrix} where the game coordinates change according to the following affine transformation:

\begin{pmatrix}X \\ Y \end{pmatrix} = \frac{1}{k - 2}\begin{pmatrix}k - 2 + \nu & - \nu \\ - \nu & k - 2 + \nu \end{pmatrix} \begin{pmatrix} U \\ V \end{pmatrix} + \frac{1}{k - 2}\begin{pmatrix}1 \\ - 1\end{pmatrix}

where k is the degree of the graph, and \nu = 1 for Birth-Death updating or \nu = \frac{1}{k - 1} for Death-Birth updating.

In particular, if we take the reductive (i.e. token) fitness of type D cells to be 1 and the reductive fitness of type C cells to be 0. In other words, each type has constant token fitness independent of who they interact with — something that most people wouldn’t describe as a game-like dynamic. But if we insist writing it dowb this cell-autonomous fitness as a payoff matrix then we get the reductive payoff matrix: \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}.

And at this point, it should be no surprise that on a 3-regular random graph with Birth-Death updating, this reductive ‘game’ becomes the effective game given by \begin{pmatrix}1 & 3 \\ -2 & 0 \end{pmatrix}.

In words: two kinds of cells that each have cell-autonomous token fitness at the reductive level can have non-cell-autonomous type fitness at the effective level if their population in spatially structured. Spatial structure can create an effective game where there is no reductive game.

When the spatial structure is simple — as it is for the first-order approximation of the ON-transform — then the resulting effective game is also relatively simple. But I would also expect this general ‘effective game creation’ result to hold for more complicated and realistic population structures. Except instead of creating a simple linear effective game of two parallel fitness functions, it could create a much more complicated non-linear game that depends on the details of the spatial structure itself.

To make things even more difficult: if space can create an effective game from a constant fitness reductive ‘game’ then space can also hide a reductive game in a constant fitness effective ‘game’.

This can be most easily seen if we invert the affine transform from reductive to effective games into one from effective to reductive games:

\begin{pmatrix}U \\ V \end{pmatrix} = \frac{1}{k - 2(1 - \nu)}\begin{pmatrix}k - 2 + \nu & \nu \\ \nu & k - 2 + \nu \end{pmatrix} \begin{pmatrix} X \\ Y \end{pmatrix} + \frac{1}{k - 2(1 - \nu)}\begin{pmatrix}1 \\ - 1\end{pmatrix}

Now, we can consider effective observations where the cell-autonomous type-fitness of type C is 0 and of type D is 1. This would correspond to the effective ‘game’ of \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix} or X = 1, Y = 0. When you plug this in above, you find that for a 3-regular graph with Birth-Death updating, the resulting reductive game is non-cell-autonomous: \begin{pmatrix} 1 & 1/3 \\ 2/3 & 0 \end{pmatrix}.

If we were judging just from the effective fitness function, we might conclude that the system has a cell-autonomous system. But at the reductive level, it would actually have frequency dependent fitness that is masked by the spatial structure.

Thus, in space, we have another complication to consider if we’re trying to make reductive statements from effective measurements. More importantly, this complication is important even if we’re only interested in broad qualitative conclusions like distinguishing cell-autonomous vs. non-cell-autonomous processes.

References

Kaznatcheev, A. (2017). Two conceptions of evolutionary games: reductive vs effective. bioRxiv: 231993.

Kaznatcheev, A. (2018). Effective games and the confusion over spatial structure. Proceedings of the National Academy of Sciences: 115(8): E1709.

Kaznatcheev, A., Peacock, J., Basanta, D., Marusyk, A., & Scott, J. G. (2018). Fibroblasts and Alectinib switch the evolutionary games played by non-small cell lung cancer. bioRxiv, 179259.

Ohtsuki, H., & Nowak, M.A. (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.

5 Responses to Effective games from spatial structure

  1. Philip Gerlee says:

    Thanks for a thought-provoking post. I’m a bit unsure how to understand the fact that the ON-transform is derived in the weak selection limit, and how that connects with the growth rates that you measured in the game assay.

    In the ON-paper they state that fitness is given by 1-w+wP, where w is the small selection coefficient and P is the payoff derived from interactions. The transform is exact only in the limit of w —> 0, which means that payoff has a very small impact on fitness.

    In your game assay, on the other hand, you assume that fitness depends entirely on payoff, which corresponds to setting w=1 in 1-w+wP, i.e. the strong selection limit.

    Is there a way to reconcile these different mappings from payoff to fitness? If not, then I’m not convinced that it makes sense to talk about the ON-transform for the game assay.

    • That is a good point Philip.

      I didn’t mean to suggest that inverting the ON-transform is a good way to spatialize our game assay. I just wanted to use a measurement one might get out of a game assay as a motivating example, and the ON transform as a simple stand in for space. I think it is still an open question on how to properly operationalize space from a top-down perspective. I have some ideas and opinion on this, but nothing super concrete.

      For this post, I should have probably phrased it more awkwardly by saying: suppose you were measuring evolutionary dynamics on a random 3-regular graph and you measured the left-hand side of the figure. Then I could have actually run some simulations to get a right hand side as an example (instead of pulling out a not well related figure that I happened to have at hand). Your statements would have still applied in this case, since simulations of games seldom take the limit of w going to 0 and since the transform is only exact on infinite Bethe-lattices and not random graphs. However, in practice it would work fine there and we’d be alright in most cases to jump back and forth from the effective and reductive conception. At least from my experience with these sort of simulations.

      But my point was just to provide a simple illustration that space can create what looks like a macroscopic signature of a game-like interaction even when there is nothing transparently game-like in the microscopic specification. I chose the ON-transform for this just because it produces simple results, and I happen to be familiar with it. A more organized approach to this might be to define some broad class of microdynamics and spatial structures and prove when their macrodynamics will look frequency dependent even when the microdynamic fitnessess are specified as frequency-independent. That would be a fun thing to do, especially with microdynamics that are believable (which graphs really aren’t for me), but it isn’t something that I’ve done yet.

      • Philip Gerlee says:

        Thanks for the clarification. I hope my ideas about spatial games that we discussed at IML can contribute to answering the questions you pose. I think we need something like that in order to move between reductive and effective games when the agents/cells are located in R^2 (or R^3). The question is how much can be achieved if selection is not weak, which is what your game assay results suggests.

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

  3. Pingback: Cataloging a year of metamodeling blogging | 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 )

Google photo

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

Connecting to %s

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