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.
Read more of this post

Hadza hunter-gatherers, social networks, and models of cooperation

At the heart of the Great Lakes region of East Africa is Tanzania — a republic comprised of 30 mikoa, or provinces. Its border is marked off by the giant lakes Victoria, Tanganyika, and Malawi. But the lake that interests me the most is an internal one: 200 km from the border with Kenya at the junction of mikao Arusha, Manyara, Simiyu and Singed is Lake Eyasi. It is a temperamental lake that can dry up almost entirely — becoming crossable on foot — in some years and in others — like the El Nino years — flood its banks enough to attract hippos from the Serengeti.

For the Hadza, it is home.

The Hadza number around a thousand people, with around 300 living as traditional nomadic hunter-gatherers (Marlow, 2002; 2010). A life style that is believed to be a useful model of societies in our own evolutionary heritage. An empirical model of particular interest for the evolution of cooperation. But a model that requires much more effort to explore than running a few parameter settings on your computer. In the summer of 2010, Coren Apicella explored this model by traveling between Hadza camps throughout the Lake Eyasi region to gain insights into their social network and cooperative behavior.

Here is a video abstract where Coren describes her work:

The data she collected with her colleagues (Apicella et al., 2012) provides our best proxy for the social organization of early humans. In this post, I want to talk about the Hadza, the data set of their social network, and how it can inform other models of cooperation. In other words, I want to freeride on Apicella et al. (2012) and allow myself and other theorists to explore computational models informed by the empirical Hadza model without having to hike around Lake Eyasi for ourselves.

Read more of this post

Operationalizing the local environment for replicator dynamics

Recently, Jake Taylor-King arrived in Tampa and last week we were brainstorming some projects to work on together. In the process, I dug up an old idea I’ve been playing with as my understanding of the Ohtsuki-Nowak transform matured. The basic goal is to work towards an operational account of spatial structure without having to commit ourselves to a specific model of space. I will take replicator dynamics and work backwards from them, making sure that each term we use can be directly measured in a single system or abducted from the other measurements. The hope is that if we start making such measurements then we might see some empirical regularities which will allow us to link experimental and theoretical models more closely without having to make too many arbitrary assumptions. In this post, I will sketch the basic framework and then give an example of how some of the spatial features can be measured from a sample histology.
Read more of this post

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.

Read more of this post

Is cancer really a game?

A couple of weeks ago a post here on TheEGG, which was about evolutionary game theory (EGT) and cancer, sparked a debate on Twitter between proponents and opponents of the idea of using EGT to study cancer. Mainly due to the limitations inherent to Twitter the dialogue fizzled. Instead, here we are expanding ideas in this guest blog post, and eagerly await comments from the others in the debate. The post is written by Philip Gerlee and Philipp Altrock, with some editing from Artem. We will situate the discussion by giving a brief summary of evolutionary game theory, and then offer commentary and two main critiques: how spatial structure is handled, and how to make game theoretic models correspond to reality.
Read more of this post

Approximating spatial structure with the Ohtsuki-Nowak transform

Can we describe reality? As a general philosophical question, I could spend all day discussing it and never arrive at a reasonable answer. However, if we restrict to the sort of models used in theoretical biology, especially to the heuristic models that dominate the field, then I think it is relatively reasonable to conclude that no, we cannot describe reality. We have to admit our current limits and rely on thinking of our errors in the dual notions of assumptions or approximations. I usually prefer the former and try to describe models in terms of the assumptions that if met would make them perfect (or at least good) descriptions. This view has seemed clearer and more elegant than vague talk of approximations. It is the language I used to describe the Ohtsuki-Nowak (2006) transform over a year ago. In the months since, however, I’ve started to realize that the assumptions-view is actually incompatible with much of my philosophy of modeling. To contrast my previous exposition (and to help me write up some reviewer responses), I want to go through a justification of the ON-transform as a first-order approximation of spatial structure.
Read more of this post

Edge effects on the invasiveness of solid tumours

MetastasisCareful readers might have noticed that, until last night’s post, the blog was silent for an atypically long 10 days (17 days since I last posted). As usual, the primary culprit is laziness, but this time it is not alone! After my fun visit to the Integrated Mathematical Oncology Department of the Moffit Cancer Research Center, I have been working closely with Jacob Scott and David Basanta to finish up our first joint paper. The last week was particularly busy as we pushed the paper out for submission and posted a draft to the ArXiv.

We look at the effect of spatial structure, in particular a spatial boundary, on the evolutionary dynamics of motility in cancer. For a tumor, one of the key steps in going from a benign to malignant is gaining the ability to spread from one organ to another non-adjacent organ. To achieve this, a cancer cell has to transition from simple proliferative cells (AG) to a motile ones (INV). However, motility usually involves a cost to the organism. We show that spatial structure can lower this cost, and smaller neighborhood size at an edge can promote motile cells at the boundary even when they are absent in the tumour body.
Read more of this post

Game theoretic analysis of motility in cancer metastasis

As I am starting to write this post, the last of the 4th of July fireworks are winding down outside. I am currently traveling through New York on my way to Swarmfest 2013 in Orlando, FL and to visit David Basanta and Jacob Scott at the Integrated Mathematical Oncology Department of Moffitt Cancer Research Institute in Tampa, FL. The weather is unbearably hot already, so I imagine I will struggle in Florida, especially since I forgot all my shorts in Montreal!

MetastasisThe more important struggle, however, will be my lack of background in biology and medicine. On Jake’s suggestion, I decided to look at a paper of David’s on an evolutionary game theoretic approach to the emergence of motility in cancer cells. As far as I understand, one of the key steps in going from a benign tumor to a malignant cancer is metastasis or the ability of a cancer to spread from one organ to another non-adjacent organ. To achieve this, a cancer cell has to transition from a simple proliferative cell to a motile one. However, motility usually involves a cost to the organism.
Read more of this post

Introduction to evolving cooperation

Since 2009, I’ve had a yearly routine of guest lecturing for Tom’s Cognitive Science course. The way I’ve structured the class was by assigning videos to watch before the lecture so that I could build on them. Last year, I started posting the video ahead of time on the blog: my 2009 TEDxMcGill talk, Robert Wright’s evolution of compassion, and Howard Rheingold’s new power of collaboration. However, instead of just presenting a link with very little commenatry, this time I decided to write a transcript with my talk that I seeded with references and links for the curious. The text is not an exact recreation of the words, but a pretty close fit that is meant to serve as a gentle introduction to the evolution of cooperation.

Earlier today, we heard about the social evolution of language and to a certain extent we heard about the emergence and evolution of zero. We even heard about our current economic affairs and such. I am going to talk about all of these things and, in particular, continue the evolutionary theme and talk about the evolution of cooperation in society and elsewhere.

We’ve all come across ideas of the greater good, altruism, cooperation or the sacrifice of an individual for the good of others. In biology, we have an analogous concept where we look at the willingness of certain individuals to give up some of their reproductive potential to increase the reproductive potential of others. This paradoxical concept in the social sciences is grappled with by philosophers, sociologists, and political scientists. In the biological context, it is obviously an important question to biologists.

Now, the question really becomes as to how and why does this cooperation emerge? First, we are going to look at this from the biological point of view, connect it to the social sciences, and then to everything else.

Currently, biology is really shaped by Darwin, Wallace and their theory of evolution by natural selection. It is a unifying theme and tie of modern biology. The interesting feature of biology is that it is an explicitly competitive framework: organisms compete against other organisms for their reproduction. Our question becomes: how does cooperation emerge in such a competitive environment?

We know this cooperation does emerge because it is essential for all the complexity we see. It is essential for single cells to come together into multi-cellular organisms, for the emergence of ant colonies, and even human society. We want to study this and try to answer these questions. But how do you create a competitive environment in a mathematical framework? We borrow from game theory the idea of Prisoner’s dilemma, or in my case I prefer the Knitter’s dilemma. This is one of many possible models of a competitive environment, and the most used in the literature.

In the Knitter’s dilemma there are two players. One of them is Alice. Alice produces yarn, but she doesn’t have any needles, and she wants to sew a sweater. In the society that she lives, knitting sweaters is frowned upon, so she can’t go ask for needles publicly. Bob, on the other hand, produces needles but not yarn. He also wants to sew a sweater. So they decide: “okay, lets go out into the woods late at night, bring briefcases with our respected goods and trade”.

Alice has a dilemma: should she include yarn in her briefcase (indicated by the green briefcase in the figure below)? Or should she not (signified by the red)? If Bob includes needles (first column), and Alice includes yarn then she gets the benefit b of going home and knitting a sweater, but she does pay a small cost c for giving away some of her yarn. Alternatively, if Bob brings needles, but she’s tricky and doesn’t bring her yarn then she gets all the benefit of going home and making a sweater without paying even the marginal cost of giving away some of her yarn. If Bob brings an empty briefcase (second column), and Alice brings yarn as she said she would then Alice pays a small cost in giving some of her yarn away without benefit of being able to make a sweater. Alternatively, if she also brings an empty briefcase then they just met in the middle of the night, traded empty briefcases, and everybody goes back with the no payoff.

Knitter's dilemma

It seems that no matter what Bob does, it is better for Alice to bring an empty briefcase, what we call defection, than to cooperate by bringing a full briefcase. This sets up the basic idea of a competitive environment. The rational strategy, or the Nash equilibrium, for this game is for both individuals to defect and bring empty briefcases. However, from outside the game we can see that if they both do what they said they would and cooperate then they are both better of. That is captured by the Pareto optimum in green.

Of course, as mentioned earlier by Andy, we cannot always expect people to be rational and make all these decisions based on reasoning. Evolutionary game theory comes from the perspective of modeling Alice and Bob as simple agents that have a trait that is passed down to their offspring. This is shown below by green circles for players that cooperate and red circles for ones that don’t. In the standard model, we will pair them off randomly and they will play the game. So a green and a green is two cooperators; they both went home and made a sweater. Two reds both went empty handed. After interaction we disseminate them through the population and let them reproduce according to how the game affected their potential. Higher for people that received a large benefit, and lower chance to reproduce to people who only paid costs. We cycle this for a while, and what we observe is more and more red emerging. All the green cooperation starts to go away. This captures the basic intuition that a competitive environment breeds defection.

Of course, you and I can think of some ways to overcome this dilemma. Evolutionary game theorists have also been there and thought of it (Nowak, 2006). They thought of three models of how to avoid it. The first is Hamilton’s (1964) kin selection: Bob’s actually your uncle, and you’re willing to work with him. You’ll bring the yarn as you said you would. Alternatively, you’ve encountered Bob many times before and he has always included needles in his briefcase. You are much more willing to work with him. This is Trivers’ (1971) direct reciprocity, and you’ll include your yarn. Finally, indirect reciprocity (Nowak & Sigmund, 1998): you’ve heard that Bob is an honest man that always brings needles as he says he will. So you are much more likely to cooperate with him.

All these things seem pretty simple to us, but if we’re an amoeba floating around in some soup (and microbes do play games; Lenski & Velicer 2001) then it’s not quiet as obvious that we can do any of these things. Recognizing kin, remembering past interactions, or social constructs like reputation become very difficult. Hence, I look at the more primitive methods such as spatial/network reciprocity or viscosity.

Earlier, Paul mentioned that if we have a turbulent environment it becomes very hard for us to live. Hence the idea that we introduce some structure into our environment. We populate all our agents inside a small grid where they can interact with their neighbors and reproduce into neighboring squares.

Alternatively, we can borrow an idea from the selfish gene approach to evolution called the green-beard effect. This was introduced by Hamilton (1964) & Dawkins’ Selfish Gene. This is a gene that produces three phenotypical effects: (1) it produces an arbitrary marker which we call the beard (or in our case circles and squares), (2) it allows you to recognize this trait in others, not their strategy just the trait/beard, and (3) it allows you to change your strategy depending on what trait/beard you observe. As before, you can cooperate or defect with other circles, or if you meet a square then you can also chose to cooperate or defect. You have four possible strategies that are drawn in the figure below. In human culture, cooperating with those that are like you (i.e. other circles) and defecting against those that are squares is the idea of ethnocentrism. Here we bring back the social context a little bit by looking at this as a simple model of human evolution, too.

We can combine the two models, by looking at little circles and squares of different colors inside a grid, and seeing how the population will evolve with time. The results we observe are that we do see cooperation emerge, but sadly it is an ethnocentric sort of cooperation. We can see it from the below graph where the y-axis is proportion of cooperative interactions: the higher up you are in the graph, the more cooperation is happening, so the better it is. In the blue model we have agents that can distinguish between circles and squares living inside a spatial lattice. In the green we see a model with spatial structure, but no cognitive ability to adjust based on tags. In the red and the yellow you can see models where there is no spatial structure, or there is no ability to recognize people based on if they are a circle or a square. In these restricted models cooperation does not consistently emerge. Although in the tags with no space model in yellow there is occasional bifurcation of cooperation highlighted by the black circle and arrow.

Annotated reproduction of figure from Kaznatcheev & Shultz 2011

Proportion of cooperation versus evolutionary cycle for four different conditions. In blue is the standard H&A model; green preserves local child placement but eliminates tags; yellow has tags but no local child placement; red is both inviscid and tag-less. The lines are from averaging 30 simulations for each condition, and thickness represents standard error. Figure appeared in Kaznatcheev & Shultz (2011).

This gives us a suggestion of how evolution could have shaped the way we are today, and how evolution could have shaped the common trend of ethnocentrism in humans. The model doesn’t propose ways to overcome ethnocentrism, but one thing it does is at least create cooperation among scientists who use it. In particular, the number of different fields (represented in one of my favorite xkcd comics, below) that use these sort of models.

Sociologists and political scientists use these models for peace building and conflict resolution (eg. Hammond & Axelrod, 2006). In this case cooperation would be working towards peace, and defection could be sending a mortar round into the neighboring village. Psychologists look at games like the Prisoner’s dilemma (or the Knitter’s dilemma in my case) and say “well, humans tend to cooperate in certain settings. Why is that? Can we find an evolutionary backing for that?” In our running example by looking at ethnocentrism (eg. Shultz, Hartshorn, & Kaznathceev, 2009). Biologists look at how the first molecules came together to form life, or how single cells started to form multi-cellular organisms. Even in cancer research (eg. Axelrod, Axelrod, & Pienta, 2006) and the spread of infectious disease such as the swine flu (eg. Read & Keeling, 2003). Even chemists and physicists use this as a model of self-organizing behavior and a toy model of non-linear dynamics (eg. Szabo & Fath, 2007). Of course, it comes back to computer scientists and mathematicians, who use this for studying network structure and distributive computing. The reason all these fields can be unified by the mathematical idea underlying evolution seems kind of strange. The reason this can happen is because of the simple nature of evolution. Evolution can occur in any system where information is copied in a noisy environment. Thus, all these fields can cooperate together in working on finding answers to the emergence and evolution of cooperation. Hopefully, starting with the scientists working together on these questions, we can get people around the world to also cooperate.


Axelrod, R., Axelrod, D. E., & Pienta, K. J. (2006). Evolution of cooperation among tumor cells. Proceedings of the National Academy of Sciences, 103(36), 13474-13479.

Hamilton, W. D. (1964). The Genetical Evolution of Social Behavior. Journal of Theoretical Biology 7 (1): 1–16.

Hammond, R. A., & Axelrod, R. (2006). The evolution of ethnocentrism. Journal of Conflict Resolution, 50(6), 926-936.

Kaznatcheev, A., & Shultz, T.R. (2011). Ethnocentrism Maintains Cooperation, but Keeping One’s Children Close Fuels It. Proceedings of the 33rd Annual Conference of the Cognitive Science Society, 3174-3179

Lenski, R. E., & Velicer, G. J. (2001). Games microbes play. Selection, 1(1), 89-96.

Nowak MA (2006). Five rules for the evolution of cooperation. Science (New York, N.Y.), 314 (5805), 1560-3 PMID: 17158317

Nowak, M. A., & Sigmund, K. (1998). Evolution of indirect reciprocity by image scoring. Nature, 393(6685), 573-577.

Read, J. M., & Keeling, M. J. (2003). Disease evolution on networks: the role of contact structure. Proceedings of the Royal Society of London. Series B: Biological Sciences, 270(1516), 699-708.

Shultz, T. R., Hartshorn, M., & Kaznatcheev, A. (2009). Why is ethnocentrism more common than humanitarianism. In Proceedings of the 31st annual conference of the cognitive science society (pp. 2100-2105).

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

Trivers, R. L. (1971). The evolution of reciprocal altruism. Quarterly review of biology, 35-57.

Slides for Roca, Cuesta & Sanchez’s EGT: Temporal and spatial effects beyond replicator dynamics

Last Wednesday, October 10th, 2012 we discussed Roca, Cuesta & Sanchez (2009) Evolutionary games theory: Temporal and spatial effects beyond replicator dynamics. The hope was to have a review as amazing as Szabo & Fath (2007), and we divided the work in a similar way.

  • Thomas Shultz presented Section 2: Basic concepts and results of evolutionary game theory.
  • Marcel Montrey presented Section 4: Structured populations.

I covered section 3 (The effects of different time scales) but without slides; I am still a fan of the blackboard. Tom’s slides provide an exposition of the basic model of the replicator equation, and closely follow Nowak’s Evolutionary Dynamics. I recommend these slides if you need a quick reminder. Unfortunately, the rest of the paper did not build on the equation (as you would expect from title) but provided (mostly) simulation based alternatives. Section 3 discussed the observation that having a different number of interactions per generation sets the speed of evolution. Evolution is fast is there are few interactions per generation, and slow otherwise. Fast evolution leads to more noise in the population, making it harder to stay in shallow optima. Unfortunately, they do not present cases where this results in a change of optima, like the low pairings we saw in Riolo, Cohen & Axelrod (2001). In his slides, Marcel does a great job of stressing the key insight RCS09 provide in section 4: the importance of update rules. The authors focus exclusively on simulation work, and point out the inconsistencies that can arise from seemingly minor changes in update rules. For the rest of the discussion of spatial structure, they do not go beyond Szabo & Fath and Marcel’s spatial structure post.

In all honesty, I was expecting a more analytic treatment from this Physics of Life Review, and was disappointed about the disconnect from the greatest strength of replicator dynamics: the intuitiveness of an analytic toolkit. Carlos P. Roca, José A. Cuesta, & Angel Sánchez (2009). Evolutionary game theory: Temporal and spatial effects beyond replicator dynamics Physics of Life Reviews, 6, 208-249 arXiv: 0911.1720v1