Evolution of Common-Pool Resources and Social Welfare in Structured Populations

1 Introduction

As argued by Garreth Hardin in his famous paper on the Tragedy of the Commons [Hardin, 1968], the problem of resource sustainability is a question of resolving the conflict between individual and collective interests. This issue of resource sustainability can be easily be extended to technological problems of resource sharing: take for instance, the shared use of dispersed calculation facilities [Buyya et al., 2001] or the sharing of a common communication bandwidth in a distributed robotic system [Wang and Premvuti, 1994]. In all these cases, individual rational decisions may produce a collective irrational outcome, which should be avoided.

∗TL and TAH are supported by FNRS and FWO Belgium.

These examples are referred to as common-pool resource (CPR) or harvesting games as they are all concerned with the exploitation of a finite resource that maintains itself according to its own internal rules [Gardner et al., 1990; Ostrom, 2002]. Even though these problems are of great importance, they have been studied much less in Evolutionary Game Theory (EGT) than the well known public goods games (PG) [Sigmund, 2010]. The latter games start from the premise that each agent needs to contribute something to a common good, as for instance to use of a shared car or a social welfare system. The collective contributions allow the community members to reap a benefit, which would be more costly to achieve by each member on their own. Yet, agents can decide not to contribute and still profit from the system, which may lead to the complete failure of the common good in the long run.

The reason for the bigger focus on the PG game may have been that, until recently, both games were assumed to produce equivalent outcomes, differing only in their framing [McCusker and Carnevale, 1995]; in case of the CPR game, each agent has to decide how much to take from a resource, whereas in the PG she has to decide how much to give. Experiments showed that people differentiate between loosing part of their assets (PG game) and gaining something from an external resource (CPR game). In [Apesteguia and MaierRigaud, 2006] however, it is shown, both theoretically and experimentally, that the fundamental difference between both games lies not in the framing but in the degree of rivalry of the good: In case of the CPR game, the good is rival since whatever is taken by an agent is lost to another agent, which is not the case in the PG game. Consequently, each game produces a distinct strategic environment, which requires a separate analysis.

In a first step towards understanding the importance of this difference while at the same time analyzing the relevance of certain results obtained for the evolutionary dynamics in the PG game, we study here the evolutionary dynamics of simple consumption strategies in finite populations playing the CPR game. We examine the conflict between selfish and cooperative actions and dissect the effect of network topology on the outcome of the game. The CPR game is modeled by a system of two coupled dynamics, i.e. a growth and consumption dynamics, where each agent's actions are defined by a consumption rate (α). As most populations are not infinite, we focus on a finite-population analysis of the game readily used within the field of EGT [Nowak et al., 2004; Imhof et al., 2005], which has to our knowledge never been performed on this type of game. As such this work provides an original perspective on the dynamics of CPR games. The results could potentially contribute to the development of decision models, of increasing complexity, that will be able to assist in managing both natural and technological shared resources [Gomes, 2009].

The remainder of this paper is organized as follows. Section 2 discusses some of the existing literature and compares this with the results obtained in this article. Section 3 explains our CPR model and methods. Section 4 shows the analytical and numerical results. Finally, Section 5 draws some conclusions from the obtained results.

2 RelatedWork

Because of its importance for the understanding of the resource sustainability problem, several Game Theoretical models have been proposed for studying the CPR game [Sethi and Somanathan, 1996; Noailly et al., 2006; 2009]. This literature focuses on determining the Nash equilibria (hence no extensive dynamics) of those games and study how social norms such as costly punishment may enforce different equilibria. The CPR feature that resources change over time and are coupled with the strategy dynamics is often omitted in the literature [Biancardi, 2010] (see also a survey in [Van Den Bergh, 2007]). We show here that this aspect plays an influential role in the final outcome of the evolutionary dynamics. For instance, which consumption rate is selected by evolution and the social welfare of the population both correlate with the growth rate of the resource. The effect of heterogeneity has been shown to play an important role in several social dilemmas such as the public goods game [Santos et al., 2008] and the Prisoner's Dilemma [Nowak and Sigmund, 1992; Santos et al., 2006], but so far in CPR games, the study has been limited to homogeneous population structures like circles and grids [Noailly et al., 2006; 2009]. As a consequence, the current work provides a significant extension to the sparse literature on modeling the evolutionary dynamics of the strategies and resources in the CPR games.

In AI, computational sustainability has been given special attention in the last few years [Gomes, 2009]. The main concern therein is to develop techniques, such as those from machine learning and operational research, see e.g. [Weintraub et al., 2001; Ermon et al., 2010], for better decision making about management and allocation of resources. In addition, some formal frameworks have been provided to examine different (exogenous) principles for organizing and sustaining CPR [Pitt and Schaumeier, 2012; Pitt et al., 2012]. These works resort to the principles originally proposed in Ostrom's seminal work [Gardner et al., 1990; Ostrom, 2002], which are deemed the prerequisites for a stable arrangement of CPR. In contrast, similarly to other evolutionary models of CPR [Van Den Bergh, 2007], the results from the present study may provide important insights into the design of systems that can sustainably manage natural and technological resources [Gomes, 2009]. For instance, what is the optimal and evolutionarily stable harvesting strategies (represented by the parameter α in our model) given the resource growth rate, and more importantly, how agents can be distributed to enhance cooperation especially when in the absence of any enforcing mechanisms.

3 Model andMethods

3.1 Common-pool resource game

The CPR game is an N-player game in which N agents have to decide simultaneously how much to take from a shared resource P. As the resource P changes according to its own internal laws and the maximum P is limited by the environment, we model the resource dynamics by a population growth model, more specifically Ricker's model [Ricker, 1954].

where Pt corresponds to the amount of resource at a given point in time t, r is the growth rate and K is the carrying capacity of the resource, corresponding to the maximum size the resource can obtain given the constraints imposed by the environment. Without any consumption by the agents the resource evolves after a number of rounds towards its carrying capacity K at a speed depending on r. Beside the effects of

the growth dynamics on the resource, there are also agents consuming parts of this resource for their own profit. Since there are N agents simultaneously competing for the same resource, they each can maximally consume P/N of this resource (note that agents cannot take more than their share in the current definition). Clearly when every agent takes her part, the resource will be completely depleted and lost to future generations. To avoid this situation, each agent can decide to restrain herself and take only a fraction α of her part, defining the payoff for each agent as: πα = α Pt N .

In every round of the CPR game, each agent first consumes her part of Pt and then the resource regrows according to As the resource changes over time, the effective carrying capacity K∗ that one obtains in the limit of growing and consumption will differ from the original carrying capacity K. In Figure 2 one can observe (for varying growth rates r) how a particular consumption strategy affects K∗ when assuming groups of agents all using the same consumption strategy α. For r ≤ 1, the effective carrying capacity decreases first slowly and then quickly for increasing α. In addition, each r has an associated maximum consumption strategy α beyond which the resource becomes completely depleted in the limit. For r > 1 the consumption drives the resource to an effective carrying capacity that can exceed the original one, which is due to overshooting. Yet the overall effect of a decreasing K∗ for an increasing α remains the same.

Figure 2: Average amount of resources. For varying growth rates r we show here how consumption α affects the original carrying capacity K. The results were obtained through simulation using Z = 100, K = 100. Identical analytical results are obtained for Equation (3).

3.2 Effective carrying capacity

Equation (1) expresses how the resource changes at each round of the game when there is no consumption. Yet in the complete CPR game, agents can first take their part, thus reducing the current resource size Pt, before the calculation of Pt+1. This resource after consumption is now ˆ Pt = φPt, where (1 - φ) represents how much the different strategies in a groups of size N take from the resource in total. In case of a single agent type, α, in groups of size N, φ = (1 - α), whereas in case of two agent types, αA and αB, in groups of the same size with j αA agents

Introducing ˆ P and simplifying the equation, Equation (1) becomes:

The effective carrying capacity K∗ is obtained in the limit where Pt+1 = Pt. As such Equation (2) can be further be simplified to produce an equation expressing the size of the resource in the limit of coupled consumption and growth dynamics:

Using Equation (3) for varying r and α produces results identical to those shown in Figure 2.

3.3 Evolutionary dynamics in finite populations

Our analysis is based on EGT methods for finite populations [Nowak et al., 2004; Imhof et al., 2005]. In such a setting, the agents' overall consumption represents their fitness or social success, and evolutionary dynamics is shaped by social learning [Hofbauer and Sigmund, 1998; Sigmund, 2010], whereby the most successful agents will tend to be imitated more often by the others. In the current work, social learning is modeled using the so-called pairwise comparison rule [Traulsen et al., 2006], assuming that an agent A with fitness fA adopts the strategy of another agent B with fitness fB with probability given by the Fermi function,

where the parameter β represents the 'imitation strength' or 'intensity of selection', i.e., how strongly the agents base their decision to imitate on fitness comparison. For β = 0, we obtain the limit of neutral drift - the imitation decision is random. For large β, imitation becomes increasingly deterministic.

In the absence of mutations or exploration, the end states of evolution are inevitably monomorphic: once such a state is reached, it cannot be escaped through imitation. We thus further assume that, with a certain mutation probability, an agent switches randomly to a different strategy without imitating another agent. In the limit of small mutation rates, the behavioral dynamics can be conveniently described by a Markov Chain, where each state represents a monomorphic population, whereas the transition probabilities are given by the fixation probability of a single mutant [Fudenberg and Imhof, 2005; Imhof et al., 2005; Hauert et al., 2007]. The resulting Markov Chain has a stationary distribution, which characterizes the average time the population spends in each of these monomorphic end states.

Let Z be the size of a well-mixed population, where the fitness of the agents is determined by the outcome of the CPR game played in groups of N players. When assuming that there are at most two strategies in the population, say, k agents using strategy αA (0 ≤ k ≤ Z) and (Z -k) agents using strategies αB, the average fitness of each type can now be written as a hypergeometric sampling of the strategies from the population [Hauert et al., 2007]. It is a function of the number of αA agents (i.e. k) in the population. The average fitnesses for αA and αB agents are, respectively

where Παi represents the payoff an agent using strategy αi received in an interaction with the other agents in the group. This payoff function makes use of Equation (3) to determine howmuch each agent takes in the limit of the effective carrying capacity K∗ :

The probability to change the number k of agents using strategy αA by ±1 in each time step can be written as

The fixation probability of a single mutant with a strategy αA in a population of (Z - 1) agents using αB is given by [Traulsen et al., 2006; Fudenberg and Imhof, 2005]

In the limit of neutral selection (i.e. β = 0), ραB,αA equals the inverse of population size, 1/Z.

Considering a set {1, ..., q} of different strategies, these fixation probabilities determine a transition matrix M = {Tij}qi,j=1 , with Tij,j̸=i = ρji/(q - 1) and Tii = 1 - ∑qj=1,j̸=i Tij , of a Markov Chain. The normalized eigenvector associated with the eigenvalue 1 of the transposed of M provides the stationary distribution described above [Fudenberg and Imhof, 2005; Imhof et al., 2005], describing the relative time the population spends adopting each of the strategies.

3.4 Structured Population Simulations

To study the effect of assigning agents in a fair (i.e. uniform) or unfair manner to the resources, two graph models were used to organize resources and agents. In the fair assignment, each resource is used by the same number of agents and each agent is able to take from the same number of resources. A ring graph, where each node is associated with a resource and a player, satisfies this description. In the unfair case some agents have access to more resources than other agents, and moreover, some resources are shared among more agents than other resources. Such a scenario is best represented by a scale-free graph. The method for producing scale-free graphs is explained in [Barabasi et al., 1999]. Both the ring and scale-free graphs used in our simulations have an average degree of 4 and consist of 100 nodes.

On these topologies the evolutionary dynamics were simulated in the following manner; Given a graph (ring or scalefree), agents playing one of six strategies, corresponding to α ∈ {0.0, 0.2, 0.4, 0.6, 0.8, 1.0}. They are assigned to the nodes of the graph in a uniformly random manner. Each resource connected to a node is initialized to K. At every iteration of the game, each player participates with her neighbors in a CPR game, using the resource of the player in the central node (for details see [Santos et al., 2008]). Hence each player in the network participates in 5 games in the ring graph and on average 5 games in the scale-free graph, given that the (average) degree of both types of networks is 4. Once the game is played for one round, the resource K is updated (see Equation (1)) and the same steps are repeated for an additional V - 1 rounds (in all settings we used V = 50). These rounds allow the resource to converge to its effective carrying capacity K∗ , determined by the variation in strategies used by the different players, while the individuals are playing the CPR game. Hence greedy strategies will deplete the resource rather quickly, lowering their overall success over the different rounds, whereas more restrained strategies may accumulate more of the resource in the long term, potentially gaining a fitness advantage over the greedy strategies. After the V rounds, the individuals have the opportunity to either imitate one of their neighbors or mutates to a randomly selected alternative strategy. The decision to mutate or to imitate depends on a parameter μ; with probability μ the individual will mutate and with probability (1 - μ) she will imitate. Imitation is performed with a probability given by the Fermi function. Once the imitation phase is terminated the next iteration is started, resetting K to its original value. The process terminates after a predetermined number of rounds.

Ten different graphs are used for the scale-free simulations, which are not required for the ring graphs as they all have the same topology. Per graph we ran 10 simulations in the case if scale-free graphs and 100 simulations for the ring graph. Each simulation took 106 iterations and 2000 additional iterations were done to collect statistics: average population composition, and a player's average payoff and population average payoff. The probability of mutation is set to 10-4 , focussing hence on the small-mutation limit as in the mathematical model.

4 Results

4.1 Finite population dynamics of the CPR game

To start, we study a well-mixed population of diverse consumption strategies, ranging from the most restrained to the most greedy one. Namely, we consider a population of six strategies, C0 to C5, where Ci utilizes a consumption rate of α = 0.2 ∗ i. Figure 3A shows the transition probabilities and stationary distribution for the six strategies. Selection dynamic favors strategy C3 - which corresponds to an α = 0.6 - in the sense that the population spends most of its time in the homogeneous state of this strategy, regardless of the initial composition of the population. This preference for C3 is even more clear when examining Figure 3C. There the evolutionary dynamics are shown for a stronger intensity of selection (β = 0.1), which means that the actual payoff received by the agent plays a more important role in the imitation decision. When every agent in the population plays the strategy C3 the effective carrying capacity is K∗ ≈ 21 (see also Figure 2).

It can be seen that, among the six strategies being considered, C3 is the most greedy consumption strategy that still maintains a positive effective carrying capacity - which is crucial for the resistance against invasion of mutants and the stability of its homogenous population: If no resource would be left, then the success of this strategy would be equivalent to the success of the strategies C4 and C5, which could then invade by neutral drift. In addition, C2 would obtain in the limit a higher payoff, making it more advantageous than the C3. For the same reasons, the more greedy consumption strategies, C4 and C5, are not the winners selected by evolution. As such, one can see that without any additional mechanisms that make restrained consumption more interesting, evolutionary dynamics will lead to a selfish optimal outcome. This evolutionary dynamics differs from what is observed in the PG games, where without any supporting mechanism of cooperation (such as population structures, direct and indirect reciprocities, and costly punishment), the most defective strategy (corresponding here to C5) would be selected.

The results in Figure 3 also show the evolutionary dilemma in this game: C3 is not the most desirable state from the perspective of the population, which is to have the highest social welfare or average fitness. The average fitness of the homogenous population of C3 agents is less than that of the homogenous population of C2 agents, which at the same time sustains a higher effective carrying capacity K∗ ≈ 81. As such, from a collective perspective it is preferred to have agents playing C2, which makes it for this distribution of strategies the cooperative one.

A similar observation can be made in the Figure 3B, comparing also with Figure 2, where we show the fractions of the six strategies for different resource growth rates r. For increasing r, strategies with increasing consumption rates (i.e. more greedy) are dominant. Namely, C1 dominates for small r, then subsequently C2, C3 and C4, when r increases further. Moreover, as expected, for increasing r, the average carrying capacity of the six strategies (see the inset of Figure 3B) tends to increase, which is only due to the fast replenishment of the resource due to r.

In short, one important implication from this analysis, is that the definition of defective strategies or free-riders needs to be slightly revised here as it is not the most greedy strategy that corresponds to the selfish one. In the CPR game the defective or selfish strategy is greedy while being able to maintain a positive resource in the long run. This result provides the foundations for any new study into mechanisms that allow cooperation, or more restrained consumption, to evolve in the CPR game, which was moreover never discussed in earlier articles (see Section 2).

4.2 Uniform versus non-uniform resource assignment

A popular mechanism for the emergence of cooperation is the notion of network reciprocity, which is triggered by imposing a graph structure on the population of agents [Santos et al., 2006; 2008; 2011]. Each agent of the population becomes assigned to one of the nodes of the graph, which are connected in a specific manner. A well-mixed population, typically used in EGT, corresponds to a complete graph. Here we examine the evolutionary dynamics on two other graph types, i.e. ring and scale-free. Details on how the stochastic dynamics are simulated on the graphs are explained in Section 3.4.

Within this setting, the ring and scale-free population structures introduce two kinds of assignments of agents to resources (and resources to agents). The ring graph ensures that each resource is used by the same number of agents and that each agent can make use of the same number of resources. As such these configurations could be considered fair or uniform, since everyone could have the same benefits. The only difference will be in the initial distribution of the consumption strategies (Ci with i ∈ {0, 1, 2, 3, 4, 5}) over the nodes of the graph. In case of the scale-free population, some agents will be able to take from many resources, whereas other will be restricted to one or two. Moreover, some resources will have to be shared among many agents whereas most resources will be used by a few. As such, this situation is unfair or non-uniform as some may get more benefits because they can exploit more resources and others may receive larger portions of a resource as only a few are exploiting it.

The ring graph comes closest to the mathematical model discussed earlier. Hence the expectation is that a similar outcome, where C3 is the dominant strategy, should be observed. Looking at Figure 4, one can observe clearly that this assumption is correct. In 92% of the simulations, the population evolves to a monomorphic state containing only C3 players. Once in a while the population evolves towards a monomorphic state containing only C5 players. This difference with the mathematical model is simply due to stochastic effects; Here each agent plays only in a small number of groups to determine its reproductive success. In the mathematical model, the fitness of each type of players is determined over all potential groups that could be extracted from the well-mixed population. Additionally, the outcomes of the simulations are dependant on the initial distribution of the agents on the network. Nevertheless, one can see that the average fitness of C3 players is higher than C5 players, making the former effectively advantageous over the latter.

In case of the scale-free graph, where resources and agents are not distributed fairly, a different outcome emerges: The systems produces a polymorphic population in which the more fair consumption strategies tend to dominate. Additionally, the balance is tipped most frequently towards the strategy C2. This result is represented in the second circle shown in Figure 4; The fraction of C2 players over all runs is higher than most other strategies. Interestingly, certain runs even end up in the C1 dominated population, which represents an even more restrained population. Note also that on average the fitness of the C2 type is clearly higher than all other types, making them selectively advantageous. Longer iterations (> 106 ) may support further the dominance of C2 players. Together these simulations on ring and scale-free graphs produce an important result; differences in resource organization result in differences in player welfare and resource sustainability. Interestingly, it is not the fair allocation that generates the most beneficial outcome.

5 Conclusions

Resorting to the tools of EGT, we have described here the detailed evolutionary dynamics of different consumption strategies in the CPR game, including an explicit modeling of the resource dynamics. We have shown that in this setting, the most greedy possible strategy that can maintain a positive resource in the long run is selected. These results, on the one hand, identify an interesting difference between CPR and PG games, in which the most defective or greedy strategy always prevails. On the other hand, they provide the foundations for further explorations into mechanisms that direct the result to a more social outcome and a more sustainable consumption of resources.

As a first step in that direction, we have studied here, using simulations, the effects of different population structures on the viability of different consumption strategies in the population as well as on the average fitness of the population, which is directly linked to the effective average carrying capacity of the resources. Interestingly, we have shown that, when resources and agents are distributed in a heterogenous graph, so that agents have unequal access to the resources (and vice versa), a more restrained consumption may evolve and a higher social welfare can be achieved. Considering the assignment of resource to agents (and agents to resources) in the scale-free scenario, those results may be due to the fact that most resources are only used by a few agents and that most agents only exploit a few resources.

A more in depth analysis is under way to verify this hypothesis, including an investigation in the effect of differing resource sizes. Nevertheless this result may provide some useful insights for the design of sustainable distributed resource systems such as Smart Grids [Gomes, 2009].