Amos Korman
email: amos.korman@irif.fr

Robin Vacus
email: rvacus@irif.fr

On the Role of Hypocrisy in Escaping the Tragedy of the Commons

We study the emergence of cooperation in large spatial public goods games. Without employing severe social-pressure against "defectors", or alternatively, significantly rewarding "cooperators", theoretical models typically predict a system collapse in a way that is reminiscent of the "tragedy-of-the-commons" metaphor. Drawing on a dynamic network model, this paper demonstrates how cooperation can emerge when the social-pressure is mild. This is achieved with the aid of an additional behavior called "hypocrisy", which appears to be cooperative from the external observer's perspective but in fact hardly contributes to the social-welfare. Our model assumes that social-pressure is induced over both defectors and hypocritical players, though the extent of which may differ. Our main result indicates that the emergence of cooperation highly depends on the extent of social-pressure applied against hypocritical players. Setting it to be at some intermediate range below the one employed against defectors allows a system composed almost exclusively of defectors to transform into a fully cooperative one quickly. Conversely, when the social-pressure against hypocritical players is either too low or too high, the system remains locked in a degenerate configuration.

Introduction

The "tragedy-of-the-commons" metaphor, popularized by Hardin in 1968 [START_REF] Hardin | The tragedy of the commons[END_REF], aims to capture situations in public goods systems where self-interested individuals behave contrary to the common good by depleting or spoiling the shared resource. In the 21st century, this metaphor finds relevance in several of our global environmental challenges [START_REF] Houghton | Climate change 2001: The scientific basis[END_REF][START_REF] Ostrom | Governing the commons: The evolution of institutions for collective action[END_REF], where the shared resource can be considered, depending on the context, as an aspect of the ecosystem. For example, excessive beef consumption by a substantial number of individuals induces vast livestock production that degrades air and water quality and causes a considerable increase in greenhouse gas emissions [START_REF] Eshel | Land, irrigation water, greenhouse gas, and reactive nitrogen burdens of meat, eggs, and dairy production in the united states[END_REF]. Conversely, our environment would significantly benefit if a large portion of individuals in the population would self-restraint the amount of beef they consume. Therefore, improving our understanding of the emergence of cooperation in public goods systems goes beyond the purely theoretical interest and may prove to be of practical importance.

Theoretical studies on the emergence of cooperation typically assume that players act according to few stereotyped behaviors, the most common being "defector", and "cooperator" [START_REF] Ohtsuki | A simple rule for the evolution of cooperation on graphs and social networks[END_REF][START_REF] Nowak | Five rules for the evolution of cooperation[END_REF][START_REF] Peter D Taylor | Evolution of cooperation in a finite homogeneous graph[END_REF][START_REF] Allen | Evolutionary games on isothermal graphs[END_REF][START_REF] Allen | Evolutionary dynamics on any population structure[END_REF]. A cooperator pays an energetic cost to produce a benefit b for others, whereas a defector does not contribute anything but also does not pay any energetic cost. In recent years, significant attention has been devoted to study the impact of the populations' structure on the emergence of cooperation [START_REF] Perc | Evolutionary dynamics of group interactions on structured populations: a review[END_REF][START_REF] Ohtsuki | A simple rule for the evolution of cooperation on graphs and social networks[END_REF][START_REF] Allen | Games on graphs[END_REF][START_REF] Débarre | Social evolution in structured populations[END_REF]. These works assume that players are organized over a fixed network, with the vertices representing the players and the edges representing reciprocal relations between neighbors. Naturally, the dynamics of the system strongly depend on the mutual relations between neighboring players.

For example, several of the works on cooperation in structured populations assume that the benefit b produced by a cooperative player is shared equally by its neighbors. For such a model, Ohtsuki et al. showed that cooperation emerges when the ratio between the benefit per neighbor and the cost of producing it exceeds a certain threshold [START_REF] Ohtsuki | A simple rule for the evolution of cooperation on graphs and social networks[END_REF]. However, large public goods games, especially those on the scale that affects the environment, exhibit a very different framework of reciprocity [START_REF] Cinyabuguma | Can second-order punishment deter perverse punishment?[END_REF][START_REF] Milinski | Reputation helps solve the 'tragedy of the commons[END_REF][START_REF] David G Rand | Positive interactions promote public cooperation[END_REF][START_REF] Rege | The impact of social approval and framing on cooperation in public good situations[END_REF][START_REF] Yamagishi | The provision of a sanctioning system as a public good[END_REF]. Rather than being shared by immediate neighbors, the benefit b is shared by all players, practically making the marginal percapita return gain (MPCR) negligible compared to the cost of cooperating. This violates the condition for the evolution of cooperation based on reciprocity [START_REF] Ohtsuki | A simple rule for the evolution of cooperation on graphs and social networks[END_REF][START_REF] Nowak | Five rules for the evolution of cooperation[END_REF][START_REF] Peter D Taylor | Evolution of cooperation in a finite homogeneous graph[END_REF][START_REF] Allen | Evolutionary games on isothermal graphs[END_REF][START_REF] Allen | Evolutionary dynamics on any population structure[END_REF] suggesting that cooperation in large public goods games might be difficult to achieve without considering other factors, such as rewards or punishments.

It is well-known that global cooperation can emerge when players severely punish their neighboring defectors (or, alternatively, significantly reward their cooperating neighbors) [START_REF] Sigmund | Reward and punishment[END_REF][START_REF] Nowak | Five rules for the evolution of cooperation[END_REF][START_REF] Daniel J Rankin | The tragedy of the commons in evolutionary biology[END_REF][START_REF] Axelrod | The evolution of cooperation[END_REF][START_REF] Milinski | Reputation helps solve the 'tragedy of the commons[END_REF][START_REF] Fehr | Cooperation and punishment in public goods experiments[END_REF][START_REF] Chen | First carrot, then stick: how the adaptive hybridization of incentives promotes cooperation[END_REF]. However, inducing severe punishments on others may be costly, and hence reaching high levels of social-pressure is by itself a non-trivial problem, often referred to in the literature as the second-order free riders problem [START_REF] Boyd | Punishment allows the evolution of cooperation (or anything else) in sizable groups[END_REF][START_REF] Boyd | The evolution of altruistic punishment[END_REF][START_REF] Tonsi | Selfishness as second-order altruism[END_REF][START_REF] Helbing | Evolutionary establishment of moral and double moral standards through spatial interactions[END_REF][START_REF] Helbing | Punish, but not too hard: how costly punishment spreads in the spatial public goods game[END_REF][START_REF] Panchanathan | Indirect reciprocity can stabilize cooperation without the second-order free rider problem[END_REF]. A crucial parameter in the second-order problem is the cost of punishing, which may be correlated to the extent of punishment [START_REF] Rockenbach | The efficient interaction of indirect reciprocity and costly punishment[END_REF]. Clearly, when the cost exceeds a certain threshold, people would avoid punishing non-cooperators. However, when the cost is low, other factors, such as reputation considerations, can subsume the cost, ultimately making punishing beneficial [START_REF] Jordan | Third-party punishment as a costly signal of trustworthiness[END_REF][START_REF] Wedekind | Cooperation through image scoring in humans[END_REF][START_REF] Zahavi | Altruism as a handicap: the limitations of kin selection and reciprocity[END_REF]. It is therefore of interest to study the emergence of cooperation in the presence of moderate punishments or mild social-pressure.

Specifically, we are interested in a regime of social-pressure that is high enough to maintain an already cooperative system, but is insufficient to transform a system that initially includes a large number of defectors into a cooperative one. To illustrate this, let us consider the context of recycling and an imaginary person named Joe. When almost all of Joe's neighbors are recycling (i.e., cooperating), the social-pressure cost they induce on him can accumulate to overshadow the burden cost of recycling and incentivize him to also recycle. Conversely, when almost all of Joe's neighbors are not recycling (i.e., defecting), the burden of recycling may exceed the overall social-pressure, effectively driving Joe to defect. This raises a natural question: How can a system that utilizes mild social-pressure escape the tragedy-of-the-commons when it is initially composed mostly of defectors?

The aforementioned recycling abstraction includes two extreme behaviors: defection and cooperation. Another type of generic behavior is hypocrisy [START_REF] Robert L Trivers | The evolution of reciprocal altruism[END_REF][START_REF] Centola | The emperor's dilemma: A computational model of self-enforcing norms[END_REF][START_REF] Douglas D Heckathorn | Collective action and the second-order free-rider problem[END_REF][START_REF] Douglas D Heckathorn | The dynamics and dilemmas of collective action[END_REF][START_REF] Helbing | Evolutionary establishment of moral and double moral standards through spatial interactions[END_REF][START_REF] Tonsi | Selfishness as second-order altruism[END_REF], which was also experimentally studied in [START_REF] Falk | Driving forces behind informal sanctions[END_REF][START_REF] Shinada | False friends are worse than bitter enemies:"altruistic" punishment of in-group members[END_REF]. In our interpretation, a hypocritical player pretends to be cooperative in order to reduce the social-pressure that it might experience as a defector, and, at the same time, avoids the high energetic cost incurred by a cooperator. To pretend to be a cooperator, a hypocritical player must invest a small amount of energy in contributing to the social welfare, as well as mimic the behavior of cooperators towards their peers. This means that such players, similarly to cooperators, also induce mild social-pressure. In other words, and in contrast to disguising players as in [START_REF] Wang | Evolutionary dynamics of cooperation in the public goods game with individual disguise and peer punishment[END_REF], hypocritical players actively "demand" cooperation from others, as part of their strategy to hide their low investment in the social-welfare.

It was previously suggested that hypocritical behavior can incentivize global cooperation [START_REF] Helbing | Evolutionary establishment of moral and double moral standards through spatial interactions[END_REF][START_REF] Helbing | Punish, but not too hard: how costly punishment spreads in the spatial public goods game[END_REF]. However, in these works, similarly to many other papers on the emergence or evolution of cooperation based on reciprocity [START_REF] Ohtsuki | A simple rule for the evolution of cooperation on graphs and social networks[END_REF][START_REF] Nowak | Five rules for the evolution of cooperation[END_REF][START_REF] Peter D Taylor | Evolution of cooperation in a finite homogeneous graph[END_REF][START_REF] Allen | Evolutionary games on isothermal graphs[END_REF][START_REF] Allen | Evolutionary dynamics on any population structure[END_REF], the dynamics heavily relies on the assumption that players gain substantially from the presence of nearby cooperators. As mentioned, this assumption is hardly justifiable in large-scale public goods scenarios such as the ones we consider.

Results

We consider public goods games played iteratively over a fixed connected network. The vertices of the network represent the players and the edges represent neighboring connections [START_REF] Perc | Evolutionary dynamics of group interactions on structured populations: a review[END_REF][START_REF] Ohtsuki | A simple rule for the evolution of cooperation on graphs and social networks[END_REF][START_REF] Allen | Games on graphs[END_REF][START_REF] Débarre | Social evolution in structured populations[END_REF]. The dynamics evolve in discrete rounds. In each round, each player chooses a behavior that minimizes its cost, where the player's cost is affected by its own behavior and the behaviors of its neighbors.

Our main model includes three behavior types, namely, defection, hypocrisy, and cooperation, in which those who hardly contribute to the social welfare, i.e., defector and hypocritical players, face the risk of being caught and punished by their neighbors who are non-defectors. The level of risk together with the extent of punishment is captured by a notion that we call "social-pressure". The main result is that adjusting the level of social-pressure employed against hypocritical players compared to the one employed against defectors can have a dramatic impact on the dynamics of the system. Specifically, letting the former level of social-pressure be within a certain range below the latter level, allows the system to quickly transform from being composed almost exclusively of defectors to being fully cooperative. Conversely, setting the level to be either too low or too high locks the system in a degenerate configuration.

As mentioned, our main model assumes that non-defectors induce mild social-pressure on the defectors among their neighbors. This implicitly assumes that inducing the corresponding social-pressure is beneficial (e.g., allows for a social-upgrade), although other explanations have also been proposed [START_REF] Fehr | Cooperation and punishment in public goods experiments[END_REF]. To remove this implicit assumption we also consider a generalized model, called the two-order model, which includes costly punishments. Consistent with previous work on the second-order problem, e.g., [START_REF] Boyd | Punishment allows the evolution of cooperation (or anything else) in sizable groups[END_REF][START_REF] Tonsi | Selfishness as second-order altruism[END_REF][START_REF] James | Altruistic punishment and the origin of cooperation[END_REF][START_REF] Douglas D Heckathorn | The dynamics and dilemmas of collective action[END_REF][START_REF] Helbing | Evolutionary establishment of moral and double moral standards through spatial interactions[END_REF][START_REF] Helbing | Punish, but not too hard: how costly punishment spreads in the spatial public goods game[END_REF], this model distinguishes between first-order cooperation, that corresponds to actions that directly contribute to the social welfare, and second-order cooperation, that corresponds to applying (costly) social-pressure, or punishments, on others. As in the main model, the level of punishment employed against first-order defectors may differ from that employed against second-order defectors. We identify a simple criteria for the emergence of cooperation: For networks with minimal degree ∆, cooperation emerges when two conditions hold. The first condition states that the cost α 2 of employing punishments against second-order defectors should be smaller than the corresponding punishment β 2 itself, i.e., α 2 < β 2 . The second condition states that the cost α 1 of employing punishments against first-order defectors should be smaller than the corresponding punishment β 1 times the minimal number of neighbors, i.e., α 1 < β 1 • ∆. The second condition is also a necessary condition for the emergence of cooperation in the two-order model.

The main model

The model considers two extreme behaviors, namely, cooperation (c) and defection (d), and an additional intermediate behavior, called hypocrisy (h). The system starts in a configuration in which almost all players, e.g., 99%, are defectors (see Methods). Execution proceeds in discrete rounds. The cost of a player depends on its own behavior and on the behavior of its neighbors. All costs are evaluated at the beginning of each round, and then, before the next round starts, each player chooses a behavior that minimizes its cost (breaking ties randomly), given the current behavior of its neighbors. In other words, we assume that players greedily choose their best behavior, given the current configuration. In our simulations, we also consider a relaxed version, where players choose the best behavior with high probability, and with small probability choose an arbitrary behavior. In contrast to many previous works on cooperation in networks [START_REF] Ohtsuki | A simple rule for the evolution of cooperation on graphs and social networks[END_REF][START_REF] Nowak | Five rules for the evolution of cooperation[END_REF][START_REF] Peter D Taylor | Evolution of cooperation in a finite homogeneous graph[END_REF][START_REF] Allen | Evolutionary games on isothermal graphs[END_REF][START_REF] Allen | Evolutionary dynamics on any population structure[END_REF], we assume that benefits from altruistic acts are negligible (i.e., the MPCR is zero), so that a player does not gain anything when others cooperate.

The cost of a player u with a behavior type i ∈ {d, h, c} is composed of two components: the energetic cost E i associated with the contribution to the social welfare, and the social-pressure cost S i (u) it faces, that is:

C i (u) = E i + S i (u).
We assume that the energetic cost of a defector is 0, and the energetic cost of a cooperator is 1, where the value of 1 is chosen for normalization:

E d = 0 and E c = 1.
A hypocritical player produces the minimal social welfare required to pretend to be cooperative. Hence, we assume that 0

< E h < 1,
thinking of E h as closer to 0 than to 1.

As mentioned above, we focus on relatively mild social-pressure induced by cooperative players, aiming to improve their social status. Since hypocritical players aim to appear similar to cooperators from the perspective of an external observer, we assume that they too induce social-pressure on their neighbors. Defectors, on the other hand, do not induce any social-pressure since such an enhancement of the social status is not justified for them. In principle, cooperators and hypocritical players might induce different levels of social-pressure, yet, for the sake of simplicity, we assume that they induce the same extent of socialpressure. This assumption is further justified by the fact that a player u cannot distinguish its hypocritical neighbors from its cooperative neighbors, hence, u's calculation of the social-pressure is evaluated assuming all of its non-defector neighbors are cooperators.

Formally, we assume that the possible social-upgrade gain associated with cooperators or hypocritical players as a result of applying social-pressure is already taken into account when calculating the energetic costs E c and E h . Since we assume that this gain is small, it hardly perturbs the cost, keeping the energy consumption as the dominant component.

Implicitly, we think of the social-pressure cost incurred by a player u as the product of two factors: (1) the risk of being caught, which is assumed to be proportional to the number of u's neighbors inducing social-pressure, and (2) a fixed penalty paid when caught, which depends on u's behavior. The product of the risk and penalty represents the expected punishment in the next round, if behaviors remain the same.

Cooperators are assumed to pay zero penalty, and are hence effectively immune to social-pressure:

S c (u) = 0.
Conversely, the social-pressure induced over defectors and hypocritical players is non-zero. For a given round, let ∆ d(u) denote the number of neighbors of u which are non-defectors at that round. The social-pressure cost induced over a defector, and respectively, a hypocritical, player u is:

S d (u) = ρ d • ∆ d(u), respectively, S h (u) = ρ h • ∆ d(u),
where ρ d > 0, respectively ρ h > 0, represents the social-pressure induced over a defector, respectively a hypocritical, from one neighboring non-defector. Note that when comparing the social-pressure incurred by defectors versus hypocritical players, both the risk of being caught and the extent of punishment are expected to be different. Indeed, since hypocritical players pretend to be cooperators, their risk of being caught is expected to be lower than that of defectors. Moreover, after being caught, the respected punishment of a defector might be different than that of a hypocritical player, depending on the social norms. Altogether, here we focus on the regime where ρ h < ρ d , since otherwise, becoming a defector is always more beneficial than becoming a hypocritical.

To sum up, at a given round, the total cost incurred by a player u is:

C(u) =        1 if u is a cooperator, ρ d • ∆ d(u) if u is a defector, E h + ρ h • ∆ d(u) if u is hypocritical.
Before stating our main result, we recall few standard definitions in graph-theory [START_REF] Diestel | Graph theory 3rd ed[END_REF]. The diameter of a network G, denoted diam(G), is the maximal distance between any pair of players (see Methods). A network is ∆-regular, if every player has precisely ∆ neighbors. Theorem 1 below assumes that the underlying network is ∆-regular. However, this theorem can be generalized to arbitrary networks with minimal degree ∆ (see SI, Theorem 6).

Theorem 1. Consider a ∆-regular network G with n players. Assume that

(1 -E h )/∆ < ρ h < ρ d -E h . (1)
Then, with probability at least 1 -1 c n , for some constant c > 1, in at most 3 • diam(G) + 1 rounds, the system will be in a configuration in which all players are cooperative, and will remain in this configuration forever.

The formal proof of Theorem 1 appears in the SI, Section B. Intuitively, the main idea behind it is as follows. When the extent of social-pressure against hypocritical players is moderate, that is, when ρ h satisfies Eq. ( 1), the transition process can be divided into two stages. At the first stage, since the punishments of hypocritical players are sufficiently lower than those of defectors, specifically, ρ h < ρ d -E h , or equivalently ρ h +E h < ρ d , the presence of at least one neighboring non-defector u makes a hypocritical player pay less than a defector. In this case, u's neighbors would become non-defectors at the next round (Figure 1a). Although this does not necessarily imply that u itself remains a non-defector in the next round, it is nevertheless possible to show that the proportion of hypocritical players gradually increases on the expense of defectors. Note that at this point, the social welfare may still remain low, since hypocritical players hardly contribute to it. However, the abundance of non-defectors increases the overall social-pressure in the system. In particular, since the social-pressure on hypocritical players is also not too mild, specifically (1 -E h )/∆ < ρ h , or equivalently 1 < ρ h ∆ + E h , the presence of many neighboring non-defectors can magnify it up to the point that the total cost incurred by a hypocritical player surpasses the energetic cost of being a cooperator (Figure 1b). At this second stage, cooperators prevail over both defectors and hypocritical players, and so the system converges to a cooperative configuration.

Conversely, severely punishing hypocritical players diminishes the prevalence of such players, preventing the system from escaping the initial degenerate configuration. Contrariwise, incurring too mild socialpressure towards hypocritical players would prevent the second stage of the dynamics. In particular, if

ρ h < (1 -E h )/∆, or equivalently, if E h + ρ h ∆ < 1,
then a player would always prefer to be hypocritical over being cooperative (even when all its neighbors induce social-pressure). In this case, the system would remain degenerative since the population would consist of a combination of defectors and hypocritical players.

To illustrate the dynamics we conducted simulations over several types of networks. Figure 2 shows how the population evolves over time, when considering a grid network (Figure 2a) and a random 10-regular network (Figure 2b). The chosen parameters satisfy the assumption in Eq. ( 1). In both dynamics, the role of hypocritical behavior as a transitory state, essential to achieving cooperation, is well illustrated by the initial peak of hypocritical players, preceding the rise of cooperative players. Moreover, if hypocritical behavior is disabled (see Methods), then the system is unable to escape the defective state (insets).

Figure 3 depicts the steady-state configuration, when hypocritical players experience different levels of energetic cost (E h ) and social-pressure (ρ h ). This is illustrated on a grid network (Figure 3a), random 10-regular networks (Figure 3b), Erdös-Rényi networks with average degree 10 (Figure 3c), and a Barabási-Albert networks with median degree 7 (Figure 3d). The figures indicate that for small values of ρ h and E h , hypocritical behavior is, unsurprisingly, dominant: punishments deter defectors, but are insufficient to incentivize cooperation. For moderate values of E h , this phenomenon changes when ρ h enters the range specified in Theorem 1. Then, when ρ h increases further, the system remain defective. The correspondence to Theorem 1 is striking in Figures 3a, 3b, and3c, whereas it is slightly more moderate in Figure 3d. Recall that Theorem 1 considers ∆-regular networks, and therefore directly applies to grid networks and random regular networks, as simulated in Figures 3a and3b, respectively. Moreover, although a typical Erdös-Rényi network is not regular, the degrees of its vertices are relatively concentrated around the average degree, justifying the similarity between the results in Figures 3b and3c. For Barabási-Albert networks (Figure 3d) the average degree is not a good representative for the typical degree since these networks are power-law. Hence, we drew the line corresponding to ρ h = (1 -E h )/∆, taking ∆ to be the median degree, which was in this case roughly 7. Even though many vertices in the network have a smaller degree than the median degree, high levels of cooperation emerge in the region specified by Theorem 1.

Consistent with Theorem 1, Figure 3 considers the case that players behave in a fully greedy fashion 1). The insets show the population's evolution when hypocritical behavior is not available to the agents. See Methods for more details.

while having perfect knowledge regarding their costs. To check if this assumption is impactful, we also simulated a more noisy variant of our model, in which each player chooses the behavior that minimizes its cost with probability 0.95, and otherwise chooses a behavior uniformly at random. This relaxed model yields more mixed populations at steady-state, as indicated in Figure 4a regarding a grid network and in Figure 4b regarding random 10-regular networks. As another relaxation, we also simulated the case that the initial configuration is not overwhelmingly composed of defectors. Specifically, in Figures 4c (grid network) and 4d (random 10-regular networks) we assumed that initially 80% of the players are defectors, instead of 99% as used in Figure 3. Not surprisingly, this relaxation enhances cooperation. Indeed, comparing Figure 4c to Figure 3a, and comparing Figure 4d to Figure 3b, we observe that for each of these networks, the corresponding regime of cooperation includes the one that emerges when there are more defectors initially.

Overall, in all the relax versions in Figure 4 we see that the necessity of the condition ρ h > (1 -E h )/∆ to the emergence of cooperation is still respected. However, the other condition mentioned in Theorem 1, namely, ρ h < ρ d -E h appears to be more sensitive to randomness. Indeed, and especially for the cases of random ∆-regular networks, cooperation emerges also for larger values of ρ h .

A Generalized Model with Costly Punishments

We next describe a different, more general model, termed the two-order model, that includes costly punishments. We then show how the second-order problem is solved in this model for a certain regime of parameters.

As the name suggests, the two-order model includes two levels of cooperation. Players engaged in firstorder cooperation incur an energetic cost to produce a benefit for other individuals, whereas players engaged in second-order cooperation induce costly punishments on other individuals whenever they fail to cooperate (on any order). The two orders of cooperation are not mutually exclusive, that is, a player can cooperate (or not cooperate) on one of the two orders or on both.

Similarly to the main model, players are organized over a connected network G. A behavior for Player u is defined as a couple of indicator functions (χ 1 (u), χ 2 (u)), with the convention that χ 1 (u) = 1 if u cooperates on the first-order (and 0 if it defects), and χ 2 (u) = 1 if u cooperates on the second-order (and 0 if it defects). The cost incurred by a player is divided into two components. We denote by α 1 > 0 the cost associated with first-order cooperation (this is analogues to the energetic cost in the main model), while α 2 > 0 refers to the cost of second-order cooperation, that is, the cost of incurring punishments. A player u such that χ 2 (u) = 1 induces a social-pressure cost on each of its neighbors, whenever these fail to cooperate, at any order. As in the main model, the extent of this social-pressure may differ depending on whether it is applied against first-order defectors or second-order defectors. Specifically, we denote by β 1 the social-pressure cost paid by a first-order defector, and by β 2 the social-pressure cost paid by a second-order defector (fully defecting players pay both). Formally, denoting by ∆ 2 (u) the number of neighbors of u which are cooperating on the second-order, that is, ∆ 2 (u) = |{v is a neighbor of u, χ 2 (v) = 1}|, the total cost paid by u equals:

C(u) = χ 1 (u)α 1 + χ 2 (u)α 2 + (1 -χ 1 (u))∆ 2 (u)β 1 + (1 -χ 2 (u))∆ 2 (u)β 2 .
(

) 2
Let us name each of the four behaviors, and recap their cost:

• a cooperator (χ 1 (u) = 1, χ 2 (u) = 1) pays α 1 + α 2 ,
• a defector (χ

1 (u) = 0, χ 2 (u) = 0) pays ∆ 2 (u)(β 1 + β 2 ), • a hypocritical (χ 1 (u) = 0, χ 2 (u) = 1) pays α 2 + ∆ 2 (u)β 1 ,
• a private cooperator (χ

1 (u) = 1, χ 2 (u) = 0) pays α 1 + ∆ 2 (u)β 2 .
As in the main model, the system starts in a configuration in which almost all players, e.g., 99%, are defectors (see Methods). The execution proceeds in discrete synchronous rounds. The costs of each player are evaluated at the beginning of each round, and then, before the next round starts, each player chooses a behavior that minimizes its cost (breaking ties randomly), given the current behavior of its neighbors.

The theorem below assumes that the underlying network is ∆-regular. However, as in the case of Theorem 1, the theorem can be generalized to arbitrary networks with minimal degree ∆ (SI, Theorem 13).

Theorem 2. Consider a ∆-regular network G with n players undergoing the two-order model. Assume that the following two conditions hold.

• Condition (i) α 2 < β 2 , and

• Condition (ii) α 1 < ∆β 1 .
Then, with probability at least 1 -1 c n , for some constant c > 1, in at most 3 • diam(G) + 1 rounds, the system will be in a configuration in which all players are cooperative, and will remain in this configuration forever.

The formal proof of Theorem 2 appears in the SI, Section C. Intuitively, the proof starts by showing that for the regime of parameters satisfying Conditions (i) and (ii), after the first round, no player ever chooses to be a private cooperator. The proof proceeds by showing that for this regime of parameters, the dynamics of the two-order model can be translated to the dynamics of the main model for the regime of parameters satisfying Eq. 1. In other words, the proof of Theorem 2 is based on a reduction to Theorem 1.

Discussion

This paper proposes a simple idealized network model that demonstrates how cooperation can emerge, even when the MPCR is zero, and even when the extent of social-pressure is low. Our results highlight the possible social role that might be played by hypocritical behavior in escaping the tragedy-of-the-commons. The main finding is that setting the level of social-pressure towards this behavior to be at a specific intermediate range allows to quickly transform an almost completely defective system into a fully cooperative one. Our model, like any model, neglects many of the real-life complexity parameters. Nevertheless, the insight we discovered sheds new light on the possibility of emergent cooperation. In particular, our results suggest that those who wish to influence others in the context of environmental preservation should rethink their relation to their hypocritical acquaintants.

Methods

For two players u and v in G, let d G (u, v) denote the distance between u and v, that is, the number edges on the shortest path linking u to v in G. The maximal distance between any pair of players, i.e., the diameter,

is denoted by diam(G) = max u,v∈G d G (u, v).
The initial configuration is governed by a given fixed 0 < < 1, which is independent from the underlying network. In the main model, each player is initially set to be a defector with probability 1 -, a hypocritical with probability /2, and a cooperative with probability /2. Similarly, in the two-order model, each player is initially chosen to be a defector, with probability 1 -, and, otherwise, with probability it chooses one of the three remaining behaviors with equal probability, i.e., /3. To demonstrate the strength of the emergence of cooperation, we consider as very small; for example, in each of our simulations (except the ones corresponding to Figures 4c and4d), we took = 0.01, which means that initially, 99% of the population were defectors, 0.5% were hypocritical, and 0.5% were cooperators.

We simulated the dynamics of the main model using the C++ language. Figures were obtained using the Python library "Matplotlib". In Figures 3a,4a, 4c and 2a we used a 50 × 50, 4-regular, torus grid. In Figures 3b, 4b, 4d and2b, we used random 10-regular networks with 1000 vertices. To sample such a network, we gradually increased the number of edges, by pairing the vertices of degree less than 10 uniformly at random, until it became not possible anymore; then we discarded the few "left-overs" if necessary. As a consequence, the sampled networks have sometimes slightly less than 1000 vertices, but are always 10-regular by construction.

For Figure 3c, we constructed Erdös-Rényi networks with 1000 vertices, taking each edge with probability p = 0.01. For Figure 3d, we constructed Barabási-Albert networks with 1000 vertices using the parameter m = 5. To sample such a network, we started with an m-clique, and then added each new vertex by attaching it to m existing vertices chosen at random, with a probability proportional to their current degree.

When running the time-simulations on the grid in Figure 2a, we took E h = 0.1, ρ d = 0.45, and ρ h = 0.23. In Figure 2b, the time-simulation was executed on a single random 10-regular network, using the parameters E h = 0.1, ρ d = 0.22, and ρ h = 0.11. For both cases these parameters satisfy the constraints in Eq. ( 1). The insets show the evolution of the population when hypocritical behavior is disabled. This means that each player must choose between cooperation and defection only, and that in the initial configuration, each player is a defector with probability 1 -, and a cooperator with probability . The setting remains otherwise unchanged.

In both Figures 3 and4, the results of the simulations are presented for 150 values of E h and 150 values of ρ h , with E h ∈ [0, 1] and ρ h ∈ [0, ρ d ]. For each couple (E h , ρ h ), a pixel is drawn at the appropriate location, whose RGB color code corresponds to the proportions of defectors (red), cooperators (green), and hypocritical players (blue) in steady-state -that is, after T rounds. These proportions have been averaged over N repetitions, with each time a new starting configuration, and, a new network. For the grid, we set T = 20, N = 10, whereas for the other networks, we took T = 10, N = 100.

Figures 4a and4b were obtained similarly to Figures 3a and3b, respectively, except that players did not choose greedily their behaviors for the next round. Instead, at each round, each player chose a behavior that minimizes its cost (breaking ties randomly) with probability 0.95, and otherwise chose a behavior uniformly at random. Figures 4c and4d were obtained similarly to Figures 3a and3b, respectively, except that the initial proportion of non-defectors was 20% (instead of 1%), i.e., we took = 0.2 (instead of 0.01).

All the experiments mentioned in this paper were numerical simulations. Specifically, they do not involve any real participant.

• If s and j -i have the same parity, then 2k +1+s-(j -i) is odd. Moreover, 2k +1+s-(j -i) < 2k +1, so

(u i = v 1 , v 2 , . . . , v s , v s+1 = u j , u j+1 , . . . , u 2k+1 , u 1 , . . . , u i-1 )
is again an odd-length cycle shorter than C, which is a contradiction.

This concludes the proof of Claim 4.

Claim 5. For every i, j ∈ {1, . . . , 2k + 1}, there exist a shortest path P between u i and u j such that P contains only vertices of C -in other words,

d C (u i , u j ) = d G (u i , u j ).
Proof of Claim 5. We prove the claim by induction on d C (u i , u j ), the distance between u i and u j in C.

When d C (u i , u j ) = 1, (u i , u j
) is a path of length 1 between u i and u j containing only vertices of C. Next, let us assume that the claim holds for every pair of vertices whose distance in C is at most 1 ≤ d ≤ k. Consider i and j such that d C (u i , u j ) = d + 1. By Claim 4, we can find and a shortest path P between u i and u j such that P contains u . By the induction hypothesis, we can find shortest paths P 1 between u i and u , and P 2 between u and u j , such that P 1 and P 2 contain only vertices of C. By merging P 1 and P 2 , we obtain a shortest path between u i and u j containing only vertices of C, which establishes the induction step. This concludes the proof of Claim 5.

By Claim 5, k = d C (u 1 , u k+1 ) = d G (u 1 , u k+1 ) ≤ diam(G)
, where the last inequality is by the definition of diameter. Hence, 2k + 1 ≤ 2diam(G) + 1. This concludes the proof of Lemma 3.

B Proof of Theorem 1

The goal of this section is to prove Theorem 1. In fact, we prove the more general theorem below. Theorem 6. Consider a network G with n players and minimal degree ∆. Assume that the following conditions hold.

• Condition (i) E h + ρ h < ρ d , and

• Condition (ii) E h + ρ h • ∆ > 1.
Then, for some constant c > 1 (that depends only on and not on G) the following holds.

• If G is not bipartite then with probability at least 1 -1 c n , in at most 3 • diam(G) + 1 rounds, the system will be in a configuration in which all players are cooperative, and will remain in this configuration forever.

• If G is bipartite and ∆-regular then with probability at least 1 -1 c n , in at most diam(G) + 1 rounds, the system will be in a configuration in which all players are cooperative, and will remain in this configuration forever.

• If G is bipartite then with probability at least 1 -1 c ∆ , in at most diam(G) + 1 rounds, the system will be in a configuration in which all players are cooperative, and will remain in this configuration forever.

Before we prove Theorem 6 we note that in the third item, the probability bound of 1 -1 c ∆ is tight for bipartite graphs, up to replacing c with another constant. Indeed, consider the bipartite graph which is constructed by having ∆ players in U , each of which is connected to each of the remaining n -∆ players in V . Then, with probability 1 c ∆ , for some constant c, all players in U are defectors initially. In this case, it is possible to show that, regardless of the relationships between ρ d , ρ h and E h , but as long as being a defector is the best choice when all neighbors are defectors, the system keeps alternating forever, so that on even rounds all players in U are defectors, and on odd rounds all players in V are defectors.

Proof of Theorem 6. We start with defining Dt as the set of non-defector players at round t. The following lemma describes the propagation of the non-defector state in the network. It says that a player u is a non-defector at round t + 1 if and only if at least one of its neighbors v is a non-defector in round t. Note, however, that this does not imply that the neighbor v remains a non-defector in the next round as well.

Lemma 7. Under Condition (i), Dt+1 = N ( Dt ).

Proof. First, we prove that N ( Dt ) ⊆ Dt+1 . Let u ∈ N ( Dt ). By definition, there exists a neighbor v of u such that v is a non-defector at round t. We claim that for u, being a hypocritical in round t + 1 is strictly more beneficial than being a defector. Indeed, as a hypocritical it will pay E h + ρ h • ∆ d(u), and as a defector it will pay ρ d • ∆ d(u). Since v is non-defector then ∆ d(u) ≥ 1, and hence:

E h + ρ h • ∆ d(u) ≤ (E h + ρ h ) • ∆ d(u) < ρ d • ∆ d(u),
where we used Condition (i) in the last inequality. Therefore, the cost of u as a defector is strictly higher than its cost as a hypocritical. This implies that in the next round u will be either a hypocritical or a cooperative player, i.e., u ∈ Dt+1 .

To prove the other inclusion, Dt+1 ⊆ N ( Dt ), consider a player u / ∈ N ( Dt ), i.e., having only defectors as neighbors at round t, or in other words, at round t, we have ∆ d(u) = 0. If u chooses to be a defector at round t + 1, then it would pay ∆ d(u)ρ d = 0, which is less than what it would pay as a hypocritical (E h + ∆ d(u)ρ h = E h ) or cooperator [START_REF] Hardin | The tragedy of the commons[END_REF]. Hence, u / ∈ Dt+1 .

Lemma 8. Assume that Conditions (i) and (ii) hold, and assume that for some round t 0 all players are non-defectors. Then, at round t 0 + 1, all players will be cooperative, and will remain cooperative forever.

Proof. Assume that at round t 0 all players are non-defectors. By Lemma 7, we know that every player will remain non-defector for every round after t 0 . It therefore remains to show, that at the end of round t, for any t ≥ t 0 , being a cooperative is strictly more beneficial than being a hypocritical.

Observe that since each player has at least ∆ neighbors, and since all neighbors are non-defectors at round t, then for every player u, we have ∆ d(u) ≥ ∆ at round t. Therefore, being a hypocritical costs

E h + ρ h • ∆ d(u) ≥ E h + ρ h • ∆.
By Condition (ii), this quantity is strictly greater than 1, hence more than what a cooperative player would pay. It follows that, at the end of round t, being a cooperative is strictly more beneficial than being a hypocritical, implying that all players would be cooperators at round t + 1. This completes the proof of Lemma 8. Lemma 9. Assume that Conditions (i) and (ii) hold, and assume that for some round t 0 , we have Dt0 ∩ N ( Dt0 ) = ∅, that is, there are at least two neighboring non-defectors. Then in at most diam(G) + 1 rounds as of round t 0 , the system will be in the configuration in which all players are cooperative, and will remain in this configuration forever.

Proof. By assumption, there exists two neighbors u 0 , u 0 ∈ Dt0 . We define inductively a sequence of sets {U j } j≥0 , setting U 0 = {u 0 , u 0 }, and for every j, defining U j+1 = N (U j ). to u. This path is of length 2s ≤ diam(G), so s ≤ k 0 . Since u +1 ∈ N (N (u )) for every ≤ s, it follows by induction on that for every ≤ s, u ∈ U , and hence that u ∈ U s . As we have seen, the sequence {U k } k is non-decreasing and since s ≤ k 0 , we obtain u ∈ U k0 . This establishes that U k0 = U .

Next, we prove by induction that for every k, U k ⊆ D2k . This is true for k = 0 by definition. Assume that this is true for some integer k ≥ 0. We have

U k+1 = N (N (U k )) ⊆ N (N ( D2k )) = D2k+2 ,
where the second transition is by the induction hypothesis and the last transition is due to Lemma 7. This concludes the induction proof. Since we have already proved that U k0 = U , we conclude that U ⊆ D2k0 .

We can apply the same reasoning to V and obtain that V ⊆ D2k0 . Thus, D2k0 contains all players. By Lemma 8, from round 2k 0 +1 ≤ 2diam(G)+1 onward, the system will be in a configuration in which all players are cooperative and will remain in this configuration forever. This concludes the proof of Lemma 12.

Finally, we wrap the aforementioned lemmas to prove the theorem with respect to different networks. Recall that initially, each player is set to be a defector with probability 1 -, a hypocritical with probability /2, and a cooperative with probability /2, for some fixed 0 < < 1 independent of n. We consider three families of networks.

• If G is not bipartite, then Lemma 11 guarantees that the system converges to full cooperation in 3 • diam(G) + 1 rounds, provided that the initial configuration contains at least one non-defector. This happens with overwhelmingly high probability, specifically, 1 -(1 -) n = 1 -1 c n , for some constant c > 1. This completes the proof of the first item in Theorem 6.

• If G is bipartite, then the set of players in G can be split into two disjoint sets U and V such that all edges are between U and V . Lemma 12 guarantees that the system converges to full cooperation diam(G) + 1 rounds, provided that there is at least one non-defector in U and at least one non-defector in V . Let us see what is the probability that the initial configuration satisfies this.

-If G is ∆-regular, then both U and V contain precisely n/2 players. This follows from the fact that the number of edges outgoing from U , respectively V , is precisely ∆|U |, respectively ∆|V |, and these numbers are equal. In this case the probability that there is at least one non-defector in U and at least one non-defector in

V is 1 -(1 -) n/2 2 ≥ 1 -2(1 -) n/2 > 1 -1 c n ,
for some constant c > 1. This completes the proof of the second item in Theorem 6.

-For general bipartite G with minimal degree ∆, we have that both |U | and |V | are greater or equal to ∆. Hence, the probability that there is at least one non-defector in U and at least one non-defector in

V is at least 1 -(1 -) ∆ 2 ≥ 1 -2(1 -) ∆ > 1 -1 c ∆ , for some constant c > 1.
This completes the proof of the third item in Theorem 6.

C Proof of Theorem 2

The goal of this section is to prove Theorem 2. In fact, we prove the more general theorem below.

Theorem 13. Consider a network G with n players and minimal degree ∆ undergoing the two-order model, so that the following conditions hold.

• Condition (i) α 2 < β 2 , and

• Condition (ii) α 1 < ∆β 1 .
Then the following holds for some constant c > 1.

• If G is not bipartite then with probability at least 1 -1 c n , in at most 3 • diam(G) + 1 rounds, the system will be in a configuration in which all players are cooperative, and will remain in this configuration forever.

• If G is bipartite and ∆-regular then with probability at least 1 -1 c n , in at most diam(G) + 1 rounds, the system will be in a configuration in which all players are cooperative, and will remain in this configuration forever.

• If G is bipartite then with probability at least 1 -1 c ∆ , in at most diam(G) + 1 rounds, the system will be in a configuration in which all players are cooperative, and will remain in this configuration forever.

Before we prove the theorem, we note that Condition (ii) is necessary for the emergence of cooperation on ∆-regular graphs, since having α 1 > ∆β 1 would imply that it is always beneficial to defect on the first level.

Proof of Theorem 13. Consider a network G, and parameters α 1 , α 2 , β 1 , and β 2 , satisfying Conditions (i) and (ii) in Theorem 13. We first observe that under Condition (i), at any round t ≥ 1, no player ever chooses to be a private cooperator in G. Indeed, if ∆ 2 (u) ≥ 1, then a private cooperator would pay

α 1 + ∆ 2 (u)β 2 > α 1 + ∆ 2 (u)α 2 ≥ α 1 + α 2 ,
hence, more than the cost of cooperating, and when ∆ 2 (u) = 0, a private cooperator would pay α 1 > 0, hence, more than the cost of defecting. It follows that, although the initial configuration may include private cooperators, this behavior completely disappears from the system after the first round.

Next, we aim to prove Theorem 13 by reducing it to Theorem 6. Let G be a network identical to G, undergoing the main model (for which Theorem 6 applies), taking the parameters:

E h = α 2 α 1 + α 2 , ρ h = β 1 α 1 + α 2 , and
ρ d = β 1 + β 2 α 1 + α 2 . (5)
A configuration C on G is an assignment of behaviors, namely, either defectors, cooperators, hypocritical, or private cooperators, to the players in G. Recall that the initial configuration on G is sampled according to the distribution ψ( ), so that each player is initially chosen to be a defector with probability 1 -, and any of the three remaining behaviors with probability /3. We next define a mapping f , transforming each initial configuration C on G to an initial configuration C on G . The mapping is very simple: All players in G remain with the same behavior as in G except that private cooperators are turned into defectors. It is easy to see that given the distribution ψ( ), this mapping induces the distribution ψ ( ) on the initial configurations in G , where = 2 3 . Indeed, under this mapping, a player in G is initially chosen to be a defector with probability 1 -+ /3 = 1 -, a cooperator with probability /3 = /2, and hypocritical with probability /3 = /2.

At this point, we address a technicality that concerns the randomness involved in breaking ties. That is, recall that at any round t, if the minimal cost is attained by several behaviors then the player chooses one of them uniformly at random. One way to implement this is by considering a certain order between the behaviors, and sampling a number uniformly at random r ∈ [0, 1]. For instance, consider the following ordering: cooperator > hypocritical > defector (as we saw, in the regime of parameters we consider, a private cooperator in the two-order model never attains the minimal cost, and hence it is never considered as an option). If a player needs to choose, say, between being a cooperator or a defector, then it chooses to be a cooperator if r is in [0, 0.5], and otherwise, it chooses to be a defector. This means that given a sequence of random numbers {r i } ∞ i=1 , where r i ∈ [0, 1], the behavior of a player is deterministically described by the behaviors of its neighbors at each round.

Consider a fixed sequence of random numbers {r i } ∞ i=1 , where r i ∈ [0, 1]. Let C 0 be an initial configuration in G, and let C t denote the configuration C 0 at round t, with the costs defined according to the two-order model on G, and using the sequence {r i } ∞ i=1 to break ties if necessary. Let C 0 = f (C 0 ) be the mapped configuration on G , and let C t be the corresponding configuration at round t ≥ 1, with the costs defined according to the parameters mentioned in Eq. ( 5), and using the same sequence {r i } ∞ i=1 to break ties if necessary.

Claim 14. For every t ≥ 1, we have

C t = C t ,
Proof of Claim 14. Our goal is to show that at any round t ≥ 0, a player u in C t is a defector, a cooperator or a hypocritical, respectively, if and only if it is a defector, a cooperator or a hypocritical, respectively, in C t , and that a private cooperator in C t is a defector in C t .

Let us prove this claim by induction. By definition, the claim holds for t = 0. Assume that it holds for some integer t ≥ 0. By the induction hypothesis, for every player u, the set ∆ 2 (u) in G is equal to ∆ d(u) in G . Hence, with our definitions of E h , ρ h and ρ d in Eq. ( 5), we argue that the cost of being a cooperator in C t (respectively hypocritical, defector) is Moreover, recall that no player in G ever chooses to be a private cooperator in rounds t ≥ 1. Hence, the behavior that minimizes the cost in G is the same as in G . It follows that at round t + 1, all players choose the same behavior in G as they would in G , which establishes the induction proof, and concludes the proof of Claim 14.

Next, we prove that with our choices of E h , ρ h and ρ d in Eq. ( 5), Conditions (i) and (ii) in Theorem 13 imply Conditions (i) and (ii) in Theorem 6:

α 2 < β 2 ⇐⇒ α 2 + β 1 < β 1 + β 2 ⇐⇒ α 2 α 1 + α 2 + β 1 α 1 + α 2 < β 1 + β 2 α 1 + α 2 ⇐⇒ E h + ρ h < ρ d , and
∆ • β 1 > α 1 ⇐⇒ α 2 + ∆ • β 1 > α 1 + α 2 ⇐⇒ α 2 α 1 + α 2 + ∆ • β 1 α 1 + α 2 > 1 ⇐⇒ E h + ρ h • ∆ > 1.
Hence, we can apply Theorem 6 to the mapped process on G . It follows that in the number of rounds and probability guarantees as stated in Theorem 6, G converges to the configuration in which all players are cooperators, and remains in that configuration forever. By Claim 14, this holds for G as well, concluding the proof of Theorem 13.

Figure 1 :

 1 Figure 1: The two stages of the dynamics. The direction of the red and blue arrows indicates the direction of the social-pressure applied on the player occupying the central vertex. Cooperative players pay an energetic cost of E c = 1 and are immune to social-pressure. A defector player pays a social-pressure cost of ρ d = 0.5 per non-defector neighbor. A hypocritical player pays social-pressure cost of ρ h = 0.25 per nondefector neighbor, and an energetic cost of E h = 0.2. (a) First stage: defectors become hypocritical players. A defector player (central vertex on the left) has one non-defector neighbor (in this case, a cooperator), implying that its social-pressure cost is ρ d = 0.5. Therefore, that player would prefer to be hypocritical (right), paying only 0.25 + 0.2 = 0.45. (b) Second stage: hypocritical players become cooperators. Here, a hypocritical player (central vertex on the left) is surrounded by four non-defector neighbors. In this case, the social-pressure accumulates to favor cooperation (right).

  (a) Time evolution on a 50 × 50 grid (b) Time evolution on a 10-regular network

Figure 2 :

 2 Figure 2: Evolution of cooperation in grids and random 10-regular networks. Figure (a) corresponds to a 50 × 50 grid network, and Figure (b) corresponds to a random 10-regular network with 1000 vertices. Both simulations start with a configuration in which 99% of players are defectors. Figures (a) and (b) show how the population evolves over time (number of rounds). The chosen parameters satisfy the assumption in Eq. (1). The insets show the population's evolution when hypocritical behavior is not available to the agents. See Methods for more details.

7 Figure 3 :

 73 Figure 3: Emergence of cooperation on various networks. The figure depicts the steady-state levels of cooperation on different network families. (a) corresponds to a 50 × 50 grid network, (b) corresponds to random 10-regular networks with 1000 vertices, (c) corresponds to Erdös-Rényi networks with 1000 vertices and parameter p = 1/100, and (d) corresponds to Barabási-Albert networks with 1000 vertices and parameter m = 5. All simulations start with a configuration in which 99% of players are defectors. In all figures, for each couple (ρ h , E h ), a pixel is being drawn, whose red (resp. green, blue) component corresponds to the average proportion of defectors (resp. cooperators, hypocrites) at steady state. See Methods for more details.

  (a) Relaxed model on a 50 × 50 grid (b) Relaxed model on 10-regular networks (c) Cooperation level on a 50 × 50 grid with 20% non-defectors initially (d) Cooperation level on 10-regular networks with 20% non-defectors initially

Figure 4 :

 4 Figure 4: Relaxed model on grids and random 10-regular networks. The figure depicts simulation results using relaxed versions of the main model. In (a) and (b) the greediness assumption in the decision making process is relaxed, allowing for some "irrationality" (see Methods for more details). In (c) and (d), the initial configuration contains 80% defectors, instead of 99% as used in Figure 3. The plots in (a) and (c) correspond to a 50×50 grid network and should be compared with Figure 3a, whereas (b) and (d) correspond to random 10-regular networks with 1000 vertices and should be compared with Figure 3b.

1

  α1+α2 times the cost of being a cooperator in C t (respectively hypocritical, defector). Indeed, a cooperator in C t pays1 = 1 α 1 + α 2 • (α 1 + α 2 ), while (α 1 + α 2 ) is what it pays in C t . A hypocritical player in C t pays E h + ∆ d(u) • ρ h = α 2 α 1 + α 2 + ∆ 2 (u) β 1 α 1 + α 2 , while (α 2 + ∆ 2 (u) • β 1) is what a hypocritical pays in C t , and a defector in C t pays∆ d(u) • ρ d = ∆ 2 (u) • β 1 + β 2 α 1 + α 2 , while ∆ 2 (u) • (β 1 + β 2 ) is what it pays in C t .

Acknowledgments

The authors would like to thank Yannick Viossat, Nathaniel Herzberg, Pierre Fraigniaud, and Ofer Feinerman for helpful discussions. This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No 648032).

Supplementary Information

A Preliminaries

A.1 Definitions

Let G be a connected, undirected network. In the context of our models, we often refer to the vertices of G as players. Given a player u, we write N (u) the set of neighbors of u. Similarly, given a subset A of players, we write N (A) the set of neighbors of A, that is

The degree of a player u is the number of its neighbors, that is |N (u)|. We say that G has minimal degree ∆ if every player has degree at least ∆. A network is called ∆-regular if all the vertices have degree precisely ∆.

For two players u and v in G, let d G (u, v) denote the distance between u and v, that is, the number edges on the shortest path linking u to v in G. Similarly, given a subset A of players, we write d G (u, A) the distance between u and A, that is

A bipartite network is a network G whose set of vertices can be divided into two disjoint sets U and V , such that every edge connects a player in U to a player in V . It is a well-known fact that a network is bipartite network if and only if it does not contain any odd-length cycles [START_REF] Diestel | Graph theory 3rd ed[END_REF].

A.2 A result in graph theory

The following lemma (mentioned also in [START_REF] Mohammadian | A generalization of the odd-girth theorem[END_REF]) appears to be a basic result in graph theory, however, we could not find a formal proof for it. We therefore provide a proof here for the sake of completeness. Lemma 3. The shortest odd-length cycle of any non-bipartite network G is of length at most 2diam(G) + 1.

Proof. Consider a non-bipartite network G. Such a network necessarily has an odd-length cycle. Let 2k + 1 be the shortest length among the odd-length cycles in G, where k is an integer, and let C = (u 1 , . . . , u 2k+1 ) be such a cycle. Claim 4. For every i, j ∈ {1, . . . , 2k + 1} such that d C (u i , u j ) ≥ 2, there exist = i, j and a shortest path P between u i and u j such that P contains u .

Proof of Claim 4. Assume by way of contradiction that we can find i < j such that no shortest path between u i and u j has any intermediate vertex among {u 1 , . . . , u 2k+1 }. Up to re-indexing the vertices of the cycle, we can assume that j -i ≤ k. Let (u i = v 1 , v 2 , . . . , v s , v s+1 = u j ) be a shortest path between u i and u j . By assumption, {v 2 , . . . , v s } ∩ {u 1 , . . . , u 2k+1 } = ∅, and s < j -i (otherwise (u i , u i+1 , . . . , u j-1 , u j ) is a shortest path). Consider two cases:

is an odd-length cycle shorter than C, which is a contradiction. Claim 10. For every integer j ≥ 0,

(each player in U j has at least one neighbor in U j ), and

(each player in U j is non-defector at round t 0 + j).

Proof of Claim 10. The proof proceeds by induction. The base of the induction, corresponding to j = 0, is true by the assumption on u 0 and u 0 . Next, let us assume that the claim holds for some integer j ≥ 0. By the induction hypothesis with respect to Eq. ( 3), U j ⊆ N (U j ), so N (U j ) ⊆ N (N (U j )), and hence, by definition, U j+1 ⊆ N (U j+1 ). In other words, we have proved that Eq. ( 3) holds at round j + 1. Next, by the induction hypothesis with respect to Eq. ( 4), we have U j ⊆ Dt0+j , so N (U j ) ⊆ N ( Dt0+j ). By definition of U j+1 , and by Lemma 7, we can rewrite this as U j+1 ⊆ Dt0+j+1 , establishing Eq. ( 4) at round j + 1. This completes the induction step and concludes the proof of Claim 10.

A direct consequence of Eq. ( 3) in Claim 10 and the definition of the sequence {U j } j is that U j+1 = U j ∪ N (U j ), and so, U j+1 is equal to U j together with all the neighbors of players in U j . As a consequence, for every j ≥ diam(G), the set U j contains all players. By Eq. ( 4) of Claim 10, this implies that from round t 0 + diam(G) onward, all players are non-defectors.

By Lemma 8, we conclude that from round t 0 + diam(G) + 1 onward, all players are cooperative. This completes the proof of Lemma 9.

Lemma 11. Assume that Conditions (i) and (ii) hold, and that G is not bipartite. If D0 = ∅, i.e., if initially there is at least one non-defector player, then in at most 3 • diam(G) + 1 rounds, the system will be in the configuration in which all players are cooperative, and will remain in this configuration forever.

Proof. By assumption, G is not bipartite, or equivalently, G contains at least one odd-length cycle. Let (u 1 , . . . , u 2k+1 ) be a shortest odd-length cycle of G. Given s = d G (u 1 , D0 ), let (v 0 ∈ D0 , v 1 , . . . , v s-1 , v s = u 1 ) be a shortest path from D0 to u 1 . By Lemma 7, it follows by induction that for every t ∈ {0, . . . , s}, v t ∈ Dt , and hence, u 1 ∈ Ds (note that, although v t-1 ∈ Dt-1 , it could be that v t-1 / ∈ Dt ). Similarly, for every t ∈ {1, . . . , k}, u 1+t ∈ Ds+t and u 2k+2-t ∈ Ds+t . Hence, u k+1 ∈ Ds+k and u k+2 ∈ Ds+k . In other words, we have just showed that in round s + k, we have two non-defector neighbors.

By the definition of diameter, s ≤ diam(G). By Lemma 3, we also have k ≤ diam(G). By Lemma 9, the system needs at most diam(G) + 1 rounds after round s + k to reach full cooperation. We conclude that it reaches cooperation in at most 3 • diam(G) + 1 rounds, as stated.

Lemma 12. Assume that Conditions (i) and (ii) hold, and that G is bipartite. The set of players can be partitioned into U and V such that

then in at most T = diam(G) + 1 rounds, the system will be in the configuration in which all players are cooperative, and will remain in this configuration forever.

Proof. By assumption, G is bipartite. We define inductively a sequence of subsets of the set of players, U 0 = U ∩ D0 , and for every k ≥ 0, U k+1 = N (N (U t )) -that is, U k+1 contains the neighbors (in U ) of the neighbors (in V ) of the players in U k . Note that, as a consequence of this definition, U k ⊆ U k+1 . Let k 0 = diam(G)/2 .

Let us show that U k0 = U (and hence, that for every k ≥ k 0 , U k = U ). For this purpose, consider a player u ∈ U . Let (u 0 , v 0 , u 1 , v 1 , . . . , u s-1 , v s-1 , u s ), where u 0 ∈ U 0 and u s = u be a shortest path from U 0