Bernstein polynomials and non-linear public goods in tumours

By analogy, or maybe homage, to standard game theory, when we discuss the payoffs of an evolutionary game, we usually tell the story of two prototype agents representing their respective strategies meeting at random and interacting. For my stories of yarn, knitting needles, and clandestine meetings in the dark of night, I even give these players names like Alice and Bob. However, it is important to remember that these are merely stories, and plenty of other scenarios could take their place. In the case of replicator dynamics there is so much averaging going on that it is often just better to talk about the payoffs as feedback between same-strategy sub-populations of agents. The benefit of this abstraction — or vagueness, if you prefer — is that you don’t get overwhelmed by details — that you probably don’t have justification for, anyway — and focus on the essential differences between different types of dynamics. For example, the prisoner’s dilemma (PD) and public goods (PG) games tell very different stories, but in many cases the PD and linear PG are equivalent. Of course, ‘many’ is not ‘all’ and my inclusion of ‘linear’ should prompt you to ask about non-linear public goods. So, in this post I want to provide a general analysis of replicator dynamics for non-linear public goods games following the method of Bernstein polynomials recently used by Archetti (2013, 2014). At the end, I will quickly touch on the two applications to mathematical oncology that Archetti considers. SInce I am providing a more general analysis, I will use notation inspired by Archetti, but defined more precisely and at times slightly differently — some symbols will be the same in name but not in value, so if you’re following along with the paper then pay close attention.

Public goods games

Let’s start with a story. In most biological contexts, we think of a public good as some sort of substance that is released into the ambient space that the cells inhabit and that diffuses out to some distance. This substance can be consumed by the agent that released it but also other agents in order to gain some sort of fitness effect, usually positive — hence public “good” and not “bad”. The effects need not be direct. For instance, when modeling oxygination the public good would be the oxygen that cells use for respiration while the relevant molecule that cells release is vascular endothelial growth factor (VEGF) that causes blood vessels to grow and thus deliver oxygen. In this example, the specific molecule released is only indirectly related to the public good that it causes. This level of indirect-ness is not atypical, because the physical molecules that cells release usually undergo at least some sort of transformation in the ambient environment before they are consumed.

For simplicity, we will assume that the strategy that causes an increase in the public-good — such as the cells making VEGF; we will call this strategy cooperators — pay some fixed cost c to create the good. This cost is usually not the exact cost of producing the mediating molecule, but some amortization over the whole population of producers that takes into account things like probability of producing the molecule. Since we want to keep the model inviscid, we incorporate the diffusion distance not as a physical distance but as a count n of agents other than the focal agent that partake in the good — if you want to get this n from some physical distance then just take the volume that the distance corresponds to and multiply by the density of cells. Now, we suppose that we have n_c cooperators and n_d defectors — defectors are agents that don’t cause an increase in the public-good — with n_c + n_d = n. To get these numbers of cooperators and defectors at each interaction, we sample from the overall strategy distribution. Hence, if the proportion of cooperators is x then our probability of sampling (n_c,n_d) is {n \choose n_c} x^{n_c} (1 - x)^{n - n_c}. The resulting benefit of the public good is then b(\frac{n_c + 1}{n}) if the focal agent is a cooperator (+1 because the focal agent contributes to the public good) and b(\frac{n_c}{n}) if the focal agent is a defector. As an example, if you want a linear public good with multiplicative factor k then you would have b(x) = kcx.

The above results in the fitness functions:

\begin{aligned}  U(C) & = \Bigg( \sum_{n_c = 0}^n {n \choose n_c} x^{n_c} (1 - x)^{(n - n_c)} b(\frac{n_c + 1}{n}) \Bigg) - c \\  U(D) & = \sum_{n_c = 0}^n {n \choose n_c} x^{n_c} (1 - x)^{(n - n_c)} b(\frac{n_c}{n})  \end{aligned}

As always, this gives us the replicator dynamics \dot{x} = x(1 - x)(U(C) - U(D)). We will be interested in knowing if the resulting equation has any non-trivial equilibria (the trivial ones are x = 0 and x = 1), and if so where they are and their stability.

Bernstein polynomials

Even wihout the non-linearily of b, our equations look scary, with the ODE having degree n + 2. Thankfully, a little bit of mathematical analysis will help us greatly simplify our lives — at least in the limit of large n. This bit of analysis is Bernstein’s approximation theorem.

In 1885, Karl Weierstrass — the father of modern analysis — proved a now standard approximation theorem: for every continuous function f defined on a closed interval [0 1] and every \epsilon > 0 there exists a polynomial p such that |f(x) - p(x)| < \epsilon for all 0 \leq x \leq 1 (Pinkus, 2000). Weierstrass’s proof was not constructive, which motivated Sergei N. Bernstein to find a constructive proof. His proof was not the first constructive one, Borel had arrived at a much less elegant construction earlier (for the history, see Pinkus, 2000), but it is the one that will help our public goods game. In particular, Bernstein showed that:

\lim_{n \rightarrow \infty} \sum_{k = 1}^n {n \choose k} x^k (1 - x)^{n - k} f(k/n) = f(x)

where the convergence is uniform — just like for Weierstrass. The proof itself relies heavily on the Chebyshev inequality — see Levasseur (1984) for a modern version of this probabilistic treatment — and a careful unpacking of the proof can give us a good bound on the rate of convergence.

We can now use this theorem to simplify our public goods game. Let \Delta_n b(x) = b(x + 1/n) - b(x) and notice that by the definition of derivative, we have that \lim_{n \rightarrow \infty} \frac{\Delta_n b(x)}{1/n} = b'(x) where the derivative is taken with respect to x. Now, we have in the limit of large n:

\begin{aligned}  U(C) - U(D) & = \Bigg( \sum_{n_c = 0}^n {n \choose n_c} x^{n_c} (1 - x)^{(n - n_c)} \Delta_n b(\frac{n_c}{n}) \Bigg) - c \\  & =  \Bigg( \sum_{n_c = 0}^n {n \choose n_c} x^{n_c} (1 - x)^{(n - n_c)} \frac{1}{n} b'(\frac{n_c}{n}) \Bigg) - c \\  & = \frac{1}{n} b'(x) - c  \end{aligned}

At this point, it is good to pause for a sanity check. If you plug in the linear public goods game then the equation simplifies to c(\frac{k}{n} - 1). From this, we expect the game to have two regimes: selection towards all defectors when k < n, and toward all cooperators when k > n. This is in agreement with more traditional approaches. For example, it is the main mechanism on which the cooperation in Santos et al. (2008) hitchhikes.

Non-linear public goods in tumours

Of course, we didn’t build all this mathematical machinery just to analyze the linear public goods game, we really care about more complicated functional forms for b that are found in biology. For Archetti (2013) this is the sigmoid function associated with production of growth factors, and for the follow up paper (Archetti, 2014) it is the double-sigmoid of acid production due to glycolysis. Depending on how you set the parameters of these benefit functions — as always with EGT, there is no perscription given for how we would go about measuring such parameters in vivo — you get qualitatively different dynamics. Archetti (2013,2014) finds all the typical dynamics of linear games, like pressure toward all cooperation, all defection, and bifurcation around or attraction to a internal fixed point. However, he also finds surprising dynamics like dynamic C of figure 1 (2013; similar dynamics are seen in type 2 of figure 1 in 2014), where there are two internal fixed points (impossible in linear games) with one being a bifurcation and one being an attractor — depending on the initial conditions, the population will go either to all defectors or a coexistence of cooperators and defectors.


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 PMID: 24075895

Levasseur, K.M. (1984). A probabilistic proof of the Weierstrass approximation theorem. Amer. Math. Monthly, 91: 249-250.

Pinkus, A. (2000). Weierstrass and approximation theory. Journal of Approximation Theory, 107(1): 1-66.

Santos, F. C., Santos, M. D., & Pacheco, J. M. (2008). Social diversity promotes the emergence of cooperation in public goods games. Nature, 454(7201): 213-216.


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.

13 Responses to Bernstein polynomials and non-linear public goods in tumours

  1. I have concerns about the derivation carried out by Archetti that leads to the binomial coefficients. This derivation assumes that groups of size n are formed, and that the payoff per individual is the average across all possible group compositions. In other words, each individual takes part in many groups during its life span, and its reproductive success is taken to be the average payoff across all these groups.

    These dynamics are in my opinion a poor reflection of what a cancer cell experiences. A cancer cell does not form groups of random composition with other cells, rather it interacts with its closest neighbours, which to a large extent are constant in time. I don’t think that migration within tumours has been quantified, but I sincerely doubt that cell within one cell cycle interacts with more than a tiny fraction of the entire population.

    Given that many growth factors, such as VEGF, diffuse on the length scale of the entire tumour (otherwise they couldn’t attract blood vessels) it is much more sensible to consider the entire cancer cell population to be a single group.

    What I tried to voice previously on Twitter (blog post still coming, I promise) is that one needs to have some idea of the applicability of mean-field models before applying them to real-world situations. For a given population size (i.e. spatial extent) what migration rate is required for the MF-equation to make sense?

    Here’s a back of the envelope calculation:

    The cell cycle of a tumour cell is often taken to be 24 hours, but this is probably an over-estimate for in vitro conditions. Let’s say 100 hours. The typical size of a tumour is roughly 10 cm. The mean displacement (i.e. square root of mean square displacement) after 100 hours is approximately 100 micrometer(*), i.e. 1/1000 of the assumed linear size. This simple calculation suggest that a tumour cell only visits a small fraction of the tumour before it divides, and hence that MF approaches should be used with caution.

    *The migration data is taken from fig. 1F of “Three-dimensional cell migration does not follow a random walk” ( which used fibrosarcoma cells in 3d-matrix.

    • You are offering a very pertinent critique that I (and most evolutionary game theorists) would agree with: this model does not include spatial structure. It would always be better to have a model with spatial structure, especially if that contributes something interesting to the dynamics and is still solvable. However, those ifs are very important. It is easy to go out and a demand a model with everything plus the kitchen sink, and it is sometimes not that hard to build such a model, especially if you go the route of simulation. But it is not always clear to me that understanding is achieved through such approaches.

      I like to know exactly what features of my model cause something to happen. So even if I was to build a spatial non-linear public goods game, I would still want to know how it works without spatial structure to understand what it is that the spatial aspects contributed. Remember, we have no hope of actually simulating tumor dynamics, the biology and our mathematical/computational tools are nowhere near that, thinking otherwise is just fooling ourselves. Thus, as we work toward more understanding, we have to balance the two opposing forces: the urge for higher complexity that biologists put on us to throw in everything we can think of, and the urge for simplicity that models put on us to understand why certain models work in certain ways. Since I am not a biologist, and since I have no particular strong feelings for one domain of application over another, I prefer to understand why models work in the way they work, and so I tend to lean toward the route of simplicity. I find that this focus on simplicity also makes me a more useful modeler, since over time I start to develop an intuition for the ‘sort of features’ that a model must have in order to get certain results. I would never be able to develop the same intuitions for biology itself, since I am not trained in that field. I could thrust upon biology my intuitions from physics, but people have been doing that for decades now and I am not clear how transformative that has been.

      On the technical aspects of your critique. Even if we did believe that the inviscid model is a ‘perfect’ or ‘good’ model (which again, nobody really believes in this case, it is just a model that we can have a hope to understand), we would not need sampling on the level of the whole tumour (as your arguments about the cells migration time try to make), we would just need the tumour to be relatively homogeneous (not too high of variance) on the length-scales of the cell’s lifetime interaction. The average fitness would then pop-out from averaging over the whole population. That is why I wrote in the opening paragraph:

      In the case of replicator dynamics there is so much averaging going on that it is often just better to talk about the payoffs as feedback between same-strategy sub-populations of agents

      Of course, I am not trying to suggest that I believe that the local variance is low enough to suppress the effects of slightly different growth rates in slightly different parts of the tumour. I have no belief on this, given that I am not a biologist. The biologists probably have intuitions with respect to this, but (I believe that) they also don’t have the proper tools to check their intuitions given that there aren’t good models in place to see if the local variations that are seen are ‘significant enough’ to alter the global dynamics. It is important to build such tools.

      I look forward to your blog post on this. If you want to do an extended post (in the style of TheEGG) that critiques EGT then I would be happy to invite you as a contributor here. That way the discussion does not splinter across multiple blogs. I’ve extended the same invitation to Philipp Altrock based on some of his critiques in the twitter thread started by Jake’s reshare of this post.

  2. Jorge Peña says:

    For more on Bernstein polynomials and evolutionary multiplayer games (e.g., public goods games) you might also want to take a look at this paper by Peña, Lehmann, and Nöldeke (2014):

    A previous version is also posted in the arXiv:

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

  4. Pingback: Double public goods games and acid-mediated tumor invasion | Theory, Evolution, and Games Group

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

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

  7. Pingback: A detailed update on readership for the first 200 posts | Theory, Evolution, and Games Group

  8. Pingback: EGT Reading Group 46-50 and a photo | Theory, Evolution, and Games Group

  9. Pingback: From linear to nonlinear payoffs in the double public goods game | Theory, Evolution, and Games Group

  10. Pingback: Lotka-Volterra, replicator dynamics, and stag hunting bacteria | Theory, Evolution, and Games Group

  11. Pingback: Multiple realizability of replicator dynamics | Theory, Evolution, and Games Group

  12. Pingback: Cataloging a year of cancer blogging: double goods, measuring games & resistance | 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