Rewarding evolutionary fitness with links between populations promotes cooperation

Evolution of cooperation in the prisoner's dilemma and the public goods game is studied, where initially players belong to two independent structured populations. Simultaneously with the strategy evolution, players whose current utility exceeds a threshold are rewarded by an external link to a player belonging to the other population. Yet as soon as the utility drops below the threshold, the external link is terminated. The rewarding of current evolutionary fitness thus introduces a time-varying interdependence between the two populations. We show that, regardless of the details of the evolutionary game and the interaction structure, the self-organization of fitness and reward gives rise to distinguished players that act as strong catalysts of cooperative behavior. However, there also exist critical utility thresholds beyond which distinguished players are no longer able to percolate. The interdependence between the two populations then vanishes, and cooperators are forced to rely on traditional network reciprocity alone. We thus demonstrate that a simple strategy-independent form of rewarding may significantly expand the scope of cooperation on structured populations. The formation of links outside the immediate community seems particularly applicable in human societies, where an individual is typically member in many different social networks.

In comparison to peer Semmann et al., 2003;de Quervain et al., 2004;Fowler, 2005;Hauert et al., 2007;Gächter et al., 2008;Ohtsuki et al., 2009;Rockenbach and Milinski, 2009;Deng et al., 2012;Vukov et al., 2013) and pool punishment Szolnoki et al., 2011;Perc, 2012;Traulsen et al., 2012), rewarding may lead to higher total earnings without potential damage to reputation (Milinski et al., 2002) or fear of retaliation (Dreber et al., 2008). The application of rewarding also avoids the problem of antisocial punishment (Herrmann et al., 2008), which has been shown to significantly challenge the effectiveness of sanctioning (Rand et al., 2010;Rand and Nowak, 2011). Although the majority of previous studies addressing the "stick versus carrot" dilemma (Sigmund et al., 2001;Hilbe and Sigmund, 2010) concluded that punishment is more effective than rewarding in sustaining public cooperation (Sigmund, 2007), evidence suggesting that rewards may be as effective as sanctions is mounting. Recent human experiments (Yamagishi et al., 2012;Egloff et al., 2013) also challenge the strong reciprocity model , and related theoretical explorations  indicate that the application of either reward or punishment, but not both, is evolutionary most advantageous.
Another relatively recent development is the study of evolutionary games on interdependent networks (Wang et al., 2012b;Gómez-Gardeñes et al., 2012b,a;Wang et al., 2012aWang et al., , 2013bJiang and Perc, 2013;Szolnoki and Perc, 2013b). The subject has gained on prominence after the discovery that even seemingly irrelevant changes in one network can have catastrophic and very much unexpected consequences in another network (Buldyrev et al., 2010). Since the evolution of cooperation, especially in human societies (Apicella et al., 2012;Rand and Nowak, 2013;Helbing, 2013), also proceeds on such interdependent networks, it is therefore of interest to determine to what extent this interdependence influences the outcome of evolutionary games. It has been shown, for example, that biased utility functions suppress the feedback of individual success and lead to a spontaneous separation of time scales on interdependent networks (Wang et al., 2012b). If utilities are symmetric, cooperation is promoted by means of interdependent network reciprocity that relies on the simultaneous formation of correlated cooperative clusters on both networks (Wang et al., 2013a). In addition to these examples, non-trivial organization of cooperators across the interdependent layers (Gómez-Gardeñes et al., 2012b), strategyindependent information sharing , probabilistic interconnectedness (Wang et al., 2012a), as well as optimal interdependence (Wang et al., 2013b), have all been shown to extend the boundaries of traditional network reciprocity (Nowak and May, 1992) past its limits on isolated networks (Santos et al., 2006;Ohtsuki et al., 2006;Szabó and Fáth, 2007;Perc et al., 2013).
Here we wish to extend the scope of evolutionary games on interdependent networks by introducing rewards for highenough evolutionary fitness of individual players in the form of additional links that bridge the gap between two initially disconnected populations. We introduce a utility threshold E that, if met or exceeded, allows the pertinent player to connect with the corresponding player in the other network. These rewards effectively introduce interdependence between the two populations, and they allow the rewarded players to increase their utility with a fraction of the utility of the player in the other population. However, as soon as the fitness of a player no longer reaches the threshold, its external link is terminated, although it may eventually be re-awarded if and when the utility of the player again becomes sufficiently large. Importantly, the onoff nature of the interdependence between the corresponding players in the two populations draws exclusively on the current level of fitness, without regard of previous evolutionary success or strategy. We consider the weak prisoner's dilemma game as representative for social dilemmas that are governed by pairwise interactions, and the public goods game which is representative for social dilemmas that are governed by group interactions. We also consider different types of networks to describe the interactions among players in each of the two structured populations. As we will show, regardless of these details, the self-organization of fitness and reward promotes the evolution of cooperation well past the boundaries imposed by traditional network reciprocity (Nowak and May, 1992), as well as past the boundaries imposed by interdependent network reciprocity (Wang et al., 2013a), if only the utility threshold is sufficiently large. On the other hand, the threshold must not exceed a critical value, which could be well below the maximal possible utility a cooperator is able to reach if it would be fully surrounded by other cooperators. We will extend and explain these results in detail in Section 3, while in the subsequent section we proceed with the description of the studied evolutionary games.

Evolutionary games
The evolutionary games are staged on two disjoint square lattices or random regular graphs with periodic boundary conditions, each of size N, where initially each player x is designated either as a cooperator (s x = C) or defector (s x = D) with equal probability. The weak prisoner's dilemma game is characterized by the temptation to defect T = b, reward for mutual cooperation R = 1, and both the punishment for mutual defection P as well as the suckers payoff S equaling 0, where 1 < b ≤ 2 (Nowak and May, 1992). In this case a player receives its payoff by playing the game with all its neighbors. For the public goods game, players are arranged into overlapping groups of size G, where every player is thus surrounded by its k = G − 1 neighbors and is a member in g = G different groups (Santos et al., 2008;Perc et al., 2013). In each group, cooperators contribute 1 to the public good, while defectors contribute nothing. The sum of contributions is subsequently multiplied by the factor r > 1, reflecting the synergetic effects of cooperation, and the resulting amount is equally shared amongst the G group members. Here the total payoff of a player is the sum of payoffs from all the g groups where she is member.
We simulate the evolutionary process on both networks in accordance with the standard Monte Carlo simulation procedure comprising the following elementary steps. First, a player x is selected randomly and its payoff Π x is determined based on the governing evolutionary game (either the weak prisoner's dilemma game or the public goods game). Next, a neighbor y from the same network is chosen randomly and acquires its payoff Π y in the same way. Lastly, player y adopts the strategy of player x with the probability where K = 0.1 quantifies the uncertainty related to the strategy adoption process (Szabó and Fáth, 2007), while U x and U y are the utilities of players x and y, respectively. All those players that have an external link to the corresponding player x ′ in the other network have the utility while those that do not have an external link retain U x = Π x . We emphasize at this point that the external links are directed. Hence, only player x benefits from the additional link, but not player x ′ . We also do not allow a direct interaction between the two mentioned players. Based on our preceding work (Wang et al., 2013b), where we have studied the general impact of the value of α and the related optimal interdependence between two networks, we here use a fixed value of α = 0.5 without loosing generality. Monte Carlo simulations are performed on sufficiently large networks ranging in size from N = 4·10 4 to 2.5 · 10 5 near transition points to avoid accidental extinction of the two competing strategies. The stationary fraction of cooperators ρ C is recorded after the system reaches dynamical equilibrium, i.e., when the average cooperation level becomes time independent. More specifically, we perform 10 4 Monte Carlo steps (MCS) to reach the stationary state, and subsequently 10 6 more steps to record ρ C . Moreover, we average the final outcome over up to 100 independent initial conditions to further improve accuracy. To distinguish who is eligible for an external link, we introduce a two-value tag for each player. If q x = 1 the utility of the player x is determined according to Eq. 2, while if q x = 0 the utility remains equal to the payoff stemming from the interactions on the host network. Initially all players have q x = 0. Subsequently, if the utility of player x with its current tag value is equal or above the threshold E, we set q x = 1. If not, the tag remains zero. Evidently, if the value of E is minimal, which is E = 0 for the weak prisoner's dilemma game, then all players are rewarded with an external link and hence are able to enhance their utility according to Eq. 2. If the value of E is too high, on the other hand, no player is ever awarded with an external link, and the two populations remain disconnected (independent of one another). Intermediate values of E, however, promise interesting results as the evolutionary processes on each individual network become interdependent through the : Intermediate values of the utility threshold E are able to sustain widespread cooperation in the evolutionary prisoner's dilemma game, even at temptations to defect where the evolution on an isolated graph would terminate in an absorbing D phase (see legend). However, as soon as a critical value E = E c is reached, the two populations become independent, and the value of ρ C drops to the level that is characteristic for an isolated network. Since here the interaction network for both populations is a square lattice where every player is connected to its four nearest neighbors, the critical value is E c = 4, which is the maximal payoff of a cooperator (if all its neighbors are also cooperators). We note, however, that this is accurate threshold is an exception, since in general the value of E c is somewhat lower than the maximal cooperator payoff, as it also depends on the typical size of cooperative clusters [which in turn depends on b (r in the public goods game)]. At E = 0, on the other hand, the two populations are completely interdependent (every player has a link to the corresponding player in the other network), and due to interdependent network reciprocity (Wang et al., 2013a), the level of cooperation is still significantly higher than on an isolated network (as obtained for E ≥ E c ).
time-varying addition and removal of the external links. We note that the selection of an external player from the other population is done randomly and is not influenced by its actual tag. If the linking would be tag-based, this might give rise to further nontrivial effects due to the establishment of bilateral connections, as it discussed recently in a related work by Fu et al. (Fu et al., 2012). While we wish to avoid this possibility within the scope of present study, it may constitute a worthy research challenge to be addressed in the future.

Results
For easier comparison, we first present results for the most traditional setup, using as the interaction network for both populations the square lattice and the weak prisoner's dilemma as the governing evolutionary game. Results presented in Fig. 1 illustrate the threshold-dependence of the cooperation level, as recorded in both populations together. It can be observed that there exist an intermediate value of the utility threshold E, at which the evolution of cooperation is optimally promoted. However, while the rise of ρ C is steady as E increases, the drop is sudden, and it occurs at a critical values of the threshold (E = E c = 4), which is related to the maximal payoff attainable by a cooperator. In the depicted case the critical value is actually identical to the maximal cooperator payoff, but as we will show in what follows, this is an exception rather than the rule. The E = 0 threshold renders all players worthy of the re- , as obtained on a regular random graph where every player has degree k = 8. The bottom layer depicts the fraction of rewarded players f E whose utility is above the threshold E. Note that there is a strong correlation between the dependence of ρ C and f E . Importantly, here the critical value of E = E c depends somewhat on b (because the values of b determines the typical size of cooperative clusters), and it is also below the maximally attainable payoff of a cooperator (if all its neighbors would also be cooperators). This indicates that the E c value does not necessarily imply a strict prohibition of external links. Cooperators that are located deep within large cooperative clusters may still be eligible for the reward, but the cooperators at the edge are vulnerable, which will eventually lead to the erosion of cooperative clusters and the disappearance of external links even at E c values that are smaller than the maximal cooperator payoff. And since larger values of b give rise to smaller cooperative clusters, the value of E c decreases as the temptation to defect increases.
ward [an external link to the corresponding player in the other network and with it related higher utility (see Eq. 2)], and thus introduces full interdependence between the two populations. The evolution of cooperation then proceeds with the support of interdependent network reciprocity (Wang et al., 2013a). On the other hand, if E ≥ E c , players are in general unable to reach the threshold, which leaves the two populations fully independent. Traditional network reciprocity (Nowak and May, 1992) is then the sole mechanism supporting the survival of cooperators, and it can be observed that it is less effective than interdependent network reciprocity (the E = 0 case). Just slightly below the critical value, however, cooperators fare best, and in what follows we will present results in favor of the robustness of this observation, as well as results that explain it. We first test the robustness by replacing the square lattice interaction topology with the random regular graph where every Here results for the public goods game are presented, as obtained on a square lattice where every player is involved in five groups of size G = 5. As in Fig. 2, the critical value of the threshold E = E c depends on the multiplication factor r (see legend), and it is lower than the maximally attainable payoff of a cooperator in five groups where all other players would also cooperate. As in the prisoner's dilemma game, this is related to the decreasing size of cooperative clusters as r decreases, and to the vulnerability of cooperators that are positioned along the edges of cooperative domains (see also Fig. 2).
player has eight neighbors. Results presented in Fig. 2(a) are qualitatively identical to those presented in Fig. 1. The dependence of ρ C on E is somewhat smoother, and due to the larger number of neighbors (on the square lattice players have only four neighbors each), the critical threshold value E c could be approximately two times as large as on the square lattice. But not quite. Indeed, it is lower than the maximally attainable cooperator payoff (which in this case would be eight), and it also decreases as the temptation to defect b increases. These subtle features, which remain hidden in Fig. 1, provide vital insights that help to understand why and how the evolution of cooperation is promoted. In particular, the fact that the value of E c is lower than the maximal payoff of a cooperator indicates that the critical threshold value does not necessarily involves the prohibition of rewarding. Cooperators deep in the bulk of a cooperative domain may qualify at any given time, but those along the interface are vulnerable because they are unable to reach a sufficiently high fitness to be rewarded. Defectors are therefore able to invade, which eventually leads to the disintegration of the clusters. In the stationary state even the aforementioned "central" cooperators will fall victim to the high utility threshold, and they will not be awarded an external link, and thus also will not be able to resist the invasion of defectors. To support this argument and to demonstrate the key role of the interdependence between the two populations, we present in Fig. 2(b) the fraction of players that have an external link (are rewarded) in dependence on the threshold E. It can be observed that there is a direct correlation between the fraction of rewarded players and the fraction of cooperators in the population. Going further in the exploration of robustness of our findings, we return to the square lattice as the interaction network, but we replace the pairwise driven prisoner's dilemma game with the group-driven public goods game (Santos et al., 2008;  Only if the distinguished players are rare (which occurs at sufficiently high values of E), but at the same time are also still able to percolate (which requires E < E c ), will cooperative behavior be optimally promoted. Left panel shows the results obtained with the prisoner's dilemma game on a regular random graph where every player has degree k = 8, and using the temptation to defect b = 1.1. Right panel depicts the results of the public goods game on a square lattice using r/G = 0.76. We note that to plot ρ CE for E ≥ E c is meaningless, because no such players exist, as evidenced by the results presented in Fig. 2(b) for the prisoner's dilemma game. Perc et al., 2013). As Fig. 3 illustrates, in this case too the evolution of public cooperation is promoted, and essentially the same conclusions apply as outlined above for the results presented in Fig. 2. In agreement with the behavior we have observed for the prisoner's dilemma game, the harsher the social dilemma (in this case the smaller the multiplication factor r), the smaller the critical threshold value E = E c at which the two populations become fully independent and the cooperation level drops. Just like larger values of b in the prisoner's dilemma game decrease the typical size of compact cooperative clusters, so do decreasing values of r in the public goods game do the same. Both the increase of the temptation to defect and the decrease of the multiplication factor enhance the severity of the social dilemma. And because the cooperative clusters become smaller in size, their ability to contain cooperators that might be able reach close-to-optimal payoffs decreases, and so does the value of E c . To explain the observed behavior at the microscopic level, we measure the cooperation level specifically amongst those players who possess an external link because their utility is above the threshold value E. In Fig. 4, we plot this quantity (denoted by ρ CE ), and we also show the cooperation level in both populations for comparison. If the value of E is small, then there is no significant difference between ρ CE and ρ E . If we increase the threshold, then two mechanisms will emerge that support each other's impact. On the one hand, by increasing the value of E, heterogeneity is introduced to both populations because not all players will fulfill the condition to be rewarded with an external link. Such heterogeneity will enhance the impact of network reciprocity because of the long-term advantage of co- E=5.9 E=6.0 MCS Figure 5: Inserting a small cooperative domain, consisting of 780 players, into a homogeneous populations of 4 · 10 4 defectors reveals the spreading of distinguished (rewarded) players, which is due to the self-organization of fitness and reward. Depicted is the time evolution of the fraction of rewarded players f E that satisfy U x ≥ E (left) and the overall cooperator density ρ C (right) versus the number of Monte Carlo steps for b = 1.1, E = 5.9 (solid blue line) and E = 6.0 (dashed red line), as obtained on a regular random graph where every player has degree k = 8. If the threshold is higher than the critical value E c (E = 6.0 in this case), a negligible minority of players is rewarded, but they are unable to percolate. Accordingly, cooperators are forced to rely solely on traditional network reciprocity, and their density is accordingly low. Just a tiny drop in E below E c (E = 5.9 in this case) enables rewarded players to percolate and thus to support each other, and therefore the stationary fraction of cooperators rises significantly.
operative leaders (the latter was identified earliest with the discovery that scale-free networks provide a unifying framework for the evolution of cooperation (Santos and Pacheco, 2005)).
The distinguished cooperators will be followed by those who fail to reach the rewarding threshold, which will in turn increase ρ C . On the other hand, the relatively rare rewarded players need to percolate, i.e., they still have to be sufficiently common for their influence in the population to overlap. If their influence does not overlap, in the absence of percolation, the advantage of cooperative behavior cannot manifest, which will reduce the cooperation level. Noteworthy, this behavior is related to the optimal density of players on a network, which we have recently explored in isolated structured populations (Wang et al., 2012d,c). Finally, to provide direct evidence that the self-organized spreading of rewarded players will elevate cooperation, we devise a specific experiment, wherein, starting from a full D state, we insert a small cooperator domain into both graphs which are not correlated to each other. To illustrate the robustness of the leading mechanism we use random regular graphs, where the cooperative domain is constructed by starting from a single cooperative player and subsequently denoting all its neighbors and the neighbors of neighbors, and so forth, as cooperators, until the initial fraction of cooperators in the whole population reaches 2%. By using two different threshold values, we monitor how the fraction of rewarded players, and how the general cooperation level, evolve. To emphasize the delicate role of the threshold, we have chosen two E values that are slightly below and above the critical utility E c for the applied b value. As Fig. 5 illustrates, players cannot become distinguished if the demand for the reward is too high, and consequently the cooperation can reach a level which is attainable solely by traditional network reciprocity. If we lower the threshold only slightly, then more players become eligible for the reward and can build an external link to the corresponding player in the other network, and the latter will in turn support the higher utility in future trails. If we compare the applied values of E in Fig. 5, it becomes clear than just a tiny change can yield a significant difference in f E (the fraction of players that are rewarded). Because the rare, yet still sufficiently common, rewarded players percolate, they can support each other through the overlap of extensive cooperative clusters that surround them, which in turn significantly elevates the cooperation level in the whole system.

Discussion
The evolution of cooperation among unrelated individuals is a long-standing problem which attracts research from a wide range fields, including biology and the social sciences (Mesterton-Gibbons and Dugatkin, 1992;Mesterton-Gibbons, 2001;Nowak, 2006;Sigmund, 2010). We have studied the evolution of cooperation in two initially independent structured populations, where players were rewarded with an external link to a player in the other network if their current utility reached or exceeded a given threshold. Being rewarded with an external link implied the acquisition of part of the corresponding player's payoff, and thus increasing one's own evolutionary potential in the next round of the game. Importantly, we have considered rewards being representative only for the current evolutionary success. Thus, as soon as the utility of a player dropped below the utility threshold, the external link was removed.
It was shown that this simple but intuitive coevolutionary rule introduces a time-varying interdependence between the two populations, which provides a dynamical coupling between them. As a result of coevolution between strategy dependent fitness and external links a threshold-dependent interdependency will emerge and stabilize. We have also shown that it may significantly promote the evolution of cooperation if the applied utility threshold is neither too small nor to large. If it is too small, the two populations are fully interdependent, and the benefits for the evolution of cooperation are similar to those warranted by interdependent network reciprocity (Wang et al., 2013a). If, on the other hand, the utility threshold is too high, the two populations are fully independent, and cooperators may take advantage only of traditional network reciprocity (Nowak and May, 1992). For intermediate values of the utility threshold, and especially for values close but lower than a critical threshold, cooperators can take advantage of percolating distinguished players that act as strong catalysts of cooperative behavior by offering a cooperation supporting mechanism to evolve at a higher level. Fine-tuning the utility threshold has the important role of adjusting the density of rewarded players just right. If the rewarded players are too many, the heterogeneity in the population vanishes, and so does the additional support for the evolution of cooperation. If the rewarded players are too few, they are unable to percolate. Indeed, the rewarded players must be rare, but at the same time frequent enough to percolate for the optimal conditions to emerge. The percolation is related to the optimal density of players on a network, which has recently been explored in detail on isolated populations for pairwise social dilemmas and the public goods game (Wang et al., 2012d).
We have also established that the value of the critical threshold is related to the maximal payoff that is attainable by a cooperator, although only in special cases will it be exactly equal to this value (see Fig. 1). In general, the critical utility threshold is lower that the maximal cooperator payoff because cooperators that are located at the interfaces of cooperative domains can never reach the highest payoffs. At such high threshold values (equal to the maximal cooperator payoff), the interfaces are therefore vulnerable to the invasion by defectors, which eventually leads to the dissolution of cooperative clusters. The value of the critical utility threshold also decreases with the increasing severity of the social dilemma (increasing value of b in the prisoner's dilemma game, or the decreasing value of the multiplication factor r in the public goods game), which is due to the fact that at harsher conditions the cooperative clusters become smaller. Their potential to harbor cooperators that might reach a close-to-optimal payoff thus decrease as well, and accordingly so does the critical utility threshold that still warrants percolation of those that are rewarded with an external link.
All the presented results are independent of the structure of the applied interaction networks and the studied social dilemma games, and thus appear to have a high degree of universality. We hope that the demonstration of the spontaneous emergence of optimal interdependence by means of a simple coevolutionary rule based on the self-organization of reward and fitness will attract further research on the evolution of cooperation on interdependent networks (Wang et al., 2012b;Gómez-Gardeñes et al., 2012b,a;Wang et al., 2012aWang et al., , 2013aJiang and Perc, 2013;Szolnoki and Perc, 2013b). The consideration of interdependence appears to be particularly relevant for human societies (Apicella et al., 2012;Rand and Nowak, 2013;Helbing, 2013), where individuals are typically members in many different networks, and those networks might play different roles in the evolutionary process. Multilayer networks are already in the focus of attention as the most apt description of a networked society (Kivelä et al., 2013), and we hope that our study will help contribute to the continued vibrancy of this research avenue.