Space and stochasticity in evolutionary games

Two of my goals for TheEGG this year are to expand the line up of contributors and to extend the blog into a publicly accessible venue for active debate about preliminary, in-progress, and published projects; a window into the everyday challenges and miracles of research. Toward the first goal, we have new contributions from Jill Gallaher late last year and Alexander Yartsev this year with more posts taking shape as drafts from Alex, Marcel Montrey, Dan Nichol, Sergio Graziosi, Milo Johnson, and others. For the second goal, we have an exciting debate unfolding that was started when my overview of Archetti (2013,2014) prompted an objection from Philip Gerlee in the comments and Philipp Altrock on twitter. Subsequently, Philip and Philipp combined their objections into a guest post that begat an exciting comment thread with thoughtful discussion between David Basanta, Robert Vander Velde, Marc Harper, and Philip. Last Thursday, I wrote about how my on-going project with Robert, David, and Jacob Scott is expanding on Archetti’s work and was surprised to learn that Philip has responded on twitter with the same criticism as before. I was a little flabbergast by this because I thought that I had already addressed Philip’s critique in my original comment response and that he was reiterating the same exact text in his guest post simply for completeness and record, not because he thought it was still a fool-proof objection.

My biggest concern now is the possibility that Philip and I are talking past each other instead of engaging in a mutually beneficial dialogue. As such, I will use this post to restate (my understand of the relevant parts of) Philip and Philipp’s argument and extend it further, providing a massive bibliography for readers interested in delving deeper into this. In a future post, I will offer a more careful statement of my response. Hopefully Philip or other readers will clarify any misunderstandings or misrepresentations in my summary or extension. Since this discussion started in the context of mathematical oncology, I will occasionally reference cancer, but the primary point at issue is one that should be of interest to all evolutionary game theorists (maybe even most mathematical modelers): the model complexity versus simplicity tension that arises from the stochastic to deterministic transition and the discrete to continuous transition.

Philip and Philipp’s opposition to EGT consists of two main parts. The first one is about the importance of spatial structure and difficulty of averaging; and the second part is about how to fit model parameters. I will not discuss the second part, although for rebuttals I would point the reader to parametrizations inspired by the analysis of reaction kinetics in chemistry (Liao & Tlsty, 2014; suggested by Marc Harper) or recent experimental progress by Ribeck & Lenski (2014; suggested with some reservations by Philip Gerlee after their initial post); or the whole issue can be sidestepped by noticing that not all models aspire to be insilications. For the first part, I will proceed by concrete example.

Suppose that we are looking at a public good game with two strategies. If Alice interacts with n many agents where k of them have the same strategy as her, then she will receive the payoff . Further, let’s suppose that a proportion x of all agents have the same strategy as Alice. Now, if I wanted to write down the (expected) fitness of the population, I would write (upto a re-normalizing constant):

.

This is the step that Philip Gerlee is opposed to. Since he gives a couple of reasons for his opposition, I will start with the simpler one and them move on to the most sophisticated:

we assume that everyone interacts with everyone else. Then we do not have to care about … if they managed to even interact at all before they reproduce and die. We only worry about the total number of individuals of a given type and say that a given individual interacts with all of them, somehow, and then reproduces. In addition the time-scale of interactions is taken to be infinitely faster than the scale of reproductive events.

This is correct, if I want to have my equation exact. If I construct every possible group of n + 1 individuals and let them interact then I will have the above equation (upto a normalizing constant that divides by the ridiculous number of interactions that I just allowed) exactly. In fact, I will have something stronger, I will have every agent of Alice’s type having the same exact fitness that is equal to the above equation. Obviously, nobody wants to be exact at this level, we want a statistical theory. So instead of looking at ever possible group of n + 1 agents, why don’t I just sample M such groups randomly. In that case, I will have to replace U by E(U) to have the equation exactly correct, and I will need to have M not too small for the average to be a useful property of the random variable; it won’t have to be super huge though, since the Binomial distribution is pretty tight around its mean.

Note that as soon as I moved to the stochastic interpretation at the level of the whole population, most of the problems in that paragraph disappeared. I don’t need everyone of Alice’s type to have some interactions before reproducing, I just need most of the agents to have interacted; I don’t need infinitely many interactions per individual, the average number per individual d has be enough to make M a decently sized number. That isn’t to say that there is not bias that is introduced from finite sampling, but it’s effect disappears at approximately 1/d (Hilbe, 2011).

Of course, whenever you go from reasoning about a stochastic random variable to talking about its mean, issues can creep in and sometimes it is worthwhile to do a deeper analysis to explore them. For instance, in the case of branching processes, your theory can get boringly simple if you just use the deterministic approximation. Another issue can be that your same-strategy population now has a variance in fitness and if you have two populations with very similar means then sometimes evolution might have a pressure for lower variance (Orr, 2007), or if have non-linear selective sweeps then you might get even stranger results. Further, if you imagine the agents as reproducing stochastically (so even two agents with the same fitness might differ in their reproduction due to noise) then you have to worry about the effects of finite population (Fogel et al., 1998; Ficini & Pollack, 2000); selection strength (Wu et al., 2010), which is decreased by random sampling of interaction partners (Traulsen et al., 2007); and, which update rule and other microdynamical assumptions you make (Wu et al., 2014a). In simpler words: it’s a mess and we haven’t even gotten around to spatial structure!

Before we jump into space (in all its gory detail), I want to mention a slightly less restrictive precursor that has an important interaction with stochasticity: patch models. Suppose that you have a game with an an inviscid dynamical profile that contains an unstable equilibrium around which the population could bifurcate into one of several basins of attraction. If we model only the inviscid replicator dynamics then our population will always fall into one of those basins and be driven to the sink; at equilibrium, we will never see a population that is heterogeneous in sinks. Now suppose instead that the initial population is distributed over regions (or patches) and the mean is very close to the unstable equilibrium. The stochastic fluctuations between regions might be enough that some regions will fall into one basin of attraction while others into another. If the coupling between regions is weak or slow enough that the within-patch evolution can outrun it then we could end up with a final population that is heterogeneous. Things can get even more exciting in games where there exist correlated equilibria that are very different from the Nash — an example would be the Hawk-Dove game. In that case, if there is some inter-patch structure then even with strong inter-parch coupling, you could have adjacent patches lock each other into a correlated equilibrium, or even form spatial patterns like traveling waves (for some fully spatial examples of this, see Hauert & Doebeli, 2004; Wakano et al., 2009; Wakano & Hauert, 2011; Bryce, 2011; Hwang et al., 2013).

I think the above is the level at which Philip is opposing when he writes:

The cell cycle of a tumor cell is often taken to be 24 hours, but this is probably an underestimate for in vitro conditions. Let’s say 100 hours. The typical size of a tumor is roughly 10 cm. The mean displacement (i.e. square root of mean square displacement) after 100 hours is approximately 100 micrometer (Wu et al., 2014b), i.e. 0.1% of the assumed linear size. Note that the migration data is taken from single cells moving at low density, and hence that the rate of migration in a tightly packed tumor is probably much smaller. This result suggests that migration contributes little towards “mixing” the population.

As I read it, he is saying that the mixing in a tumour is happening on the order of 100 micrometers or less, which is tiny compared to the tumour that is sized on the order of centimeters. Thus, a proper model would have to (at least) split up the tumor into thousands of patches with some small coupling of migration between the patches, while the much more global nature of the diffusing public good would have to be modeled as spreading past patches given the experimental work of Marusyk et al. (2014; although see Robert’s comment for a disputation of this interpretation).

Of course, Philip might also advocate for a fully-spatial hybrid model with discrete cells localized in space and a continuous gradient for the public good through all of space.

Now, we finally reach spatial structure. After all, with the possible exception of leukemia and lymphoma, cancers exist in space, adjacent to cells and boundaries, with daughter cells taking over the space of (or near) their mothers. This consideration is so important that a particular approach to it even has its own sub-field name: evolutionary graph theory (Lieberman et al., 2005; Szabo & Fath, 2007; Shakarian et al., 2012; Maciejewski & Puleo, 2013). Durrett & Levin (1994; also, see Shnerb et al., 2000) provide a particularly good demonstration of how much spatial structure and stochasticity can matter as they build from mean-field approaches (of which the inviscid replicator dynamics with which we started is an example) to patch models of discrete individuals to reaction-diffusion equations to full-fledged interacting particle systems. Further, Rick Durrett is an established name in mathematical oncology and the preceding is his most cited paper, so surely modelers in mathematical oncology are aware of the importance of space. We know that space can promote cooperation (Nowak & May, 1992; Ohtsuki et al., 2006), or inhibit it (Hauert & Doebeli, 2004), or complicate the whole discussion around it (Killingback & Doebeli, 2006). Spatial structure can so drastically change the nature of the game that the inviscid analysis in completely inapplicable. Even the argument of analytic intractability is no defense when we have pair-approximation techniques (and other alternatives) that can be applied with few arbitrary model commitments (Matsuda et al., 1987; van Baalen, 2000; Ohtsuki & Nowak, 2006).

With all of these arguments for space and stochasticity, why does anybody even bother start to think about inviscid replicator dynamics and averaging of payoffs? Why doesn’t everybody build spatial models with stochasticity of adjustable variance and selection of variable strength? In a future post, I will try to make a case for why all these considerations shouldn’t stop us from working with inviscid models.

References

Archetti, M. (2013). Evolutionary game theory of growth factor production: implications for tumour heterogeneity and resistance to therapies. British Journal of Cancer, 109(4): 1056-1062.

Archetti, M. (2014). Evolutionary dynamics of the Warburg effect: glycolysis as a collective action problem among cancer cells. Journal of Theoretical Biology, 341: 1-8.

Bryce, A. (2011). Turing instability in discrete replicator systems. Masters Thesis at Rochester Institute of Technology

Durrett, R., & Levin, S. (1994). The Importance of Being Discrete (and Spatial). Theoretical Population Biology, 46 (3), 363-394 DOI: 10.1006/tpbi.1994.1032

Ficici, S. G., & Pollack, J. B. (2000). Effects of Finite Populations on Evolutionary Stable Strategies. In GECCO (p. 927).

Fogel, G. B., Andrews, P. C., & Fogel, D. B. (1998). On the instability of evolutionary stable strategies in small populations. Ecological Modelling, 109(3): 283-294.

Hauert, C., & Doebeli, M. (2004). Spatial structure often inhibits the evolution of cooperation in the snowdrift game. Nature, 428(6983), 643-646.

Hilbe, C. (2011). Local replicator dynamics: a simple link between deterministic and stochastic models of evolutionary game theory. Bull Math Biol, 73: 2068-2097.

Hwang, S. H., Katsoulakis, M., & Rey‐Bellet, L. (2013). Deterministic equations for stochastic spatial evolutionary games. Theoretical Economics, 8(3): 829-874.

Killingback, T., & Doebeli, M. (1996). Spatial Evolutionary Game Theory: Hawks and Doves Revisited. Proceedings of the Royal Society of London. Series B: Biological Sciences, 263(1374), 1135–1144.

Liao, D., & Tlsty, T. D. (2014). Evolutionary game theory for physical and biological scientists. I. Training and validating population dynamics equations. Interface Focus, 4(4).

Lieberman, E., Hauert, C., & Nowak, M. A. (2005). Evolutionary dynamics on graphs. Nature, 433(7023): 312-316.

Maciejewski, W., & Puleo, G. J. (2013). Environmental Evolutionary Graph Theory. arXiv preprint: 1311.3214.

Matsuda, H., Tamachi, N., Sasaki, A., & Ogida, N. (1987). A lattice model for population biology. In: Teramoto, E., Yamaguti, M. (Eds.), Mathematical Topics in Biology, Morphogenesis and Neurosciences. Spring Lecture Notes in Biomathematics 71: 154-161.

Marusyk, A., Tabassum, D.P., Altrock, P.M., Almendro, V., Michor, F., & Polyak, K. (2014). Non-cell-autonomous driving of tumour growth supports sub-clonal heterogeneity. Nature, 514 (7520), 54-8

Nowak, M. A., & May, R. M. (1992). Evolutionary games and spatial chaos. Nature, 359(6398), 826-829.

Ohtsuki, H., Hauert, C., Lieberman, E., & Nowak, M. A. (2006). A simple rule for the evolution of cooperation on graphs and social networks. Nature, 441(7092): 502-505.

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

Orr, H.A. (2007). Absolute fitness, relative fitness, and utility. Evolution, 61(12): 2997-3000.

Ribeck, N., & Lenski, R. E. (2014). Modeling and quantifying frequency-dependent fitness in microbial populations with cross-feeding interactions. bioRxiv: 012807.

Shakarian, P., Roos, P., & Johnson, A. (2012). A review of evolutionary graph theory with applications to game theory. Biosystems, 107(2): 66-80.

Shnerb, N.M., Louzoun, Y., Bettelheim, E., & Solomon, S. (2000). The importance of being discrete: Life always wins on the surface. Proceedings of the National Academy of Sciences, 97 (19): 10322-4.

Szabo, G., & Fath, G. (2007). Evolutionary games on graphs. Physics Reports, 446 (4-6), 97-216

Traulsen, A., Nowak, M.A., & Pacheco, J.M. (2007). Stochastic payoff evaluation increases the temperature of selection. Journal of Theoretical Biology, 244(2): 349-356.

van Baalen, M. (2000). Pair approximations for different spatial geometries. In: Dieckmann, U., Law, R., & Metz, J.A.J (Eds.), The geometry of ecological interactions: Simplifying spatial complexity. Cambridge University Press. 359-387.

Wakano, J. Y., Nowak, M. A., & Hauert, C. (2009). Spatial dynamics of ecological public goods. Proceedings of the National Academy of Sciences, 106(19): 7910-7914.

Wakano, J. Y., & Hauert, C. (2011). Pattern formation and chaos in spatial ecological public goodsgames. Journal of Theoretical Biology, 268(1): 30-38.

Wu, B., Altrock, P. M., Wang, L., & Traulsen, A. (2010). Universality of weak selection. Physical Review E, 82(4): 046106.

Wu, B., Bauer, B., Galla, T., & Traulsen, A. (2014a). When do microscopic assumptions determine the outcome in evolutionary game dynamics? arXiv preprint: 1406.4030.

Wu, P. H., Giri, A., Sun, S. X., & Wirtz, D. (2014b). Three-dimensional cell migration does not follow a random walk. Proceedings of the National Academy of Sciences, 111(11): 3949-3954.