How to analyze models of nonlinear public goods

Archetti, Marco Article How to analyze models of nonlinear public goods Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Archetti, Marco (2018) : How to analyze models of nonlinear public goods, Games, ISSN 2073-4336, MDPI, Basel, Vol. 9, Iss. 2, pp. 1-15, https://doi.org/10.3390/g9020017 This Version is available at: https://hdl.handle.net/10419/179177 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ games Review How to Analyze Models of Nonlinear Public Goods Marco Archetti ID School of Biological Sciences, University of East Anglia, Norwich Research Park, Norwich NR4 7TJ, UK; [email protected] Received: 28 February 2018; Accepted: 3 April 2018; Published: 4 April 2018   Abstract: Public goods games often assume that the effect of the public good is a linear function of the number of contributions. In many cases, however, especially in biology, public goods have nonlinear effects, and nonlinear games are known to have dynamics and equilibria that can differ dramatically from linear games. Here I explain how to analyze nonlinear public goods games using the properties of Bernstein polynomials, and how to approximate the equilibria. I use mainly examples from the evolutionary game theory of cancer, but the approach can be used for a wide range of nonlinear public goods games. Keywords: game theory; public goods; cooperation; nonlinear games; evolutionary dynamics; Bernstein polynomials; cancer 1. Introduction 1.1. Public Goods Fifty years after Garret Hardin’s “Tragedy of the Commons” [ 1 ], the problem of collective action remains one of the most influential concepts in science: free-riding on the contributions of others enables free-riders to thrive at the expense of cooperators. Examples can be found in almost all areas of human knowledge, from biology to economics, from selfish genetic elements [ 2 ], microbes secreting diffusible molecules [ 3 ] and cancer cells secreting growth factors [ 4 , 5 ] to cooperative hunting in mammals [ 6 ] and, indeed, the exploitation of shared natural resources described by Hardin [ 1 ]. The major transitions in evolution are considered solutions to social dilemmas of this kind [7]. The problem of cooperation can be modelled by games with at least one Pareto inefficient equilibrium: an alternative outcome exists in which at least one player could have a higher payoff without reducing any other player’s payoff (a Pareto improvement is possible; hence the inefficiency); no one, however, has an incentive to change their behavior (hence the equilibrium). The Prisoner’s Dilemma (PD) [ 8 ] is the most famous among such games, and it has been used extensively to describe the problem. The game of Chicken [ 9 ] (also known as the Hawk–Dove game [ 10 ] or the Snowdrift game [11]) has also been used to study cooperation. 1.2. Multiplayer Games and Nonlinear Benefits The social dilemma described by Hardin [ 1 ] is essentially a multiplayer version of the PD (NPD [ 12 , 13 ]): individuals can be cooperators or defectors; only cooperators pay a contribution; all contributions are summed, the sum is multiplied by a reward factor and redistributed to all individuals. It is well-known and easy to prove that in this game, if group size is large enough, pure defection is the only stable outcome. The n-person prisoner’s dilemma (NPD) has become a synonym for social dilemma and the tragedy of the commons, at least in biology [ 14 ] (while in economics it is understood [ 15 ] that this is not necessarily the case). This is unfortunate, because very few cases of public goods in biology can actually be described as an NPD. The reason is that the NPD assumes linear benefits: the effect of each contribution is additive. In other words, the public good is a linear function of the number of cooperators. Games 2018,9, 17; doi:10.3390/g9020017 www.mdpi.com/journal/games Games 2018,9, 17 2 of 15 In biology, however, almost everything is nonlinear. The effect of biological molecules is generally a sigmoid function of their concentration (usually described by the Hill equation [ 16 – 18 ]). A case in point is the production of growth factors by cancer cells: since they are diffusible in the extracellular matrix, growth factors are public goods that can be exploited by producer and non-producer cells. In cancer research, game theory was introduced [ 19 , 20 ] using a version of the game of Chicken. Subsequent papers using game theory in cancer research [ 21 – 28 ] were extensions (with up to four strategies) of this game, and games with pairwise interactions continue to be used in cancer research [ 29 , 30 ]. The production of diffusible factors by cells, however, is a clear example of collective interactions rather than pairwise, because the effect of secreted molecules is not limited to one other cell. The dynamics of growth factor production therefore should be modelled using games with collective interactions [ 31 , 32 ]. It is also well known that the effect of growth factors on cell growth is generally a sigmoid function of its concentration. In order to describe cooperation for the production of growth factors in cancer biology, therefore, we must use multiplayer games with collective interactions for the production of nonlinear public goods—in short, nonlinear public goods games. 1.3. Rationale of the Paper The problem with nonlinear public goods games is that they are hard to analyze. While games with concave and convex benefits can be studied analytically, and approximate results can be derived for games with threshold benefits, games with sigmoid benefits have been considered impossible to study analytically until recently [ 32 ]. Recent work on nonlinear public goods [ 33 – 36 ] has been applied to the production of diffusible molecules in cancer [ 37 – 44 ]. Some other recent models have used linear benefits [45,46]. Here I show how to characterize analytically the dynamics of nonlinear games and how to find the equilibria analytically for well-mixed populations. I will also show how the results differ from linear and pairwise games and why glossing over nonlinearities can lead to crucial errors. 2. How to Analyze Nonlinear Public Goods Games 2.1. The Replicator Dynamics with Two Strategies In a game with two pure strategies, an individual can be a producer (cooperator) or a non-producer (defector) of a public good. The diffusion range of the public good defines a number nof individuals that benefit from its effect (group size is n). We assume a large population and random group formation at each generation. Thus, one’s probability of having a number iof producers among the other group members, given that the frequency of producers in the population is x, is given by the probability mass function of a binomially distributed random variable iwith parameters (n−1, x): pi,n−1(x)= n−1 i!xi(1−x)n−1−i(1) The fitnesses of producers and non-producers are given therefore by WC= n−1 ∑ i=0 pi,n−1(x)·b(i+1)−c(2) WD= n−1 ∑ i=0 pi,n−1(x)·b(i)(3) where b(i) is the benefit (payoff) for being in a group with iother cooperators; a producer has one producer (itself) more in a group, compared to a non-producer in the same group, but it pays a cost c Games 2018,9, 17 3 of 15 (0 < c< 1); if we assume that the maximum benefit is 1 and cis the cost/benefit ratio of cooperation. The average fitness of a mixed population is W=x·WC+(1−x)·WD(4) The replicator dynamics [47] of this system is . x=x(1−x)β(x)(5) where the fitness difference WC−WDis written in the form β(x), and β(x)=∑n−1 i=0pi,n−1(x)·∆bi(6) is the gradient of selection, with ∆bi=b(i+1)−c−b(i)(7) Beyond the two trivial rest points x= 0 and x= 1, further interior rest points are given by β(x)=0 (8) When b(i) is a linear function, (8) can be easily solved analytically [ 25 ]. With non-linear benefits, however, this is generally not possible. 2.2. Nonlinear Benefits Many cases of nonlinear benefits can be modelled using the following function. The benefit b(i) for an individual in a group with a number iof producers and a number (n − i) of non-producers is described by b(i)=[l(i)−l(0)] [l(n)−l(0)] (9) the normalized version of a logistic function l(i) with inflection hand steepness s: l(i)=1 1+es(h−i/n)(10) The parameter hdefines the position of the inflection point: h → 1 gives increasing returns and h → 0 diminishing returns; sdefines the steepness of the function at the inflection point (s →∞ models a threshold public goods game; s → 0 models an NPD; the normalization in (9) in prevents the logistic function (10) from becoming constant for s→0) (Figure 1). Figure 1. Sigmoid benefits. The benefit b(i) of a public good as a function of the number of producers (i), described by a normalized logistic function (Equation (9)) with inflection point h;h → 1 gives increasing returns and h → 0 diminishing returns. Multiple curves are shown, with increasing steepness s(increasing opacity). Games 2018,9, 17 4 of 15 When the benefit b(i) is a nonlinear function such as the one in (9) the roots of β in (6) cannot be found analytically. We can, however, characterize the dynamics exactly, and approximate the equilibria, by resorting to the properties of Bernstein polynomials. 2.3. Bernstein Polynomials Bernstein polynomials were introduced 100 years ago by Sergei Natanovich Bernstein [ 48 ] in order to constructively (employing only basic algebra) prove the Weierstrass approximation theorem: given any continuous function f(x) on an interval [a,b] and a tolerance ε > 0, a polynomial P(x) of sufficiently high degree exists, such that |f(x) − P(x)|< ε for all xin [a,b]; in other words, polynomials can uniformly approximate any continuous function over a closed interval. Bernstein polynomials are a significant advance over Taylor polynomials, as they are applicable to any continuous function, whereas the Taylor approximation requires the function to be differentiable. Probably because of their slow convergence, however, Bernstein polynomials were for a long time (and still are) a relatively unknown tool in mathematics. A review of the history of Bernstein polynomials [ 49 ] and a full treatment are available [50–52]. For our purposes, the following definitions are enough to set the problem. •The Bernstein polynomial basis of degree non xin [0, 1] is defined, for i= 0, . . . , n, by pi,n(x)= n i!xi(1−x)n−i(11) • Apolynomial in Bernstein form of degree nassociated with any continuous function f i on [0, 1] is defined for each positive integer nas F(x)∑n i=0pi,n(x)fi(12) •fiis called the Bernstein coefficient The following properties of Bernstein polynomials are sufficient to characterize the dynamics of our system (see [49] for a complete list of properties, and [50–52] for further discussion): •End-point values: The initial and final values of fand F are the same: F(0) = f0; F(1) = fn. •Shape preservation: F and fhave the same shape (monotonicity, convexity, concavity). • Variation-diminishing property: The number Zof real roots of F in (0,1)is less than the number Sof sign changes of fby an even amount: Z=S − 2jfor some integer jgreater or equal to 0 and lower than the integer part of n/2 [53] (each root contributes according to its multiplicity). 2.4. Characterizing the Dynamics Compare (11) with (1) and (12) with (6); β in (6) is, by definition, a polynomial in Bernstein form and ∆ b i is its Bernstein coefficient. Hence, based on the properties defined above, it is straightforward to characterize the dynamics of a nonlinear public goods game based on the number of sign changes of the Bernstein coefficient ∆ b i instead of inspecting the gradient of selection of the Bernstein polynomial β . This Bernstein approach was introduced to study public goods games with sigmoid benefits in the context of cancer biology [ 39 , 40 ]. Games with concave or convex benefits can be analyzed [ 54 ] without resorting to the properties of Bernstein polynomials, although in that case the proof is unnecessarily long—the proof is trivial using the Bernstein approach (the results of this exercise have been published in [55], which also replicated the sigmoid case analyzed in [39]). For games in which the Bernstein coefficient never changes sign, obviously, there is no interior equilibrium. An example of this case is the NPD. Games with concave or convex benefits are cases in which there can be at most one sign change (Figure 2). If the Bernstein coefficient has one sign change, then there is a unique interior equilibrium Games 2018,9, 17 5 of 15 x* in (0,1): if the initial sign is +, then x* is stable and x= 0 and x= 1 are unstable: an example of this occurs in games with concave benefits when ∆ b n−1 <c< ∆ b 0 ; if the initial sign is -, then x* is unstable and x= 0 and x= 1 are stable: an example of this occurs in games with convex benefits when ∆ b 0 <c< ∆ b n−1 . Games with concave or convex benefits can also have no sign change. Hence, with concave benefits, if c ≥∆ b 0 then x= 0 is the unique stable equilibrium and x= 1 is the unique unstable equilibrium; if ∆ b n−1 <c< ∆ b 0 then there is a unique interior stable equilibrium and x= 0, x= 1 are unstable equilibria; if c ≤∆ b n−1 then x= 1 is the unique stable equilibrium and x= 0 is the unique unstable equilibrium. With convex benefits, if c ≥∆ b n−1 then x= 0 is the unique stable equilibrium and x= 1 is the unique unstable equilibrium; if ∆ b 0 <c< ∆ b n−1 then there is a unique interior unstable equilibrium and x= 0, x= 1 are stable equilibria; if c ≤∆ b 0 then x= 1 is the unique stable equilibrium and x= 0 is the unique unstable equilibrium. In summary, games with concave or convex benefits can have at most one interior equilibrium, either stable or unstable (Figure 2). Figure 2. The gradient of selection β (bottom panels, continuous blue line) and its Bernstein coefficient ∆ b i (bottom panels, dotted line) for different types of benefit functions (top panels): concave (n= 9, h= 0.1, s= 10, c= 0.1); convex (n= 9, h= 0.9, s= 10, c= 0.1); sigmoid (n= 10, h= 0.4, s= 9, c= 0.1); step function (n= 9, h= 0.4, s= 1000, c= 0.1). Arrows show the direction of the dynamics (determined by the sign of the gradient of selection); squares show the equilibria (full: stable; empty: unstable). The Bernstein approach is however essential to characterize the dynamics of games with sigmoid benefits [ 39 , 40 ]. If bis sigmoid, that is an h(the inflection point) exists such that ∆ b i is increasing for i<h, decreasing for i>h, and satisfies ∆ b i6= 0 ∀ i, then ∆ b i is single-peaked and can have at most two sign changes (Figure 3); thus, there are either two interior rest points, or one (if they coincide) or zero, and the dynamics can be characterized as follows: • If c ≥βMAX (the maximum value of β ) there is a unique stable equilibrium x= 0 (producers go extinct) (c1in Figure 3) • If Max[ ∆ b 0 , ∆ b n−1 ] ≤ c< βMAX there are two stable equilibria: a pure equilibrium x= 0 made of all non-producers and a mixed equilibrium x*; the basins of attraction of these two equilibria are separated by a mixed unstable equilibrium xˆ; if the initial frequency of producers x<xˆ the population will evolve to x= 0; if x>xˆ it will evolve to x* (c2in Figure 3). • If ∆ b 0≤ c< ∆ b n−1 (this case can exist only for h> 0.5) there is a unique interior unstable equilibrium xˆ separating the basins of attraction of two pure stable equilibria: x= 0 and x= 1; if x<xˆ the population will evolve to x= 0; if x>xˆ it will evolve to x=1(c3in Figure 3). • If ∆ b n−1≤ c< ∆ b 0 (this case can exist only for h< 0.5) there is a unique interior stable equilibrium x*, to which the population will converge irrespective of the initial frequencies of the two types (c3in Figure 3). Games 2018,9, 17 6 of 15 • If c< Min[ ∆ b 0 , ∆ b n−1 ] there is a unique stable equilibrium x= 1 (non-producers will go extinct) (c4in Figure 3). Figure 3. Types of dynamics when the benefit is a sigmoid function. The gradient of selection β (continuous blue line) and its Bernstein coefficient ∆ b i (dotted line); squares show the equilibria (full: stable; empty: unstable) for different values of c(gray lines); arrows show the direction of the dynamics (determined by the sign of the gradient of selection); s= 5; n= 9, h= 0.4 or 0.6. In summary, nonlinear games with collective interactions in which the benefit is a sigmoid function of the frequency of cooperators can have at most two internal equilibria, one of which can be stable (Figure 3). The dynamics is the same for any benefit function in which ∆ b i increases for i < h and decreases for i>h. Figure 4shows two examples of a more complex benefit function, and a case in which the benefits of the two strategies are different functions. Figure 4. The gradient of selection β (continuous blue line) and its Bernstein coefficient ∆ b i (dotted line) for more complex functions; squares show the equilibria (full: stable; empty: unstable); arrows show the direction of the dynamics (determined by the sign of the gradient of selection); A: The double inverse sigmoid function described in (13) (n= 10, h 1 = 0.4, h 2 = 0.2, s 1 = 10, s 2 = 10, c= 0.1, y= 2, d= 0.5). B: Two different benefit functions described by (16) and (17) (n= 10, h 1 = 0.6, h 2 = 0.2, s 1 = 5, s 2 = 20, c= 0.1). Games 2018,9, 17 7 of 15 Figure 4A shows the dynamics for the upregulation of glycolysis in cancer cells (the “Warburg effect”)—another example of cooperation for the production of a public good [ 40 ] (as it is energetically inefficient under adequate oxygen supply, glycolysis is costly; the products of glycolysis, however, induce the acidification of the microenvironment, which is beneficial to all cancer cells, irrespective of their metabolism). To take into account the possibility that high levels of glycolysis are detrimental to tumor cells (self-poisoning) we must use a double sigmoid function, monotonically increasing for i<d and monotonically decreasing for i>d: b(i)=   b1(i)=[l1(i)−l1(0)] [l1(d·n)−l1(0)] f or i <d·n b2(i)=1−[l2(i,y)−l2(d·n,y)] [l2(n,1)−l2(d·n,1)] f or i ≥d·n(13) where l1(i)=1 1+es1(h1−i/nd)(14) l2(i,y)=y 1+es2[h2−(i/n−d 1−d)] (15) The parameter ddescribes the value of iat which the benefits of acidity are overcome by the deleterious effects of self-poisoning; for i<dn, the function is monotonically increasing and has an inflection point at h 1 and steepness s 1 ; for i>dn, the function is monotonically decreasing and has an inflection point at h 2 and steepness s 2 (with 0 < h 1 ,h 2≤ 1 and s 1 ,s 2 > 0); the additional parameter ymeasures the maximum damage of self-poisoning. While analyzing the gradient of selection with benefits given by (13) appears hopeless, the Bernstein approach enables us to characterize the dynamics simply by looking at the number and type of sign changes of the Bernstein coefficient, as shown in Figure 4A. Figure 4B shows another class of games that appear analytically unsolvable but that are easily characterized using the Bernstein approach. In tumor-stroma interactions, the fitness of cancer cells is an increasing function of the fraction of stromal cells, while the fitness of stromal cells is an increasing function of the fraction of cancer cells (because of stroma and tumor exchange growth factors that are mutually beneficial). Figure 4B shows the simplest model of this scenario with benefit functions for the tumor and stroma increasing in opposite directions, that is, given by: g1(i)=1 1+es1(h1−i/n)(16) g2(i)=1−1 1+es2(h2−i/n)(17) 2.5. Comparison with Pairwise and Linear Games Let us consider again the case of sigmoid benefits. Note how the steepness of the benefit function affects the dynamics (Figure 5): as we have seen, games with linear benefits (s → 0) have no interior equilibria; as steepness increases interior equilibria, stable and (or) unstable, arise; also note that the approximation of the gradient of selection to its Bernstein coefficient is less accurate as sincreases, and becomes inaccurate when the sigmoid function approaches a step function (s→∞). Figure 5also shows an example of the difference between games with pairwise interactions and collective interactions. Two-player games are a special case of collective games with n= 2 and thus there are only one or zero sign changes; not surprisingly, therefore, there are only four possible types of sign change (always +; always − ; from + to − ; from − to +) and therefore four possible types of dynamics and four types of equilibria in games with two strategies with pairwise interactions (the same types we saw for concave and convex benefits). Games 2018,9, 17 8 of 15 Figure 5. Effect of sand n. The gradient of selection β (continuous blue line) and its Bernstein coefficient ∆bi(dotted line) in public goods games with sigmoid benefits, for different values of s(n= 10, h= 0.4, c= 0.05) or for different values of n(s= 10, h= 0.4, c= 0.05); squares show the equilibria (full: stable; empty: unstable); arrows show the direction of the dynamics (determined by the sign of the gradient of selection). 2.6. Finding the Equilibria We can find the internal equilibria analytically by setting to zero, instead of the gradient of selection, its Bernstein coefficient ∆ b i , resorting to an additional property of Bernstein Games 2018,9, 17 15 of 15 54. Motro, U. Cooperation and defection, playing the field and the ESS. J. Theor. Biol. 1991 ,151, 145–154. [CrossRef] 55. Pena, G.; Lehmann, L.; Noeldeke, G. Gains from switching and evolutionary stability in multi-player matrix games. J. Theor. Biol. 2014,346, 23–33. [CrossRef] [PubMed] 56. Voronovskaya, E. Détermination de la forme asymptotique d’ approximation des fonctions par les polynômes de M. Bernstein. CR Acad. Sci. URSS 1932,79, 79–85. 57. Mabry, R. Problem 10990. Am. Math. Mon. 2003,110, 59. [CrossRef] 58. Hamilton, W.D. The genetical evolution of social behaviour. J. Theor. Biol. 1964,7, 1–52. [CrossRef] 59. Frank, S.A. Foundations of Social Evolution; Princeton University Press: Princeton, NJ, USA, 1998. 60. Nowak, M.A. Evolutionary Dynamics; Harvard University Press: Cambridge, MA, USA, 2006. 61. Axelrod, R.; Hamilton, W.D. The Evolution of cooperation. Science 1981 ,211, 1390–1396. [CrossRef] [PubMed] 62. Greig, D.; Travisano, M. The Prisoner’s Dilemma and polymorphism in yeast SUC genes. Proc. R. Soc. Lond. Ser. B 2004,27, S25–S26. [CrossRef] [PubMed] 63. Gore, J.; Youk, H.; van Oudenaarden, A. Snowdrift game dynamics and facultative cheating in yeast. Nature 2009,459, 253–256. [CrossRef] [PubMed] 64. MacLean, R.C.; Fuentes-Hernandez, A.; Greig, D.; Hurst, L.D.; Gudelj, I. A Mixture of “Cheats” and “Co-Operators” Can Enable Maximal Group Benefit. PLoS Biol. 2010,8, e1000486. [CrossRef] [PubMed] © 2018 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).