Evolutionary dynamics of social dilemmas in structured heterogeneous populations

F. C. Santos; J. M. Pacheco; Tom Lenaerts

doi:10.1073/pnas.0508201103

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 single-scale graphs, for which heterogeneity is small and associated degree distributions exhibit a Gaussian tale, to scale-free graphs, for which heterogeneity is large with degree distributions exhibiting a power-law 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 long-term cooperative behavior easily resists short-term noncooperative behavior. Moreover, we show how cooperation depends on the intricate ties between individuals in scale-free populations.

Footnotes

^§To whom correspondence should be sent at the ∗ address. E-mail: 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 “broad-scale.” The associated degree distribution of broad-scale NoC exhibits a region of scale-free behavior truncated by a fast-decaying 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 single-scale and scale-free graphs. Our results (data not shown) for uncorrelated broad-scale 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 edges-to-be. 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 ₀) of vertices, at every time step we add a new vertex with m ≤ m ₀ 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:
Abbreviation:
NoC,
network of contacts.
© 2006 by The National Academy of Sciences of the USA