Dynamical Organization of Cooperation in Complex TopologiesJ. Go´mez-Garden˜es, 1,2 M. Campillo, 2 L.M. Flor? ´a, 1,2 and Y. Moreno 1, *1 Institute for Biocomputation and Physics of Complex Systems (BIFI), University of Zaragoza, Zaragoza 50009, Spain2 Departamento de F? ´sica de la Materia Condensada, University of Zaragoza, Zaragoza E-50009, Spain(Received 12 December 2006; published 7 March 2007)In this Letter, we study how cooperation is organized in complex topologies by analyzing theevolutionary (replicator) dynamics of the prisoner’s dilemma, a two-player game with two availablestrategies, defection and cooperation, whose payoff matrix favors defection. We show that, asymptotically,the population is partitioned into three subsets: individuals that always cooperate (pure cooperators),always defect (pure defectors), and those that intermittently change their strategy. In fact, the size of thelater set is the biggest for a wide range of the ‘‘stimulus to defect’’ parameter. While in homogeneousrandom graphs pure cooperators are grouped into several clusters, in heterogeneous scale-free (SF)networks they always form a single cluster containing the most connected individuals (hubs). Our resultsgive further insights into why cooperation in SF networks is enhanced.DOI: 10.1103/PhysRevLett.98.108103 PACS numbers: 87.23.Kg, 02.50.Le, 89.75.FbTo understand the observed survival of cooperationamong unrelated individuals in social communities whenself i sh actions provide a higher benef i t, a lot of attention isbeing paid to the analysis of evolutionary dynamics ofsimple two-players games like the prisoner’s dilemma(PD). In this game individuals adopt one of the two avail-able strategies, cooperation or defection; both receive Runder mutual cooperation and P under mutual defection,while a cooperator receives S when confronted to a defec-tor,which in turnreceivesT,where T > R > P > S.Underthese conditions it is better to defect, regardless of theopponent strategy, and assuming that strategies are allowedto spread within the population according to their payoffs(replicator dynamics [1,2]), the proportion of cooperatorsasymptotically vanishes in a well-mixed population (i.e.,when each agent interacts with all other agents).If the well-mixed population hypothesis is abandoned,so that individuals only interact with their neighbors in asocial network, several studies [3–9] have reported theasymptotic survival of cooperation on different types ofnetworks. Notably, cooperation even dominates over de-fection in heterogeneous, scale-free (SF) networks wherethe distribution density of local connectivities follows apower law. In view of the accumulated evidence [10,11]that many social (as well as technological, biological, andother) networks are highly heterogeneous, these results arehighly relevant for the understanding of the evolution ofcooperation.In this Letter, we are interested in exploring the roots ofthe diverse behavior observed on top of different complextopologies and in providing an explanation in terms ofmicroscopic arguments. We have analyzed in detail themicroscopic structural aspects underlying the differencesin the evolution of cooperation in a one-parameter familyof networks interpolating between Baraba´si-Albert (BA)[12] and Erdo¨s-Re ´nyi (ER) graphs. As usual in recentstudies [3,4], we choose the prisoner’s dilemma payoffsas R ? 1, P ? S ? 0, and T ? b > 1, and implement thef i nite population analogue of replicator dynamics [4]. Ateach time step t, which represents one generation of thediscrete evolutionary time, each node i in the networkplays with all its neighbors and accumulates the obtainedpayoffs, P i . Then, the individuals, i, update synchronouslytheir strategies by picking up at random a neighbor, j, andcomparing their respective payoffs P i and P j . If P i > P j ,nothing happens and i keeps the same strategy for the nextgeneration. On the contrary, if P j > P i , with probability? i!j ? ?P j ? P i ?=maxfk i ;k j gb, i adopts the strategy of jfor the next round robin with its neighbors [4].We have performed simulations for a population of Nindividuals that interact following the couplings dictatedby the underlying graph. To explore the structure anddynamics of cooperative behavior in different topologies,we have made use of the model developed in [13], whichallows to smoothly pass from a BA network to a randomgraph of the sort of ER networks by tuning a singleparameter ? 2 ?0;1?. We will restrict hereafter to thesetwo limiting cases (ER, ? ? 1, and BA, ? ? 0). Theresults obtained for other values of ? will be discussedelsewhere [14]. We advance that they are consistent withthe picture described in what follows.The dynamics is implemented once the network isgrown. At the beginning, each individual of the populationhas the same probability of adopting either of the twoavailable strategies: cooperation (s i ? 1) or defection(s i ? 0). We let the system evolve for 5000 generationsand check whether or not the system has reached a sta-tionary state as given by the fraction, c?t?, of individualsthat are cooperators. We impose that this magnitude is inequilibrium when, taken over a time window of 10 3 addi-tional generations, the slope of c?t? is smaller than 10 ?2[15]. After such a def i ned transient time t 0 , we let thesystem evolve again for 10 4 additional time steps, andmeasure the magnitudes whose behavior is described inPRL 98, 108103 (2007)PHYSICAL REVIEW LETTERSweek ending9 MARCH 20070031-9007=07=98(10)=108103(4) 108103-1 © 2007 The American Physical Society
