New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
Evolutionary dynamics of social dilemmas in structured heterogeneous populations

Edited by Brian Skyrms, University of California, Irvine, CA, and approved December 15, 2005 (received for review September 21, 2005)
Abstract
Real populations have been shown to be heterogeneous, in which some individuals have many more contacts than others. This fact contrasts with the traditional homogeneous setting used in studies of evolutionary game dynamics. We incorporate heterogeneity in the population by studying games on graphs, in which the variability in connectivity ranges from singlescale graphs, for which heterogeneity is small and associated degree distributions exhibit a Gaussian tale, to scalefree graphs, for which heterogeneity is large with degree distributions exhibiting a powerlaw behavior. We study the evolution of cooperation, modeled in terms of the most popular dilemmas of cooperation. We show that, for all dilemmas, increasing heterogeneity favors the emergence of cooperation, such that longterm cooperative behavior easily resists shortterm noncooperative behavior. Moreover, we show how cooperation depends on the intricate ties between individuals in scalefree populations.
Cooperation has played a key role throughout evolution (1). Selfreplicating cells have cooperated to form multicellular organisms throughout evolutionary history (2, 3). Similarly, we know that animals cooperate in families to raise their offspring and in groups to prey and to reduce the risk of predation (4, 5). Cooperation has been conveniently formulated in the framework of evolutionary game theory, which, when combined with games such as the Prisoner’s Dilemma, which is used as a metaphor for studying cooperation between unrelated individuals, enables one to investigate how collective cooperative behavior may survive in a world where individual selfish actions produce better shortterm results. Analytical solutions for this problem have been obtained when populations are assumed infinite and their interactions are assumed homogeneous such that all individuals are in equivalent positions. Under such assumptions, noncooperative behavior prevails. Such an unfavorable scenario for cooperation in the Prisoner’s Dilemma game, together with the difficulty in ranking the actual payoffs in field and experimental work (6, 7), has lead to the adoption of other games (8, 9), such as the Snowdrift game (also known as Hawk–Dove or Chicken), which is more favorable to cooperation, and the StagHunt game (10), and to numerical studies of cooperation in finite, spatially structured populations (11) in which homogeneity is still retained. Such studies of the role of structured populations have attracted considerable attention, originating from fields ranging from sociology to biology, ecology, economics, mathematics, and physics, to name a few (11–19). More recently, however, compelling evidence has been accumulated that a plethora of biological, social, and technological realworld networks of contacts (NoC) are mostly heterogeneous (20–22). Indeed, analysis of realworld NoC (20) has provided evidence for the following (heterogeneous) types: (i) singlescale networks, which are characterized by degree distributions (defined in the Methods) that exhibit a fast, typically Gaussian, decaying tail; (ii) broadscale networks, which are characterized by a powerlaw regime truncated for large connectivities by a fastdecaying tail; and (iii) scalefree networks, which are characterized by a distribution that decays as a powerlaw. In Fig. 1, we show the distribution of connectivities associated with both singlescale and scalefree NoC, on which the results shown in Figs. 2 and 3 were based. To better illustrate the degree of heterogeneity associated with each NoC, we show a double logarithmic plot of the cumulative degree distribution, defined in Fig. 1. Clearly heterogeneity greatly increases as one moves all of the way from single scale to extreme heterogeneous, scalefree NoC. In particular, the broadscale NoC also identified in ref. 20 exhibit tails that fall off somewhere between the extreme limits depicted in Fig. 1. All of these different levels of heterogeneity stand in sharp contrast with homogeneous NoC.
What is the impact of moving from a homogeneously structured population, in which everyone has the same amount of interactions, to a heterogeneously structured population, in which some can interact more than others? In particular, what is the impact of more realistic NoC in the evolution of cooperation?
Here we address this problem by examining the emergence of cooperation in terms of the three popular and extensively studied dilemmas of cooperation referred to above. It will be shown that increasing heterogeneity generally favors the emergence of cooperation, irrespective of the dilemma under investigation.
Games and Social Dilemmas
We shall model interactions among individuals in terms of twoperson games in which both players can either cooperate or defect when interacting with each other. Mutual cooperation leads to the reward, R (without loss of generality, we make R = 1), whereas mutual defection leads to the punishment, P (we make P = 0, thereby normalizing the advantage of mutual cooperation over mutual defection to 1 in all games). The other two possibilities occur when one player cooperates and the other defects, for which the associated game payoffs are S (sucker’s payoff) and T (temptation) for the cooperator and the defector, respectively. Provided that mutual cooperation is always preferred over mutual defection, the three dilemmas arise naturally (16), depending on the relative ordering of these four payoffs: The Snowdrift game, for which T > 1 > S > 0; the StagHunt game, for which 1 > T > 0 > S; and the Prisoner’s Dilemma game, for which T > 1 > 0 > S. For all dilemmas, mutual cooperation is also preferred over unilateral cooperation (S) and over an equal probability of unilateral cooperation and defection (2 > T + S). Tension becomes apparent when the preferred choices of each player lead to individual actions resulting in mutual defection, despite the fact that mutual cooperation is more beneficial. Indeed, tension will arise when players prefer unilateral defection to mutual cooperation (T > 1), when players prefer mutual defection to unilateral cooperation (S < 0), or when both situations arise, which is precisely what happens in the Snowdrift game, the StagHunt game and the Prisoner’s Dilemma game, respectively. Formally, these dilemmas span a fourdimensional parameter space. By normalizing mutual cooperation to 1 and mutual defection to 0, we are left with two parameters, T and S. We study the behavior of all dilemmas, summarized in Table 1, in the ranges 0 ≤ T ≤ 2 and −1 ≤ S ≤ 1, which will be shown to be sufficient to characterize the games under study.
Role of Heterogeneity in the Evolution of Cooperation
Let us consider heterogeneous NoC. Different individuals in the population may engage in different number of rounds per generation because of the number of different ties that each entails. Moreover, the pattern of connectivity may also be different for different individuals: For example, one individual may be connected to few immediate neighbors, whereas another individual may have many connections, some of which may constitute direct links to faraway individuals.
As an illustration, consider two focal individuals, a cooperator with N _{1} neighbors, and a defector with N _{2} neighbors, and let us imagine that both have the same number of defectors, say N _{D}. After interacting with all their neighbors, the cooperator accumulates a payoff of P _{C} = N _{1} +(S − 1)N _{D}, whereas the defector ends up with P _{D} = (N _{2} − N _{D})T. If the NoC were homogeneous, all one needs to do is to make N _{1} = N _{2} = z, the average connectivity of the population, in the previous expressions. This calculation, however, leads to very different outcomes in what concerns the accumulated payoffs in homogeneous and heterogeneous NoC. Indeed, whereas, in homogenous NoC, the answer to whether P _{D} > P _{C} relies exclusively on the relative ordering of the payoffs (T, R, P, S); in heterogeneous NoC the answer depends now on the fact that N _{1} ≠ N _{2}. In other words, the pattern of connectivity also contributes to define the accumulated payoff of each individual, a feature that, being natural, is absent in homogeneous NoC. Indeed, heterogeneity embeds the intuition that different individuals engage in different numbers of interactions with different intensities, which opens a new route to the evolution of cooperation: Cooperators will increase their fitness to the extent they succeed in maximizing their amount of cooperative interactions per generation. However, defectors may also increase their fitness by exploiting more cooperators per generation. Results presented as supporting information, which is published on the PNAS web site, show that cooperators are able to profit from heterogeneity to outperform defectors.
Results and Discussion
Well Mixed Populations.
Before addressing heterogeneous, structured populations (results for homogeneous structured populations are provided in the supporting information), we examine the effect of the dynamics on the finite population analog to the infinite well mixed limit, which is well known from the standard analytical treatment (23): a complete, fully connected graph. Evolution is implemented via the stochastic dynamics described in Methods. As usual in evolutionary biology, the fitness of each individual is associated with the accumulated payoff at the end of a life cycle. The results are shown in Fig. 2 Left, in which the StagHunt, Snowdrift, and Prisoner’s Dilemma games span the three domains that fill the lowerleft, upperright, and lowerright squares of the contour plot, respectively. Note further that in the Snowdrift domain, only the lower triangle of the domain strictly satisfies the requirement 2 > T + S.
The results obtained here for a well mixed population of N = 10^{4} individuals retain all of the features familiar from the analytical results for infinite well mixed populations: the (i) dramatic fate of cooperators in the Prisoner’s Dilemma domain, (ii) a similar fate for cooperators in the StagHunt domain when the disadvantage of being defected exceeds the temptation to defect, and (iii) the coexistence of cooperators and defectors in the Snowdrift domain when only the temptation to defect undermines mutual cooperation.
Heterogeneous Populations.
Let us examine now the evolutionary dynamics in structured heterogeneous populations. We start with the singlescale type of populations identified in ref. 20, in which heterogeneity is small (Fig. 1), exhibiting a Gaussian tail for the degree distribution. Finite populations exhibiting such features were generated by using the configuration model (24), which leads to random graphs compatible with a given degree distribution (additional details are provided in Methods). The corresponding results are shown in Fig. 2 Right. Taking the results for well mixed populations as a reference, it is clear that cooperation is enhanced for all dilemmas. Specifically, cooperators now resist invasion by defectors in the Prisoner’s Dilemma domain. Moreover, only for larger intensities of the temptation to defect will cooperators be outweighed by defectors in the Snowdrift domain. Finally, for the StagHunt domain, cooperators are now able to resist defectors even when the disadvantage of being defected exceeds the temptation to defect.
The net results shown in Fig. 2 Right and Fig. 3 hide a detailed interplay of two mechanisms related to the smallworld and heterogeneous nature of the underlying scalefree NoC: the occurrence of many longrange connections (socalled shortcuts) in these graphs precludes the formation of compact clusters of cooperators, thereby facilitating invasion by defectors when S < 0. However, the increase in heterogeneity of the NoC opens a new route for cooperation to emerge, because, now, different individuals interact different number of times per generation, which enables cooperators to outperform defectors. In other words, whereas the increased difficulty in aggregating clusters of cooperators would partially hamper cooperation (see the supporting information), heterogeneity counteracts this effect with a net increase of cooperation. Indeed, the results discussed below for scalefree NoC show how cooperation is sensitive to the overall degree of heterogeneity of the underlying NoC, leading to an increase of cooperation as one evolves from homogeneous populations (Fig. 2 Left) to extreme heterogeneous populations (Fig. 3).
The effects of heterogeneity become indeed more prominent when we consider scalefree NoC. ^{¶} The results for the evolution of cooperation in populations exhibiting a scalefree degree distribution such that all connections between individuals are purely random are shown in Fig. 3 Left. Notice that, despite the abundance of scalefree behavior identified in real NoC, the detailed cartographic representation of the ties between individuals remains to a large extent unknown (25). In this sense, random scalefree populations, generated in the way described in Methods provide a general biasfree scenario. The results in Fig. 3 Left provide further evidence of the determinant role played by such heterogeneous population structures on the evolution of cooperation for all dilemmas. Maintaining Fig. 2 Left as a reference, we observe that, over all, scalefree NoC efficiently neutralize the detrimental role of the temptation to defect (when T > 1) in the evolution of cooperation, whereas the disadvantage of being defected (when S < 0) remains a strong deterrent of cooperation. Indeed, in the Snowdrift domain, cooperators dominate for all values of T > 1. In the StagHunt domain, cooperators now survive even when S < T − 1. For the Prisoner’s Dilemma domain, the region of coexistence between cooperators and defectors is clearly broadened. Moreover, the small slope of the borderline between cooperators and defectors provides further evidence that the disadvantage of being defected (S < 0) constitutes the major threat to cooperation.
The sustainability of cooperation, however, is not affected solely by the overall heterogeneity of the NoC associated with a given degree distribution. In fact, cooperation is particularly susceptible to the detailed and intricate ties between individuals in a population. Indeed, if we do not randomize the pattern of connectivity between individuals such that the NoC exhibit the correlations arising naturally in the Barabási and Albert (21) model, a different result emerges for the evolution of cooperation, as shown in Fig. 3 Right. Under the presence of such correlations, the temptation to defect no longer poses any threat to cooperation, defectors being wiped out from populations in the entire Snowdrift domain. In the StagHunt domain, cooperators now wipe out defectors, where, before (Fig. 3 Left), they managed to coexist. In the Prisoner’s Dilemma domain, cooperators also get a strong foothold up to larger intensities of S.
As is well known, the Barabási and Albert (21) model exhibits socalled age correlations in which the older vertices not only acquire the highest connectivity but also become naturally interconnected with each other. These correlations result from the combined mechanisms of growth and preferential attachment, which lie at the heart of the model (21). As a result, the formation of compact clusters of cooperators, which was inhibited by the occurrence of many shortcuts in random scalefree NoC, will be partly regained in such NoC, mostly for the few individuals that exhibit high connectivity. Of course, such a clustering of cooperators will occur only to the extent that cooperators are able to occupy such highly connected sites, which indeed happens. The results shown in Fig. 3 have the additional feature that the degree distributions of the NoC used in studying the evolution of cooperation actually coincide, the difference between the two NoC residing solely in the detailed pattern of ties between individuals. Finally, we would like to point out that all our results remain unchanged both for larger (we have checked up to N = 10^{5}) and smaller population sizes, down to values of N ≈ 10^{2} individuals. For such small population sizes, stochastic effects resulting from both the graph generation procedures and the evolutionary dynamics preclude a clearcut result for the evolution of cooperation.
Conclusions
The present results demonstrate that, in more realistic, heterogeneous populations, the sustainability of cooperation is simpler to achieve than in homogeneous populations, a result that is valid irrespective of the dilemma adopted as a metaphor of cooperation. The results shown in Fig. 2 Right show that heterogeneity constitutes a powerful mechanism for the emergence of cooperation, because, even for mildly heterogeneous populations, heterogeneity leads to sizeable effects in the evolution of cooperation. The results also show that the disadvantage of being defected (S < 0) constitutes a stronger deterrent of cooperation than the temptation to defect (T > 1), a feature found before for the Prisoner’s Dilemma in the context of homogeneous, infinite populations (26).
The overall enhancement of cooperation obtained on singlescale and scalefree graphs may be understood as resulting from the interplay of two mechanisms: (i) the existence of many longrange connections in random and smallworld NoC, which precludes the formation of compact clusters of cooperators (this effect acts to inhibit cooperation when S < 0) and (ii) the heterogeneity exhibited by these NoC, which opens a new route for cooperation to emerge and contributes to enhance cooperation (which increases with heterogeneity), counteracting the previous effect. The net result is that cooperation is enhanced, as shown in Figs. 2 Right and 3.
Finally, the sustainability of cooperation depends also on the intricate ties between individuals, even for the same class of graphs, features not accounted for by meanfield or pair approximations.
In this context, it is noteworthy that the present model assumes a given population structure that remains immutable throughout evolution. A more realistic model, however, should take into account that individuals have the capacity to establish new links as well as to severe others throughout evolution, leading to an adaptive coevolution of strategy and structure. It remains an open problem the extent to which such a possibility will naturally lead to the scalefree populations studied here.
Methods
Homogeneous and Heterogeneous Graphs.
In the language of graph theory, well mixed populations of size N are represented by complete graphs, which correspond to a regular, homogeneous graph with average connectivity z = N − 1, because all vertices share the same number of connections and are topologically equivalent. Indeed, all homogeneous graphs exhibit the same singlepeak shape for the degree distribution d(k), defined for a graph with N vertices as d(k) = N _{k}/N, where N _{k} gives the number of vertices with k edges. In Fig. 1, we show the cumulative degree distribution associated with the heterogeneous types of NoC explicitly considered in this work [the cumulative degree distribution D(k) is defined in Fig. 1]. Realworld NoC are clearly heterogeneous, corresponding to populations in which different individuals exhibit distinct patterns of connectivity, portraying the coexistence of local connections (spatial structure) with nonlocal connections (or shortcuts) and often exhibiting regions with a powerlaw dependence of their degree distributions (20–22). When heterogeneity is moderate, such that the connectivities of most individuals do not deviate significantly from the average connectivity value, the pattern of connectivity has been classified as “singlescale,” as in ref. 20, where it was found that such NoC typically exhibit a Gaussian tail. Those NoC exhibit cumulative degree distributions such as that illustrated in Fig. 1 with a dashed line. The results in Fig. 2 Right correspond to populations modeled in terms of such NoC, making use of the configuration model (24), which provides a maximally random graph compatible with such a degree distribution. ^{∥} Scalefree graphs, in contrast, constitute examples of strongly heterogeneous NoC. The Barabási–Albert model (21) provides the best known model leading to overall scalefree degree distributions, d(k) ≈ k ^{−γ}, with γ = 3, and cumulative degree distributions scaling as ≈k ^{−(γ − 1)}, as shown in Fig. 1 with a solid line. The scalefree features of the Barabási–Albert model result from the combined effect of the two processes of growth** and preferential attachment, ^{††} the latter corresponding to the well known “rich get richer” effect in economics (27), which is also known as the Matthew effect in sociology (28). After t time steps, this algorithm produces a graph with n = t + m _{0} vertices and mt edges. Because vertices appear at different moments in graphgeneration time, socalled age correlations (21) arise. Such agecorrelated NoC with n = 10^{4} vertices and average connectivity z = 4 are on the basis of the results shown in Fig. 3 Right.
The role of heterogeneity in evolution may be singled out by removing any correlations (including age correlations) in a graph, which is easily accomplished by randomly and repeatedly exchanging the ends of pairs of edges of the original graph (29), a procedure that washes out correlations without changing the degree distribution (29) of the graphs. The results shown in Fig. 3 Left were obtained on Barabási–Albert scalefree NoC subsequently randomized in this way.
Evolutionary Games on Graphs.
For R = 1, P = 0, 0 ≤ T ≤ 2 and −1 ≤ S ≤ 1, evolution is carried out by implementing the finite population analog of replicator dynamics (18, 30), to which simulation results converge in the limit of infinite, complete graphs (well mixed populations). These dynamics are obtained by defining the following transition probabilities: In each life cycle (one generation), all pairs of directly connected individuals x and y engage in a single round of the game, their accumulated payoff being stored as P _{x} and P _{y}, respectively. At the end of the generation, all strategies are updated simultaneously (synchronous updating). When a site x is updated, a neighbor y is drawn at random among all k _{x} neighbors; then, only if P _{y} > P _{x} the strategy of chosen neighbor y replaces that of x with probability given by (P _{y} − P _{x})/[k _{>} D _{>}], where k _{>} = max(k _{x},k _{y}) and D _{>} = max(T,1) − min(S,0). This denominator ensures a proper normalization of the transition probability. ^{‡‡} The results obtained are robust and therefore insensitive to replacement of the previous expression by a transition probability function W(P _{y} − P _{x}), being zero when P _{y} ≤ P _{x} and increasing monotonously to 1 when P _{y} > P _{x}. We have also confirmed that replacing synchronous updating by asynchronous updating does not bring any qualitative modifications to the results presented here.
Simulations.
Simulations were carried out on graphs with N = 10^{4} vertices and average connectivity z = 4 (except in Fig. 2 Left, where z = N − 1). Equilibrium frequencies of cooperators and defectors were obtained for each value of T and S by averaging over 1,000 generations after a transient time of 10,000 generations (we confirmed that averaging over larger periods or using different transient times did not change the results). Furthermore, final data results from averaging over 100 simulations, corresponding to 10 runs for each of 10 different realizations of a given type of NoC specified by the appropriate parameters (N and z). All simulations start with an equal percentage of strategies (cooperators and defectors) randomly distributed among the elements of the population. In this way, all vertices are initially populated with a strategy, and no initial advantage is given to cooperators or to defectors. Finally, even when graphs are generated stochastically, as is the case for the Barabási–Albert NoC, the evolution of cooperation is studied in fullgrown graphs; that is, the topology of the graph remains frozen throughout evolution.
Acknowledgments
We thank two anonymous reviewers whose constructive comments helped us improve our manuscript. F.C.S. acknowledges support from COMP^{2}SYS, a Marie Curie Early Stage Training Site funded by the European Commission through the Marie Curie Human Resources and Mobility Activity program.
Footnotes
 ^{§}To whom correspondence should be sent at the ∗ address. Email: tlenaert{at}ulb.ac.be

Author contributions: F.C.S., J.M.P., and T.L. designed research; F.C.S., J.M.P., and T.L. performed research; and F.C.S., J.M.P., and T.L. wrote the paper.

Conflict of interest statement: No conflicts declared.

This paper was submitted directly (Track II) to the PNAS office.

↵ ¶ In ref. 20, a third class of NoC was identified and described as “broadscale.” The associated degree distribution of broadscale NoC exhibits a region of scalefree behavior truncated by a fastdecaying tail for large values of the connectivity, which leads naturally to intermediate levels of heterogeneity as compared with those discussed in this work. In view of the results obtained here, one expects to obtain levels of cooperation intermediate from those associated with singlescale and scalefree graphs. Our results (data not shown) for uncorrelated broadscale NoC entirely corroborate this picture.

↵ ∥ To generate a graph with the configuration model, one assigns to each vertex a number of “stubs” that constitute the tips of edgestobe. The number of stubs must, of course, conform with the given degree distribution. Subsequently, one chooses, at random, pairs of stubs and joins them together, in this way generating the edges of the corresponding graph.

↵ ** Starting with a small number (m _{0}) of vertices, at every time step we add a new vertex with m ≤ m _{0} edges that link the new vertex to m different vertices already present in the system.

↵ †† When choosing the vertices to which the new vertex connects, we assume that the probability, p _{i}, that a new vertex will be connected to vertex i depends on the degree k _{i} of vertex i: p _{i} = k _{i}/Σk _{i}.

↵ ‡‡ It is noteworthy that the present stochastic dynamics relies entirely on local information pertaining to each pair of individuals involved. Furthermore, the update rule is invariant under translation and rescaling of the payoff matrix, the dynamics converging to the well known replicator dynamics in the limit of complete, infinite graphs. Such an update rule typically models cultural evolution, in which individuals tend to imitate the strategies of those performing better.
 Abbreviations:
 NoC,
 network of contacts.
Abbreviation:
 © 2006 by The National Academy of Sciences of the USA
References

↵
 Sigmund K.

↵
 MaynardSmith J. ,
 Szathmáry E.

↵
 Michod R. E.
 ↵

↵
 Hamilton W. D.
 Fox R.

↵
 Milinski H. ,
 Lüthi J. H. ,
 Eggler R. ,
 Parker G. A.
 ↵

↵
 Heinsohn R. ,
 Parker C.

↵
 CluttonBrock T.

↵
 Skyrms B.
 ↵

↵
 Skyrms B. ,
 Pemantle R.
 ↵
 ↵

↵
 Axelrod R. ,
 Riolo R. L. ,
 Cohen M. D.

↵
 Macy M. W. ,
 Flache A.
 ↵
 ↵
 ↵

↵
 Amaral L. A. N. ,
 Scala A. ,
 Barthelemy M. ,
 Stanley H. E.
 ↵

↵
 Dorogotsev S. N. ,
 Mendes J. F. F.

↵
 Weibull J. W.

↵
 Molloy M. ,
 Reed B.
 ↵

↵
 Rapoport A. ,
 Chamah A. M.

↵
 Simon H.

↵
 Merton R. K.

↵
 Maslov S. ,
 Sneppen K.

↵
 Gintis H.