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.

I want to start with a disclaimer, and explanation of why I tend to favour the assumptions description. No matter what you do, if you are measuring, observing, or reasoning about the empirical world then you have to make assumptions. If you think otherwise then you are wrong. To correct this, you should read about Popper’s theory-laden observation and then meditate on Jacob Scott’s post about mental models. If you are like me and have an irrational love of finding minimal sets of assumptions then I recommend looking into Russell’s thoughts on non-demonstrative inference, in particular the 5 postulates he introduces in Human Knowledge (1948). This means that even when we are talking about approximations, we will still need to discuss assumptions.

So why talk about approximations at all then? The assumptions that we usually require for our models are too strict and specific to be realized in practice, but we still use these models as ‘approximate’, ‘good enough’, or ‘best we can do’. However, by making these statements of approximation outside of any framework, they become untestable and meaningless — just hunches. The classic example is homo economicus; most of neoclassical economics is built on the assumption of rational agents. Yet, at least since the time of Tversky and Shafir (1992), every economist realizes that humans are not rational and continues to use these models because they are ‘approximately’ correct. What sense of ‘approximate’ is meant here? From just the assumptions we cannot conclude anything about the approximation, instead the experimenters that test these deviations from rationality need to come up with ad-hoc frameworks that can represent both rational and irrational behavior and then explore inside these frameworks.

Instead, we will start with a loose framework based on assumptions that have a chance of satisfying in practice (of course, this is still an aesthetic judgement) and build up our model within it. For the case of evolutionary game-theoretic models, we want to have both evolution and game-theory as assumptions. Hence, we suppose that agent fitness depends only on some static intrinsic factors and the outcome of pairwise interaction with other agents. We also suppose that short-term reproductive success of each agent is a monotonically increasing function in the focal agents fitness, and monotonically decreasing function in the average agent fitness (where we don’t yet specify the distribution used for computing averages).

Just from this, we get out zeroth-order approximation of evolutionary dynamics. The roughest guess we can make of the probability of interacting with another agent is just to say that we sample agents from a distribution given by their proportion in the population — a mean-field approximation. This gives us a utility function for agents of type i as [Gx]_i where G_{ij} is the payoff of an agent of type i interacting with an agent of type j and x is a vector of proportions of agents of each type. From here on in, our hands are tied and the math forces us to replicator dynamics: \dot{x}_i = x_i([Gx]_i - x^TGx).

However, if we want ask a question of how the size of interaction neighborhood affects dynamics — as we do in our study of the edge-effect (Kaznatcheev, Scott, & Basanta, 2013) — then we can’t even express that question in this model since the perfect sampling used in the calculation of fitness effectively makes interactions global. To overcome this, we can say that instead of the fitness being the mean-field [Gx]_i, we instead sample M interaction partners from the distribution given by x and use these local interaction groups for our fitness calculation. This would be our 0.5-order approximation (the name will make sense in a bit), and the strategy pursued by Hilbe (2011). If we turn our math-crank with this new assumption then Hilbe (2011) showed that the result is still replicator dynamics (although with a different time-scale that is irrelevant to the functional form) but with a modified payoff matrix G' = G + \frac{1}{M - 2}(G - G^T). This is a great way to reintroduce some local effects, but the groups of M agents are constantly re-sampled and fitness-competition still happens at a global level; in other words, there is no spatial structure. Hence the 0.5 and not 1.

To get things completely localized, we will assume a fixed population size, and make our replication procedure more explicit to make a first-order approximation of spatial structure. Since the population size is fixed, we can only get a new agent if an old one dies, this gives us a great way to localize. Once a focal agent dies, there is some neighborhood of the focal agent with k agents that compete for the focal spot. Now, we can have some extra information, instead of just keeping track of the proportion of agents of type i given by x_i, we can keep track of neighbors. More explicitly, we will keep track of proportion x_{ij} meaning, the probability of seeing an agent of type i in the neighborhood of an agent of type j. This technique is known as pair-approximation (Matsuda et al., 1987; van Baalen, 2000).

This tells us who is competing for for the vacated spot, but it doesn’t let us calculate their fitness because we would need to know the probability x_{ijk} of seeing an agent of type i near an agent of type j and k. To update that probability, we would need to know more long range effects like x_{ijkl}, etc. Hence, for a first-order approximation, we truncate the series here and approximate the further effects by saying that x_{ijk} = x_{ij}. Working under these assumptions, Ohtsuki and Nowak (2006) showed that we still get replicator dynamics but with a modified payoff matrix G” given by:

G'' = G + \frac{1}{k-2}(\Delta\vec{1}^T - \vec{1}\Delta^T) + \frac{1}{k(k - 1) - 2}(G - G^T)

Where vector \Delta which is the diagonal of the game matrix G, i.e. \Delta_i = G_{ii} and latex \vec{1}$ is the all ones vector; thus \Delta\vec{1}^T (\vec{1}\Delta^T) is a matrix with diagonal elements repeated to fill each row (column). Note that we have k agents competing for a spot, and each one samples k – 1 other agents (since one spot they are neighboring was just vacated) so M = k(k – 1). Thus, the last term is Hilbe’s (2011) finite sampling effect and the first term is the spatial structure.

Since we assumed that the neighbors of the perished agent i are drawn from the same sort of distribution as the neighbors’ neighbors, we have ignored extra correlations that might arise from looking out to distance two or more, hence the first order nature of the approximation. As I’ve described in the assumptions version of this post (see that version for a visual demonstration of the transform’s effect on all cooperate-defect games), the approximation is only exact for infinite Beth-lattices and relative good for k-regular random graphs. If we were looking at other graph structures like grids then higher order terms would dominate.

The fun part of this presentation is that it shows us that we don’t need to assume our spatial structure is a graph. We just need to think in terms of sampling k times from distributions of agents’ neighbors with some locality assumptions on these distributions (i.e. the distribution becomes effectively biased to return focal similar agents, also known as local-child placement). Since Ohtsuki & Nowak (2006) have a seperation of time-scales in their analysis, effects of the graph beyond this random sampling are not preserved anyway. Thus, this approximation technique is generally applicable, even to strangle structured settings like a solid tumor. Of course, like any first-order approximation, if higher-orders are important then it will not agree with experimental data. However, if we just look at data without a first-order theory then we wouldn’t even know that higher-order terms are important. Thus, the first-order approximation is always a good first step; if empirical results contradict it then at least we know where to look, second-order and higher correlations in the distributions of neighbors.


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

Kaznatcheev, A., Scott, J.G., & Basanta, D. (2013). Edge effects in game theoretic dynamics of spatially structured tumours. arXiv: 1307.6914v2.

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.

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

Russell, B. (1948). Human Knowledge: It’s Scope and Limits. London: Routledge.

Shafir, E., & Tversky, A. (1992). Thinking through uncertainty: Nonconsequential reasoning and choice. Cognitive Psychology, 24: 449-474.

Tversky, A., & Shafir, E. (1992). The disjunction effect in choice under uncertainty. Psychological Science, 3: 305-309.

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.


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.

9 Responses to Approximating spatial structure with the Ohtsuki-Nowak transform

  1. Reblogged this on CancerEvo and commented:
    Artem is the mathematical brains behind a project where he, Jacob Scott and myself have worked to come with a simple (a first order approximation) game theoretical model of the effect of edges on growing tumours. To do so we have used the Ohtsuki-Nowak transform. Here Artem explains the philosophy of our approach.

  2. Pingback: Misleading models in mathematical oncology | Theory, Evolution, and Games Group

  3. Pingback: Cataloging a year of blogging: cancer and biology | Theory, Evolution, and Games Group

  4. Pingback: Space and stochasticity in evolutionary games | Theory, Evolution, and Games Group

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

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

  7. Pingback: Operationalizing the local environment for replicator dynamics | Theory, Evolution, and Games Group

  8. Pingback: Boundaries and evolutionary dynamics in cancer | CancerEvo

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

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