PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of plosonePLoS OneView this ArticleSubmit to PLoSGet E-mail AlertsContact UsPublic Library of Science (PLoS)
 
PLoS One. 2010; 5(6): e11187.
Published online 2010 June 30. doi:  10.1371/journal.pone.0011187
PMCID: PMC2894855

Evolution of Cooperation on Stochastic Dynamical Networks

Olaf Sporns, Editor

Abstract

Cooperative behavior that increases the fitness of others at a cost to oneself can be promoted by natural selection only in the presence of an additional mechanism. One such mechanism is based on population structure, which can lead to clustering of cooperating agents. Recently, the focus has turned to complex dynamical population structures such as social networks, where the nodes represent individuals and links represent social relationships. We investigate how the dynamics of a social network can change the level of cooperation in the network. Individuals either update their strategies by imitating their partners or adjust their social ties. For the dynamics of the network structure, a random link is selected and breaks with a probability determined by the adjacent individuals. Once it is broken, a new one is established. This linking dynamics can be conveniently characterized by a Markov chain in the configuration space of an ever-changing network of interacting agents. Our model can be analytically solved provided the dynamics of links proceeds much faster than the dynamics of strategies. This leads to a simple rule for the evolution of cooperation: The more fragile links between cooperating players and non-cooperating players are (or the more robust links between cooperators are), the more likely cooperation prevails. Our approach may pave the way for analytically investigating coevolution of strategy and structure.

Introduction

Cooperation is ubiquitous in the real world ranging from genes to multicellular organisms [1][4]. Most importantly, human society is based upon cooperation. However this cooperative behavior apparently contradicts natural selection [5]: Selfish behavior will be rewarded during competition between individuals, because selfish individuals enjoy the benefits from the cooperation of others, but avoid the associated costs. Therefore, the puzzle how natural selection can lead to cooperation has fascinated evolutionary biologists since Darwin.

Evolutionary game theory is an intuitive and convenient framework to study this puzzle. As a metaphor, the Prisoner's Dilemma (PD) has been widely used to investigate the origin of cooperation. In this game, two players simultaneously decide whether to cooperate (An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e001.jpg) or to defect (An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e002.jpg). They both receive An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e003.jpg upon mutual cooperation and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e004.jpg upon mutual defection. A defector exploiting a cooperator receives An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e005.jpg, and the exploited cooperator gets An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e006.jpg. This can be formalized in the form of a payoff matrix,

equation image
(1)

The PD is characterized by the payoff ranking An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e008.jpg. For repeated games, the additional requirement An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e009.jpg ensures that alternating between strategies is less lucrative than repeated mutual cooperation. In the one shot PD, it is best for a rational individual never to cooperate irrespective of the co-player's decision. Thus, defection is the Nash Equilibrium [6]. However, the two players would be better off if they both cooperated, hence the dilemma. In an evolutionary setting, where payoff determines reproductive fitness, defectors can reproduce faster based on their higher payoff and cooperation diminishes - defection is evolutionary stable [7], [8]. Several mechanisms have been proposed to explain the persistence of cooperative behavior, including kin selection [9], direct [10], [11] and indirect reciprocity [12], [13], group selection [14], [15] as well as the network reciprocity [16]–. Furthermore, the relationship between these mechanisms receives an increasing attention [25][28].

Both in animal and human societies, individuals interact with a limited number of individuals. The interactions of individuals are often captured based on the network of contacts. Therefore, there has been an increasing interest in the influence of population structure on the evolution of cooperation.

Nowak and May first studied the PD game on regular lattices [16]. Subsequently, social dilemmas on regular graphs have been investigated [19][21], [29]. Many authors have also considered more complex networks, such as scale-free and small-world afterwards [17], [18], [24]. It has been well recognized that network topologies can play a crucial role in the evolution of cooperation, in addition to the payoff matrix and the update mechanism.

The network topology is assumed to be static in the above work. However, social relationships between individuals are not eternal, but are continuously changing in the real world. Therefore, the coevolution of strategy and network receives increasing attention [30][47].

Dynamical networks can significantly boost cooperation compared to static networks. On the one hand, cooperation thrives if individuals are able to promptly adjust their social ties, because this allows cooperators to escape from defectors [38]. Similarly, cooperation is more likely to occur if the favored relationships between cooperators (An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e010.jpg links) tend to be less fragile than adverse social ties (An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e011.jpg links) [37], [43]. The latter result is consistent with our empirical intuitions and is widely observed in the real world. However, most of the works on this issue are investigated only by numerical methods and not by analytical approaches. This is mainly because it is difficult to describe the coevolution of strategy and structure of a network analytically.

Pacheco et al. approximate their linking dynamics by ordinary differential equations [39][41], [43]. They found that fast linking dynamics leads to a transformation of the payoff matrix, such that e.g. cooperation in a Prisoner's Dilemma can be stabilized. This approach does not keep the total number of links constant. Moreover, the analytical approach does not take stochastic effects into account.

Here, we consider a linking dynamics described by a discrete stochastic model. The evolution of links can be described as a Markov chain, which is the starting point for our analytical considerations. We specify the conditions required for the payoff matrix to make cooperation stable. A simple rule is obtained when the linking dynamics proceeds sufficiently fast, which reveals quantitatively how the link breaking probabilities have to be chosen such that cooperation may gain a foothold. Furthermore, we show how our stochastic linking dynamics also results in a transformation of the payoff matrix as in [39].

Analysis

We consider the coevolution of strategy and structure in the PD game. Each player's strategy An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e012.jpg can either be cooperation (C) or defection (D), denoted by An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e013.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e014.jpg, respectively. Initially, the whole population of size An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e015.jpg are situated on vertices of a regular graph with degree An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e016.jpg, where nodes indicate individuals while edges denote the pairwise partnerships between individuals. We consider the case where the total number of agents An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e017.jpg is much larger than the average degree An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e018.jpg. The payoff of each individual is obtained by playing the PD game with all of its immediate neighbors:

equation image
(2)

where An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e020.jpg represents the neighborhood set of player An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e021.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e022.jpg is the payoff matrix. Instead of the general matrix of the Prisoner's Dilemma Eq. (1) with four parameters, we consider a simpler payoff matrix,

equation image
(3)

where the parameter An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e024.jpg, measuring how profitable unilateral defection is, ranges from zero to one. Note that this payoff matrix recovers the payoff ranking described above, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e025.jpg.

We emphasize that Eq.(3) describes a special case of general PD games, but it is widely used in biology and sociology [1].

In each time step, an agent has the opportunity to change its strategy with probability An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e026.jpg. With probability An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e027.jpg, a link in the network can be changed. For An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e028.jpg, no strategy update takes place, hence the cooperation level stays unchanged and only the dynamical organization of cooperators and defectors can be observed [45]. For An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e029.jpg, this model degenerates to a PD game on a static regular graph, which has been studied in great detail [16], [19], [22], [29], [48].

Let us first consider the dynamics of links (which occurs with probability An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e030.jpg). In each rewiring step, a link An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e031.jpg is selected from the network at random (An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e032.jpg). The link remains intact with probability An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e033.jpg. With probability An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e034.jpg, the link is broken. In this case, one of the two adjacent players is picked at random and switches to a random player who is not its immediate neighbor in the population (see Fig. (1)). In this way, link An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e035.jpg is broken and a new link An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e036.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e037.jpg is introduced.

Figure 1
Linking dynamics.

We consider the case of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e039.jpg. In this case, linking dynamics does not assume rationality of agents: Adverse An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e040.jpg links may be kept and advantageous An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e041.jpg links may sometimes be broken.

In contrast with previous analytical work focusing on a dynamical number of links [39], here the total number of links An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e042.jpg is constant in the evolution process as in [33], [38]. This constraint can imply a limited resource and avoids that all individuals are linked to all others (for generic parameter choices).

In the beginning, each link is assigned a name An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e043.jpg, where An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e044.jpg. In each time step, we choose a link An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e045.jpg at random, where the superscript denotes the time. If the selected link An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e046.jpg does not break, we have An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e047.jpg. If the link breaks, a new social tie is introduced, denoted as An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e048.jpg. We denote the type of link An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e049.jpg by An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e050.jpg, where An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e051.jpg can be An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e052.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e053.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e054.jpg. Herein, we investigate how An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e055.jpg changes with time An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e056.jpg.

The dynamics of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e057.jpg can be captured by a Markov chain with transition matrix An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e058.jpg, which is the probability that an An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e059.jpg link transforms to a An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e060.jpg link in one time step. According to the linking dynamics, the probability of moving between An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e061.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e062.jpg is zero. So, we only have to calculate An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e063.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e064.jpg.

For instance, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e065.jpg is the probability that An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e066.jpg of type An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e067.jpg transforms to An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e068.jpg of type An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e069.jpg. This occurs in the following cases:

  1. When An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e070.jpg is not selected in the linking dynamics (with probability An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e071.jpg);
  2. When An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e072.jpg is selected (with probability An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e073.jpg), this happens either when the original An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e074.jpg link is not broken off (with probability An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e075.jpg) or when the selected player of the original link switches to another cooperator provided the link is broken (with probability An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e076.jpg where An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e077.jpg is the frequency of cooperators). Hence,
    equation image
    (4)
    Similar considerations for other links lead to the transition probability matrix
    equation image
    (5)
    where An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e080.jpg is the identity matrix and the matrix An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e081.jpg is given by
    equation image
    (6)
    and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e083.jpg is the frequency of defectors. We emphasize that the transition matrix is only an approximation, because it does not exclude the case that a player establishes a second link with one of its immediate neighbors. However, the approximation is very good when the degree of all links is much smaller than the population size.

Note that this Markov chain is irreducible and aperiodic when An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e084.jpg, hence there exists a unique stationary distribution An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e085.jpg determined by equation An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e086.jpg [49]. We find that

equation image
(7)

where An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e088.jpg is a normalization factor. Here, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e089.jpg represents the probability that a link An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e090.jpg is of type An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e091.jpg in the stationary regime. Therefore, the average number of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e092.jpg links An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e093.jpg is given by:

equation image
(8)

Thus, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e095.jpg also represents the average fraction of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e096.jpg links in the whole population in the stationary regime of the linking dynamics.

Let us now consider the dynamics of strategies (which occurs with probability An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e097.jpg). A player An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e098.jpg with strategy An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e099.jpg is selected at random, subsequently player An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e100.jpg with strategy An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e101.jpg is randomly selected among An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e102.jpg's current neighbors. Player An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e103.jpg compares the payoff with that of player An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e104.jpg and takes strategy An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e105.jpg with probability [48], [50]

equation image
(9)

where An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e107.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e108.jpg are the accumulated payoffs for An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e109.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e110.jpg, respectively. The parameter An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e111.jpg denotes the intensity of selection. For An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e112.jpg, selection is weak and strategy changes are almost random. For An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e113.jpg, selection is strong and strategies of more successful agents are always adopted, whereas less successful agents are never imitated. In large, well mixed populations the dynamics can be approximated by [51]

equation image
(10)

where An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e115.jpg is the Gaussian white noise with variance An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e116.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e117.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e118.jpg denote the average fitness of a cooperator and a defector, respectively. For large population size An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e119.jpg, the stochastic term vanishes [51] and we obtain

equation image
(11)

Note that this equation has the same equilibrium properties as the usual replicator dynamics [8]

equation image
(12)

If An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e122.jpg is sufficiently small, the structure of the system is close to the stationary state when strategies change. In this case, the stationary distribution of linking dynamics determines the average fitness of individuals [39]. Then, we can employ the strategy dynamics from well mixed populations for our structured system. The average payoff of cooperators is given by

equation image
(13)

The average payoff of defectors is

equation image
(14)

Equating An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e125.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e126.jpg or, equivalently, substituting them into Eq. (12), we find that an unstable equilibrium An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e127.jpg emerges when

equation image
(15)

It is located at

equation image
(16)

This critical value An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e130.jpg determines the attraction basin of cooperation An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e131.jpg: Cooperators take over when their initial frequency An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e132.jpg is larger than this critical value, whereas defectors take over when An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e133.jpg is less than this critical value. In other words, the evolutionary PD game with linking dynamics is similar to that of the coordination game in well mixed population where both cooperation and defection are best replies to themselves.

Let us show how the PD game transforms into a coordination game under linking dynamics. Substituting Eqs. (13)(14) into Eq. (12) yields

equation image
(17)

where the first factors are always positive and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e135.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e136.jpg are the payoffs of cooperators and defectors in a modified game with payoff matrix

equation image
(18)

In other words, the coevolution of strategy and structure transforms the original PD game into another one. In particular, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e138.jpg turns to a coordination game when An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e139.jpg, i.e., An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e140.jpg. Thus, the PD game with linking dynamics corresponds to a coordination game in a well mixed population [39], [40]. Cooperation is stable only when

equation image
(19)

where An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e142.jpg.

The quantity An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e143.jpg measures the propensity for cooperators to form clusters that supports cooperation [16]. Indeed, remembering that An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e144.jpg indicates the probability with which an An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e145.jpg link breaks, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e146.jpg characterizes the fragility ratio between An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e147.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e148.jpg link. In particular, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e149.jpg link are more fragile than An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e150.jpg links if An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e151.jpg exceeds zero. In other words, a cooperator is more likely to play with cooperators than defectors and to sustain the social relationship when An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e152.jpg is greater than zero. Therefore An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e153.jpg also illustrates how likely a cooperator is to interact with a cooperator. The greater An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e154.jpg, the more likely it is for cooperators to form clusters.

Increasing An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e155.jpg allows cooperators to spread more effectively and can allow them to invade from initially small clusters [52]. The quantity An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e156.jpg characterizes the propensity of cooperators to form clusters. Cooperation gains a foothold when An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e157.jpg is sufficiently large. Precisely, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e158.jpg is sufficiently large when An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e159.jpg by Eq. (19). In this case, cooperator clusters expand and take over the whole population.

We have explained intuitively how An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e160.jpg enhances cooperation level. In addition, we can also show analytically that large An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e161.jpg leads to cooperation by enlarging the cooperation attraction basin:

Substituting An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e162.jpg to Eq. (16), we obtain:

equation image
(20)

The quantity An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e164.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0011187.e165.jpg is always negative for all permitted parameters. Hence, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e166.jpg is a decreasing function of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e167.jpg. Since An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e168.jpg is the attraction basin of cooperation. Accordingly, increasing An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e169.jpg enlarges the attraction basin of cooperation. In other words, it requires fewer cooperators to take over the whole population with larger An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e170.jpg.

So far, it has been shown that the simple rule gives us an insight on how cooperation comes into being with linking dynamics. Furthermore, it can also be revealed that An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e171.jpg links should be less fragile [39] while An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e172.jpg ones should be easy to break in order to promote cooperation. Since An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e173.jpg, the larger An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e174.jpg or the smaller An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e175.jpg, the greater An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e176.jpg is. Thus cooperation is promoted when the probability to break An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e177.jpg links An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e178.jpg is large or the probability to break An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e179.jpg links An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e180.jpg is small. This is in line with previous numerical consideration [37], [38]. However, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e181.jpg is independent of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e182.jpg. Does this mean that An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e183.jpg has no impact on cooperation? In fact, it is not the case. On the contrary, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e184.jpg plays an important role in promoting cooperation when An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e185.jpg holds. Actually, this simple rule only guarantees that the equilibrium An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e186.jpg of Eq. (16) lies between zero and one, where it is defined. However it is not sufficient to make cooperation advantageous. Besides, the initial frequency of cooperators should lie in the attraction basin of cooperation An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e187.jpg to make cooperators gain a foothold in the population. Nevertheless, notice that Eq. (16) can be rewritten as:

equation image
(21)

hence, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e189.jpg is a decreasing function of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e190.jpg provided An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e191.jpg, i.e. the simple rule holds. In this way, increasing An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e192.jpg augments the attraction basin of cooperation An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e193.jpg (See Fig. (2)). Thus it is easier for cooperators to gain a foothold when An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e194.jpg is larger.

Figure 2
Final fraction of cooperators as a function of initial fraction of cooperators.

In Fig. (3), we show that the simulation results are in agreement with our analytical predictions when the selection pressure is high, while the simulations deviate from the analytical results when the selection pressure is low. For strong selection, we find above the line An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e206.jpg, the cooperation level is low, which is consistent with our theoretical predictions. For weak selection, however, the cooperation level is almost An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e207.jpg for the parameter region closely above the line for An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e208.jpg between An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e209.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e210.jpg, where the cooperation level should be low based on our the simple rule.

Figure 3
Results for the final fraction of cooperators for different selection pressure An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e211.jpg.

These deviations are due to both the finite population effect and the approximation of linking dynamics by Eq. (5). On the one hand, as mentioned above, the transition matrix Eq. (6) is only an approximation based on the global frequency of cooperators, while they are also influenced by local frequencies in the simulations. On the other hand, we use the replicator equation to describe the strategy evolution. But the replicator equation is only an approximation of the strategy evolution when the population size is sufficiently large, which implies that small fitness differences can influence the dynamics. This explains why our theoretical predictions are less accurate for weak selection. Therefore, we focus on strong selection in the following.

We first investigate how An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e218.jpg affects the evolution of cooperation. For each plot in Fig. (4), above the line An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e219.jpg, there is nearly no cooperation, while below the line, cooperation is possible. This is consistent with our simple rule. Furthermore, compared with the three plots in Fig. (4), we observe a decrease of the parameter region to sustain the cooperation when An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e220.jpg increases. It indicates that only a small temptation to defect can sustain cooperation.

Figure 4
Results for the final fraction of cooperators for different values of the payoff parameter An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e221.jpg.

Let us further examine the role of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e227.jpg in the evolution of cooperation by simulation. It is observed clearly in Fig. (5) that the more fragile An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e228.jpg ties are, the easier it is for cooperators to wipe out defectors. Intuitively, for greater An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e229.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e230.jpg links are more likely to break and defectors are no longer trapped in their fruitless interactions and can instead seek new cooperators to exploit. Thus, it seems less likely to promote cooperation for large An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e231.jpg. However, both analytical and simulation results show that high An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e232.jpg promotes cooperation (See Eq. (21) and Fig. (2)). This is counter-intuitive. In fact, in this case, the quick partner-switching between defectors induces the heterogeneity of the population, which results in cooperation. Similar results have been reported in [43].

Figure 5
Results for the final fraction of cooperators for different values of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e233.jpg.

Finally, we turn to investigate the role of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e238.jpg on the coevolution. Fig. (6) shows that for small An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e239.jpg, the result is in good agreement with the theoretical prediction, while deviates from the simple rule for large An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e240.jpg, as expected. Similar results have been reported in the analytical approach of Pacheco et al. [39]. Both analytical approaches are based on the time scale separation, i.e., all the links are almost in the stationary states when the strategy update occurs.

Figure 6
Results for the final fraction of cooperators for different values of An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e241.jpg.

Results and Discussion

To sum up, we have established a discrete model to describe the stochastic linking dynamics analytically in terms of a Markov chain. Based on this linking dynamics, we have studied the coevolution of strategy and network structure. A simple condition for the evolution of cooperation is obtained analytically that becomes more accurate when selection is stronger. The rule shows that the less fragile An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e245.jpg links are, the easier cooperation emerges. The more fragile An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e246.jpg links are, the easier cooperation prevails.

Compared to Pacheco et al.'s work, time scales separation also plays an important part in our analysis. In Pacheco et al.'s work, time separation is used to ensure that the linking dynamics is in the stationary regime when the strategy evolution happens. But in contrast to Pacheco et al.'s work, our analytical approach explicitly considers stochastic effects in the linking dynamics. Further, when the population size is sufficiently large, this Markov chain describing the linking dynamics can be approximated by a different system of differential equations. Since the total number of links is constant in our approach, there are only two independent variables describing the different kinds of links. In Pacheco et al.'s method, however, all the three variables are independent. In general, both methods lead to very similar qualitative results.

Regarding the coevolution of strategy and network, previous numerical work with constant number of links has assumed that dissatisfied ties are more likely to break off than satisfied ones. In this case, cooperation is more likely to be sustained. However, it has not been shown analytically that to what extent satisfied links are more stable than adverse ones to make cooperation gain a foothold. The simple rule An external file that holds a picture, illustration, etc.
Object name is pone.0011187.e247.jpg reveals such a relation between the payoff matrix and the parameters of the linking dynamics. It shows under which conditions cooperation may prevail, provided the linking dynamics is sufficiently fast. Furthermore, we have provided a series of numerical results to validate the analytical results. We find that numerical results are in agreement with the analytical results for strong selection, yet may deviate from the analytical results for weak selection.

Acknowledgments

We thank C.S. Gokhale and W. Huang for help.

Footnotes

Competing Interests: The authors have declared that no competing interests exist.

Funding: B.W. gratefully acknowledges the financial support from China Scholarship Council (2009601286). D.Z. acknowledges support by the Natural Science Foundation of China (10625101) and 973 Fund (2006CB805900). L.W. acknowledges support by the National Natural Science Foundation of China (10972002 and 60736022). A.T. acknowledges support by the Emmy-Noether program of the Deutsche Forschungsgemeinschaft. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

References

1. Nowak MA. Evolutionary Dynamics. Cambridge, MA: Harvard University Press; 2006.
2. Sigmund K, editor. The calculus of selfishness. Princeton, New Jersey: Princeten University Press; 2010.
3. Axelrod R. The Evolution of Cooperation. New York: Basic Books; 1984.
4. Levin SA, editor. Games, Groups and the Global Good. Springer Series in Game Theory. Springer; 2009.
5. Nowak MA. Five rules for the evolution of cooperation. Science. 2006;314:1560–1563. [PMC free article] [PubMed]
6. Nash JF. Equilibrium points in N-person games. Proc Natl Acad Sci USA. 1950;36:48–49. [PubMed]
7. Maynard Smith J. Evolution and the Theory of Games. Cambridge: Cambridge University Press; 1982.
8. Hofbauer J, Sigmund K. Evolutionary Games and Population Dynamics. Cambridge: Cambridge University Press; 1998.
9. Hamilton WD. The genetical evolution of social behavior I. J Theor Biol. 1964;7:1–16. [PubMed]
10. Trivers RL. The evolution of reciprocal altruism. Q Rev of Biol. 1971;46:35–57.
11. Ohtsuki H, Nowak MA. Direct reciprocity on graphs. J Theor Biol. 2007;247:462–470. [PMC free article] [PubMed]
12. Wedekind C, Milinski M. Cooperation through image scoring in humans. Science. 2000;288:850–852. [PubMed]
13. Nowak MA, Sigmund K. Evolution of indirect reciprocity. Nature. 2005;437:1291–1298. [PubMed]
14. Wilson DS. A theory of group selection. Proc Natl Acad Sci USA. 1975;72:143–146. [PubMed]
15. Wilson DS, Wilson EO. Rethinking the theoretical foundation of sociobiology. Q Rev of Biol. 2007;82:327–348. [PubMed]
16. Nowak MA, May RM. Evolutionary games and spatial chaos. Nature. 1992;359:826–829.
17. Santos FC, Pacheco JM, Lenaerts T. Evolutionary dynamics of social dilemmas in structured heterogeneous populations. Proc Natl Acad Sci USA. 2006;103:3490–3494. [PubMed]
18. Santos FC, Pacheco JM. Scale-free networks provide a unifying framework for the emergence of cooperation. Phys Rev Lett. 2005;95:098104. [PubMed]
19. Szabó G, Hauert C. Phase transitions and volunteering in spatial public goods games. Phys Rev Lett. 2002;89:118101. [PubMed]
20. Szabó G, Fáth G. Evolutionary games on graphs. Physics Reports. 2007;446:97–216.
21. Ohtsuki H, Hauert C, Lieberman E, Nowak MA. A simple rule for the evolution of cooperation on graphs. Nature. 2006;441:502–505. [PMC free article] [PubMed]
22. Perc M. Transition from gaussian to levy distributions of stochastic payoff variations in the spatial prisoner's dilemma game. Phys Rev E. 2007;75:022101. [PubMed]
23. Tomassini M, Luthi L, Giacobini M. Hawks and doves on small-world networks. Phy Rev E. 2006;73:016132. [PubMed]
24. Chen X, Fu F, Wang L. Promoting cooperation by local contribution under stochastic win-stay-lose-shift mechanism. Physica A. 2008;387:5609–5615.
25. Nowak MA, Tarnita CE, Antal T. Evolutionary dynamics in structured populations. Phil Trans Roy Soc London B. 2010;365:19–30. [PMC free article] [PubMed]
26. Taylor C, Nowak MA. Transforming the dilemma. Evolution. 2007;61:2281–2292. [PMC free article] [PubMed]
27. Traulsen A. Mathematics of kin-and group-selection: Formally equivalent? Evolution. 2009;64:316–323. [PubMed]
28. Bshary R, Grutter AS. Punishment and partner switching cause cooperative behaviour in a cleaning mutualism. Biology Letters. 2005;1:396–399. [PMC free article] [PubMed]
29. Lindgren K, Nordahl MG. Evolutionary dynamics of spatial games. Physica D. 1994;75:292–309.
30. Skyrms B, Pemantle R. A dynamical model of social network formation. Proc Natl Acad Sci USA. 2000;97:9340–9346. [PubMed]
31. Bala V, Goyal S. Conformism and diversity under social learning. J Econ Theory. 2001;17:101–120.
32. Ebel H, Bornholdt S. Evolutionary games and the emergence of complex networks. 2002. cond-mat/0211666.
33. Zimmermann MG, Eguluz VM. Cooperation, social networks, and the emergence of leadership in a prisoner's dilemma with adaptive local interactions. Phys Rev E. 2005;72:056118. [PubMed]
34. Poncela J, Gómez-Gardeñes J, Traulsen A, Moreno Y. Evolutionary game dynamics in a growing structured population. New Journal of Physics. 2009;11:083031.
35. Hanaki N, Peterhansl A, Dodds PS, Watts DJ. Cooperation in evolving social networks. Management Science. 2007;53:1036–1050.
36. Biely C, Dragosit K, Thurner S. Prisoners dilemma on dynamic networks under perfect rationality. Physica D. 2007;228:40–48.
37. Fu F, Hauert C, Nowak MA, Wang L. Reputation-based partner choice promotes cooperation in social networks. Phy Rev E. 2008;78:026117. [PMC free article] [PubMed]
38. Santos FC, Pacheco JM, Lenaerts T. Cooperation prevails when individuals adjust their social ties. PLoS Comput Biol. 2006;2:1284–1291. [PubMed]
39. Pacheco JM, Traulsen A, Nowak MA. Co-evolution of strategy and structure in complex networks with dynamical linking. Phys Rev Lett. 2006;97:258103. [PMC free article] [PubMed]
40. Pacheco JM, Traulsen A, Nowak MA. Active linking in evolutionary games. J Theor Biol. 2006;243:437–443. [PMC free article] [PubMed]
41. Pacheco JM, Traulsen A, Ohtsuki H, Nowak MA. Repeated games and direct reciprocity under active linking. J Theor Biol. 2008;250:723–731. [PMC free article] [PubMed]
42. Segbroeck SV, Santos FC, Lenaerts T, Pacheco JM. Reacting differently to adverse ties promotes cooperation in social networks. Phy Rev Lett. 2009;102:058105. [PubMed]
43. Segbroeck SV, Santos FC, Nowé A, Pacheco JM, Lenaerts T. The evolution of prompt reaction to adverse ties. BMC Evolutionary Biology. 2008;8:287. [PMC free article] [PubMed]
44. Zschaler G, Traulsen A, Gross T. A homoclinic route to full cooperation on adaptive social networks. 2009;arXiv:09100940.
45. Do AL, Rudolf L, Gross T. Patterns of cooperation: fairness and coordination in self-organized networks of interacting agents. New Journal of Physics. 2009 (in press)
46. Gross T, Blasius B. Adaptive coevolutionary networks - a review. J R Soc Interface. 2008;5:259–271. [PMC free article] [PubMed]
47. Perc M, Szolnoki A. Coevolutionary games - a mini review. Biosystems. 2010;99:109–125. [PubMed]
48. Szabó G, Töke C. Evolutionary Prisoner's Dilemma game on a square lattice. Phys Rev E. 1998;58:69.
49. Karlin S, Taylor HMA. A First Course in Stochastic Processes. London: Academic, 2nd edition edition; 1975.
50. Blume LE. The statistical mechanics of strategic interaction. Games and Economic Behavior. 1993;5:387–424.
51. Traulsen A, Nowak MA, Pacheco JM. Stochastic dynamics of invasion and fixation. Phys Rev E. 2006;74:011909. [PMC free article] [PubMed]
52. Helbing D, Yu W. The outbreak of cooperation among success-driven individuals under noisy conditions. Proc Natl Acad Sci USA. 2009;106:3680–3685. [PubMed]

Articles from PLoS ONE are provided here courtesy of Public Library of Science