Cooperation percolation in spatial prisoner's dilemma game

Cooperation is ubiquitous in biological and social systems [1]. Understanding the emergence and persistence of cooperation among selfish individuals remains an outstanding problem. The development of evolutionary game theory has offered a powerful mathematical framework to address this problem [2]. In order to capture the interaction pattern among greedy individuals, various models have been introduced, among which the prisoner's dilemma game (PDG) has been a prevailing paradigm [3].

In the original PDG, two players simultaneously decide whether to cooperate or defect. They both receive the payoff R upon mutual cooperation and the payoff P upon mutual defection. If one cooperates but the other defects, the defector gets the payoff T, while the cooperator gains the payoff S. The payoff rank for the PDG is T > R > P > S. As a result, in a single round of PDG, mutual defection is the best strategy for both players, rendering the social dilemma, in other words, the Nash equilibrium. For simplicity, but without loss of generality, the elements of the payoff matrix for the PDG are often rescaled with T = b > 1, R = 1 and P = S = 0 [4], where b denotes the temptation to defect. Since the pioneering work of Nowak and May [4], evolutionary games have been extensively studied in a structured population, including regular lattices [5–16] and complex networks [17–36]. To facilitate cooperation in the spatial PDG, a number of mechanisms have been proposed, such as voluntary participation [37], punishment [38], similarity [39], inhomogeneous activity [40], social diversity [41, 42], dynamical linking [43], asymmetric interaction and replacement graph [44], migration [45–48], in-group favoritism [49], interdependent links [50, 51] and so on.

It has been known that the formation of cooperator clusters plays an important role in promoting cooperation in spatial games [52]. A cooperator cluster is defined as a connected component (subgraph) fully occupied by cooperators. Within clusters, cooperators can assist each other and the benefits of mutual cooperation outweigh the losses against the defector. It is of paramount importance to explore the dynamical organization of the cooperator clusters so as to understand the emergence of cooperation among selfish individuals. Previous studies focused on the size distribution of the cooperator clusters [53, 54], but paid little attention to the conditions under which a giant cooperator cluster of the order of the system size arises. In this paper, we attempt to address this issue from the perspective of percolation theory [55, 56]. In recent years, the percolation transition, characterized by a large spanning cluster arising at the critical point, has been widely found in various dynamical processes, such as the spreading of disease [57], the formation of public opinion [58] and cascading failures [59]. In particular, percolation phenomena with respect to optimal cooperation level in diluted system were discovered in [60, 61]. However, percolation phenomena pertaining to the emergence of cooperator clusters have not yet been studied in the framework of evolutionary games. Here, we report percolation transition behavior characterized by the emergence of a large spanning cooperator cluster when the initial fraction of the cooperators in the system exceeds a certain threshold. The phase transition can be classified to either regular site percolation or invasion percolation with trapping, depending on the temptation to defect. We substantiate our findings by systematic numerical simulations and analysis of the phase transition.

The paper is organized as follows. In section 2, we formalize the problem by introducing the PDG on square lattices. In section 3, we study the cooperation percolation in terms of different values of the temptation to defect. Finally, conclusions and discussions are presented in section 4.

Individuals are located on a L × L square lattice with periodic boundary conditions. Each individual x can follow one of two strategies: cooperation or defection, described by

$$\begin{equation} z_{x} =\left( \begin{array}{c} 1 \\ 0 \\ \end{array} \right)\qquad \mathrm{or}\qquad \left( \begin{array}{c} 0 \\ 1 \\ \end{array} \right), \end{equation} \tag{ 1 }$$

respectively. At each timestep, each individual plays the PDG with its four nearest neighbors. The accumulated payoff of individual x can be expressed as

$$\begin{equation} P_{x}=\sum_{y\in \Omega_{x}}z_{x}^{\rm T}Mz_{y}, \end{equation} \tag{ 2 }$$

where the sum runs over the nearest neighbor set Ω_x of node x and M is the rescaled payoff matrix with

$$\begin{equation} M=\left( \begin{array}{cc} 1 & 0 \\ b & 0 \\ \end{array} \right). \end{equation} \tag{ 3 }$$

According to the setting in [62], initially, the cooperation and the defection strategies are randomly assigned to all individuals in terms of some probabilities: with probability f a node occupied by a cooperator and with probability 1 − f a node occupied by a defector. The individuals asynchronously update their strategies in a random sequential order [63–66]. A randomly selected player compares its payoff with its nearest neighbors and changes strategy by following the one (including itself) with the highest payoff. After a period of transient time, the system will enter a steady state.

We focus on the formation of the cooperator clusters in the steady state. In order to study the critical behavior regarding the giant cooperator cluster, we employ the normalized size of the largest cooperator cluster s₁, the susceptibility χ and the Binder's fourth-order cumulant U. These quantities are defined as follows [68]:

$$\begin{equation} s_{1}=\frac{S_{1}}{N}, \end{equation} \tag{ 4 }$$

$$\begin{equation} \chi=N[\langle s_{1}^{2} \rangle - \langle s_{1} \rangle^{2}], \end{equation} \tag{ 5 }$$

$$\begin{equation} U=1-\frac{\langle s_{1}^{4} \rangle}{3\langle s_{1}^{2} \rangle^{2}}, \end{equation} \tag{ 6 }$$

where S₁ is the size of the largest cooperator cluster, N = L × L is the system size and 〈···〉 stands for the configurational averages. According to the standard finite-size scaling approach [68], the phase transition point can be identified by Binder's fourth-order cumulant U and there are the following power-law relationships at the critical value:

$$\begin{equation} s_{1}\sim N^{-\beta/\nu} \quad \mathrm{and} \quad \chi\sim N^{\gamma/\nu}. \end{equation} \tag{ 7 }$$

We can use the tool to identify the phase transitions pertaining to the formation of the cooperator clusters and explore the class to which the phase transition belongs.

According to our analysis of the phase transition, we can separate the values of b into four regions: b∈(1,4/3), (4/3,3/2), (3/2,2) and (2,∞). We find that in the same region, the cooperator clusters with respect to the percolation transition remain unchanged, irrespective of the value of b. In the following, we present the results in the four regions respectively.

3.1. The case of 1 < b < 4/3

We first explore the characteristics of the cooperator clusters when 1 < b < 4/3. Figure 1 shows snapshots of the spatial distributions of the cooperators and the defectors on a 200 × 200 square lattice. We can observe that the size of the largest cooperator cluster (denoted by red) expands as the initial fraction of cooperators f increases. In contrast, the size of the second largest cooperator cluster (denoted by blue) first becomes larger but then shrinks as f continuously increases. The non-monotonic relationship between the size of the second largest cooperator cluster and f implies the existence of a second-order phase transition [67].

Zoom In Zoom Out Reset image size

Figure 2 shows the normalized size of the largest cooperator cluster s₁ and the fraction F_c of cooperators in the population, as a function of f. We see that both F_c and s₁ increase toward 1 as f increases. Over a wide range of f, F_c is larger than s₁, whereas for very small and large values of f, F_c is approximately equal to s₁. In figure 2, we can also find that there exists a critical value f_c, below which s₁ approaches 0, while above it s₁ continuously increases as f increases. The fact that F_c > 0.5 at f_c suggests that it is possible for the cooperators to form a giant cluster comparative to the size of the system, insofar as sufficient numbers of cooperators survive during the evolution.

Zoom In Zoom Out Reset image size

Figure 3 shows the normalized size of the largest cooperator cluster s₁, the susceptibility χ and the reduced Binder's fourth-order cumulant U as a function of f for different lattice sizes L. Figure 3(a) shows that s₁ is almost the same for different values of L for large f. However, when f is below some value, s₁ decreases as L increases. Figure 3(b) shows that the susceptibility χ reaches a maximum at some value of f for different values of L. Moreover, one can see that the value of f that corresponds to the peak of χ increases with L. The critical value f_c can then be identified in figure 3(c), where the curves of the reduced fourth-order cumulant U for different L intersect with each other [69, 70]. The intersection point gives f_c ≃ 0.7551 for 1 < b < 4/3.

Zoom In Zoom Out Reset image size

Figure 4 shows s₁ and χ as a function of N at the critical value f_c. From figures 4(a) and (b), we obtain the critical exponents β/ν ≃ 0.051 and γ/ν ≃ 0.908, which are very close to the critical exponents of the regular site percolation (β/ν ≃ 0.052 and γ/ν ≃ 0.896) [67]. These results indicate that the cooperation percolation belongs to the same universality class as the regular site percolation when 1 < b < 4/3.

Zoom In Zoom Out Reset image size

3.2. The case of 3/2 < b < 2

We explore the cooperation percolation when 3/2 < b < 2. Figure 5 shows the normalized size of the largest cooperator cluster s₁, the susceptibility χ and the reduced Binder's fourth-order cumulant U as a function of f for different lattice sizes L. As shown in figure 5(a), s₁ decreases as the system size increases when f is below some value. The susceptibility χ reaches the maximal value at some value of f (see figure 5(b)) and the reduced fourth-order cumulants cross at the critical point f_c ≃ 0.9553 (see figure 5(c)).

Zoom In Zoom Out Reset image size

Figure 6 shows s₁ and χ as a function of the system size N at the critical value f_c. In figures 6(a) and (b), we obtain the critical exponents β/ν ≃ 0.082 and γ/ν ≃ 0.856, which are close to the critical exponents of the invasion percolation with trapping (β/ν ≃ 0.084 and γ/ν ≃ 0.832) [71]. These results demonstrate that the cooperation percolation belongs to the same universality class as the invasion percolation with trapping in the region of 3/2 < b < 2.

Zoom In Zoom Out Reset image size

3.3. The cases of 4/3 < b < 3/2 and b > 2

Figure 7(a) shows the normalized size of the largest cooperator cluster s₁ and the fraction of cooperators F_c, as a function of the initial concentration of the cooperators f when 4/3 < b < 3/2. One can observe that F_c is much lower than 1 and s₁ ≈ 0 even when f is very close to 1. Figure 7(b) shows s₁ as a function of N when initially there is only one defector in the system. We can find that s₁ decreases as N increases. Figure 7 demonstrates that the percolation threshold for 4/3 < b < 3/2 is f_c = 1. To intuitively understand why the threshold is 1 in the parameter region, we explore the evolution of the spatial distributions of the cooperators and the defectors on a square lattice given a single defector at the center initially (t = 0). Figure 8 shows that eventually a giant reticular defector cluster is formed and many small cooperator clusters are separated by the defectors. This result is in agreement with that reported in  [72], i.e. the defectors can spread over the system even if initially there is only one defector in the region of 4/3 < b < 3/2. Hence, only the absence of the defector can lead to a large cooperator cluster that covers the whole lattice, accounting for the phase transition at f_c = 1.

Zoom In Zoom Out Reset image size

Zoom In Zoom Out Reset image size

In the case of b > 2, the cooperators cannot survive when f < 1 (the results are not shown here), implying that even one defector can lead to the extinction of the cooperators in the ocean of cooperators when b > 2. We can thus infer that the percolation threshold for b > 2 is also f_c = 1.

In conclusion, we have explored the formation of the cooperator clusters in the PDG, finding that the process of establishing a giant cluster pertains to the percolation behavior. In particular, when the initial fraction of the cooperators in the system exceeds a critical threshold, there arises a giant spanning cooperator cluster, resulting from the merging of many small cooperator clusters. The phase transition behavior is validated by various scaling laws at the critical point, such as the normalized size of the largest cooperator cluster and the susceptibility scale with the system size. Strikingly, the phase transition belongs to different universality classes, depending on the temptation to defect. The results on the square lattices demonstrate that the phase transition is subject to the class of regular site percolation when 1 < b < 4/3 or invasion percolation with trapping when 3/2 < b < 2 whereas in the parameter region 4/3 < b < 3/2 and b > 2, the percolation threshold is 1, indicating that even one defector can prevent the formation of large cooperator clusters. Interestingly, we found that the partition of the parameter region in terms of percolation is exactly the same as the previous findings based on the chaotic spatial patterns in the literature [4, 72]. The agreement offers an underlying connection between the phase transition and the spatial chaos in evolutionary games.

Our findings presented here raise a number of questions, answers to which could further deepen our understanding of the persistence and the dominance of cooperation in terms of a large cooperator cluster. For example, for strategy updating rules rather than the currently used best-take-over rule, such as the Fermi rule [63], does the percolation transition remain? If the answer is positive, will the universality class change? Another significant question pertaining to the network structure is how does the structural property affect the percolation phenomena, e.g. small-world and scale-free topology. Taken together, our results indicate that cooperation in many evolutionary games can be explored from the perspective of the cooperator clusters in combination with the tools for quantifying the phase transition and the percolation, opening new avenues to deepening our understanding of the cooperative behavior widely observed in many aspects in nature and society.

This work was supported by the National Natural Science Foundation of China (grant numbers 11247266, 11105011 and 61004098), the Natural Science Foundation of Fujian Province of China (grant number 2013J05007), the Research Foundation of UESTC and Hong Kong Scholars Program (grant number G-YZ4D) and the Research Foundation of Fuzhou University (grant number 0110-600607).