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 U_n(k). 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):

U = \sum_{k = 0}^n x^k(1 - x)^{n - k}U_n(k)  .

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.

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.

17 Responses to Space and stochasticity in evolutionary games

  1. Philip Gerlee says:

    Thanks Artem for this detailed description of the issues me and Philipp have brought up. I really think this type of discussion benefits the community and generating it was my intention all along.

    Let me just point out that the critique of the public goods game (PGG) with Bernstein polynomials as applied to cancer is related but distinct from the content of my guest blog post. My concern with the PGG has to do with the concept of forming random groups of players. This completely misses the impact of the neighbourhood of a cell, which in my view is crucial for understanding the dynamics.

    • Thanks for writing the guest post and your helpful comments! I am enjoying the discussion. Some points that are still lingering for me:

      First, I am concerned about the statement of “Bernstein polynomials”. You haven’t criticized that technique at any point, i.e. the elimination of a high-degree polynomial of special form by an easier to analyze continuous function, and the nice properties of fixed points that are preserved in the process. What you seem to have issue with, as far as I understand, is the writing down of the payoff as a binomial distribution over groups — this is not the Bernstein polynomial technique, although it is the setting in which it applies.

      Am I correct in understanding the limit of criticism? If so, I would prefer that you phrase the critique as what it is: a critique of my (and Archetti and others) modeling choices (i.e. averaging over groups), not a critique of the mathematical techniques we then use after we have made our modeling choices.

      Second, I understand how your above critique is related to the content of your guest post, but I don’t understand how it is distinct (apart from point 3 below). As far as I can tell, you get into the same (or very similar) issues with pair-wise games; I have focused a bit more on these types of games in this post simply because there is more literature on that and I wanted the post to be a useful reference for people orienting themselves in the ridiculously vast corpus of EGT.

      Third, the only point of departure in the case of the public-goods-game is your concern about the relevant length-scales of interaction; the mixing of cells happens on the order of 100 micrometers while (you believe) the public good disperses on the order of centimeters. Is this correct? Is this the only objection that is specific to public goods, or do you have further ones that apply only to public goods and not spatialization in general?

      If these questions take a lot of space to answer, especially in light of this comment by me, this one by Robert, and recent follow up by me, then I would appreciate if you responded with a more detailed exposition of why the modeling choices related to PG that we (and Archetti and others) make is flawed and maybe suggestion of how you would (or others have) proceed instead. Maybe that could lead to a collaboration, that would be a wonderful close to this blogging story! As always, I would welcome that as a guest post here or I could read it over on your blog.

      • Philip Gerlee says:

        Sorry, I should have been clearer. What I am worried about is “the writing down of the payoff as a binomial distribution over groups.” The maths that follows I don’t have any complaints about.

        Let me address your second point. For pair-wise games the non-spatial approximation (i.e. the replicator equation) is the limit of a perfectly well-mixed system with complete separation between interaction and division time scales. We know that cells are essentially immobile so the mixing must be due to signals that mediate the interactions. If we think about a growth factor that diffuses, then the well-mixed limit corresponds to a GF whose concentration is always in equilibrium, constant across the population, and proportional to the frequency of producers.

        Now assume that this GF is a public good. With the above assumptions its concentration everywhere in space will be proportional to the frequency of contributors. Since everyone interacts with everyone the most accurate description is to take n = N, i.e. the group size equals the population size.

        Now look at the other extreme a: GF that only spreads to nearest neighbours. Here a small group size makes sense (e.g. n=6 for a hexagonal lattice), but cells only interact locally so averaging across all possible group compositions will introduce an error. Thus it seems as if the limiting case which truly reflects your approach is one where the population really is inviscid. Do you agree about this?

        In conclusion a fast spreading signal can motivate a pair-wise mean-field model, but not your approach to the PGG. The latter requires a mixing of the population.

        Regarding the third point I think that mixing is limited to small (and basically negligible) spatial scales compared to the diffusion of GF. The Marusyk paper gives some hints about the scale, but this is something that needs to be quantified.

        • Robert Vander Velde says:

          I’ll ask a couple questions, one about spatial dynamics and the other about Bernstein polynomials:

          Spatial: You seem willing to go along with the idea of an interaction neighborhood that encompasses the entire tumor but have a problem with a similar dispersal neighborhood. I can see how this might change the timing slightly (since replacement is only occurring along the boundaries of a homogeneous group) but I doubt that it changes the equilibrium conditions. Ifti et al. have looked at decoupling the different types of neighborhood sizes: http://www.zoology.ubc.ca/~doebeli/reprints/ifti_2004.pdf
          However they didn’t look at the case of an inviscid interaction neighborhood and a limited dispersal neighborhood, which I suspect corresponds to the completely inviscid model at equilibrium. I would like to see more papers on this if anyone has seen them (I worked on this a little bit over the summer, just because invasive cells have the same interaction neighborhood as other cells but disperse differently).

          Also Artem might mention this in his next post, but I still think inviscid models, if they turn out to be completely off, as Philip seems to suggest (I’m still not convinced), are useful as control cases in the spirit of Hardy-Weinberg . As Artem mentioned to me, they are a good way to elucidate the importance of (or lack thereof) spatial structure (as Hardy-Weinberg does for different evolutionary mechanisms).

          As to Bernstein polynomials, it seems to me that most public goods games use them, but only behind the curtain. For example the classic payoff for defectors, r*x*c (where r is the interest, x is the proportion of producers and c is the cost of production), is the average of a binomial distribution (which can be derived using Bernstein polynomials). So is your objection about using Bernstein polynomials or using classic public goods games in cancer? Or the fact that an n pops out of our equations?

          • You are right that I will discuss the usefulness of inviscid models as controls. Also, a quick clarification:

            So is your objection about using Bernstein polynomials

            Philip is not objecting to Bernstein polynomials. Also, the group size will pop out from simple averaging, just as it does from BernPoly.

            As you said, we could ignore the reference to BernPoly completely, and simply average (as most people do), but BernPoly give us a few extra handles. In particular, their guarantees on preservation of fixed points (well, not exactly: that we will have an even number, maybe zero, fewer fixed points) allows us to guarantee that in certain cases, the equilibria are not being changed qualitatively by averaging away the discretization due to groups having specific sizes.

            • Robert Vander Velde says:

              I see. I was responding to “The derivation with Bernstein polynomials is flawed” on twitter which made me think there was an objection to their use (in cancer modelling at least).

          • Philip Gerlee says:

            I will back down from my previous wording ‘flawed’ and simply say that I find the derivation problematic.

            I also think that inviscid models are useful, but it is important to understand their inherent limitations. My main concern is that no one in this discussion seems to know what exactly is lost when perfect mixing is assumed. That is fine if one is concerned with game theory from an abstract point of view, but when the aim is to capture some real system knowing the limitations of your tool is important.

  2. vznvzn says:

    see that you have cited archetti quite thoroughly in this & previous blog on cancer oncology. noticed a new ref just popped up in PNAS. Game theory explains social interactions of cancer cells. yes its great to see some kind of theoretical model show up that has a theoretical plausibility, and the ties to economics “free rider” problem is quite signficant also. the “free rider” problem applies also in cyberspace but it hasnt been studied so much there….

  3. Thanks for the post Artem. I concur with Philip that this post is a good venue in which to discuss modelling topics.
    Regarding your arguments, I won’t comment much on them because I first want to make sure I understand them. I wonder whether you’d like to have some sort of summarising statement at the end of your posts for the benefit of those less gifted such as myself.
    The gist as I understand it: our model does not consider space explicitly, Philip thinks that this is a gross oversimplification of reality when it comes to public goods, then you entertain his arguments, propose that patches would be an improvement, elaborate that a probabilistic approach to the interactions between players could be a solution and mention that people that are good at Game Theory have use inviscid models before anyway so why the fuss. Does this capture the spirit of it?

    • I didn’t provide any arguments against Philip’s position in this post, because I was still unsure that I properly expressed it. Although his position is much more clear to me after his new comment. I originally intended the post to also include responses, so artifacts from that preliminary draft is what might have suggested that I was going to do it in this post. I will try to write a couple of posts in the near future to provide some responses, probably one as a response to P&P and this post, one about the measurement of fitness (that we chatted about over hot chocolate, but that I need to read a bit more about), and one as a response to Philip about PGG. The last response is probably the one you are interested in, since it will deal with the PGG work.

      Here, I wasn’t suggesting patches as a response to Philip, but as the ‘minimum required’ to express his opposition. Although maybe not the level he would want to express it at (since he seems to prefer full spatial, hence the last sentence of that section).

  4. Pingback: Seeing edge effects in tumour histology | Theory, Evolution, and Games Group

  5. Pingback: Operationalizing replicator dynamics and partitioning fitness functions | Theory, Evolution, and Games Group

  6. Pingback: An update | Theory, Evolution, and Games Group

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

  8. Pingback: Measuring games in the Petri dish | Theory, Evolution, and Games Group

  9. Pingback: Hadza hunter-gatherers, social networks, and models of cooperation | 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 )

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