Decentralisation Conscious Players And System Reliability

Sarah Azouvi¹ and Alexander Hicks²

¹ Protocol Labs

sarah.azouvi@protocol.ai

² University College London

alexander.hicks@ucl.ac.uk

Abstract. We propose a game-theoretic model of the reliability of decentralised systems based on Varian’s model of system reliability [27], to which we add a new normalized total eort case that models decentrali- sation conscious players that prioritize decentralisation. We derive the Nash equilibria in the normalized total eort game. In these equilibria, either one or two values are played by players that do not free ride. The speed at which players can adjust their contributions can determine how an equilibrium is reached and equilibrium values. The behaviour of decentralisation conscious players is robust to deviations by other players.

Our results highlight the role that decentralisation conscious players can play in maintaining decentralisation. They also highlight, however, that by supporting an equilibrium that requires an important contribution they cannot be expected to increase decentralisation as contributing the equilibrium value may still imply a loss for many players. We also discuss practical constraints on decentralisation in the context of our model.

Keywords: decentralisation, public goods, free-riding, reliability

1 Introduction

The reliability of a system captures the likelihood that it performs as intended. For a decentralised system, there are two important components to consider, the number of participants and the distribution of power between them [26]. Even if there is a high number of contributors, if one of them has signicantly more control over the system, there will be no meaningful level of decentralisation. This presents a problem that has been hard to solve in practice. How can the eort put into a system grow while maintaining an acceptable level of decentralisation?

Participation rewards can incentivise an increase in the eort invested in a system but a greater total eort can also be more centralised. Certain protocol considerations may alleviate this eect, e.g., at the consensus level [7]. It is also sometimes assumed that a portion of players will behave altruistically, following protocol guidelines even when an a priori more protable strategies exist.

An alternative assumption, which we consider here, is that players have an incentive to maintain decentralisation. Short-term prots may be outweighed by the possible long-term prots associated with maintaining a reliable system. For example, the value of a cryptocurrency that is vulnerable to hostile takeovers may decrease so miners have an incentive to maintain decentralisation and preserve the value of the tokens they hold and continue to receive.

Three observations support this assumption. First, the market price of a cryptocurrency is linked to its security [9]. Second, numerous aws have been identied in the incentive structure of cryptocurrencies [11,21], yet attacks based on these have scarcely been observed [23]. Third, a mining pool has previously acted to avoid controlling more than half of Bitcoin’s hash rate [20].

To further understand the rationality of maintaining decentralisation, this paper studies a game-theoretic model of decentralisation conscious players who prioritise decentralisation. With this model, we can analyse how such players will behave to ensure that a system remains decentralised, what eort they may contribute, and under which circumstances they will free-ride.

Our contributions The main contribution of this paper is the introduction and analysis of the normalised total eort game with decentralisation conscious players that extends Varian’s system reliability model to decentralised systems.

We introduce our model based on the normalized total eort (NTE) function in the context of Varian’s system reliability model [27] in Section2. In Section3, we derive the two types of Nash equilibria between decentralisation conscious players in which players contribute the same amount or two distinct amounts while others free ride. We also consider the social optimum, in which players contribute the same eort while minimizing their costs to maximize decentralisation.

To understand how decentralisation conscious players will behave in real systems alongside selsh and Byzantine players, we study in Section4the robustness of the previously derived equilibria when (i) the number of players change, which does not always aect the equilibrium; (ii) players deviate from the equilibrium, which can lead to a new equilibrium where players (possibly fewer) contribute a greater eort. Non-myopic players may, therefore, be incentivised to deviate from an equilibrium to reach a new equilibrium with fewer contributing players and a greater share of rewards.

Finally, we discuss in Section6some practical constraints on decentralisation in relation to our model.

2 Modelling System Reliability And Normalized Total Eort

Varian’s original model of system reliability (treated as a public good) considers three cases based on how the individual eorts x_iof players are factored in [27]. The weakest link case considers the minimal eort exerted by any one of the players i.e, F (x₁;:::;xn) = mini(xi). The total eort case considers the sum of every Pn player’s eorts i.e., F (x₁;:::;x_n) =_i=1x_i. The best shot case considers the maximal eort exerted by any one of the players i.e., F (x₁;:::;x_n) = max_i(x_i).

$$ x_{i} $$

$$ \textstyle(F_{1},\ldots,x_{n})=\operatorname{m i n}{i}(x{i}) $$

$$ Ftextstyle F(x_{1},\ldots,x_{n})=\sum_{i=1}^{n}x_{i} $$

$$ F(x_{1},\ldots,x_{n})=\mathrm{m a x}{i}\ \ x{i}\big(x_{i}\big) $$

Reliability will usually depend on a combination of these cases. For example, in the case of software security, a program’s correctness can depend on the weakest link (the developer that introduces bugs), vulnerability testing depends on the total eort of all the testers, and the contributions of a system architect maps to the best shot case [4].

For each case, the Nash equilibria can be computed with the expected pay-o u_ifor a player i expressed as in Equation1, as can be the social optimum based on social pay-o SP expressed as in Equation2. The likelihood that the system operates successfully is captured by P (F (x₁;:::;x_n)), which is assumed to be dierentiable, increasing, and concave. The parameter v_iis the value derived by player i of the system operating successfully, and c_ix_iis the cost to player i where c_iis a constant. The choice of a linear cost function of the form c_ix_iimplicitly ignores more complex forms of cost and any xed costs. This is a limitation but it is realistic in relevant cases e.g., the energy required to operate a computer may be valued at a xed price per kilowatt-hours.

$$ u_{i} $$

$$ S P $$

$$ P(F(x_{1},\ldots,x_{n})) $$

$$ v_{i} $$

$$ c_{i}x_{i} $$

$$ c_{i} $$

$$ c_{i}x_{i} $$

$$ u_{i}=P\big(F(x_{1},\ldots,x_{n})\big)v_{i}-c_{i}x_{i} $$

(1)

$$ S P=P(F(x_{1},\ldots,x_{n}))(v_{1}+\ldots+v_{n})-\sum_{i=1}^{n}c_{i}x_{i} $$

(2)

The equilibria can be used to determine when free-riding can be expected to occur based on the form of F. For example, in the total eort case, the equilibrium is for players to free ride on the player who has the highest benetvi cost ratio. The so^cial optimum, obtained by maximizing the social pay-o ci rather than the player’s utility functions, can also reveal how selsh behaviour from the players will lead to an outcome that is dierent from the social optimum. This is the case in the total eort case used as an example. Players free ride on the player with the highest benet-cost ratio, which amounts to less total eort than in the social optimum, and the \wrong" players (those with the smallest benet-cost ratio) can be found to contribute that eort.

$$ \frac{v_{i}}{c_{i}} $$

The takeaway from Varian’s results is that centralisation emerges even in the total eort case that involves everyone’s contributions, and that rational behaviour can conict with the social optimum i.e., selsh behaviour can lead to a weaker system { a concept known as the price of anarchy [24]. If decentralisation is desired, this means that an alternative model that produces individual and social outcomes that support a decentralised and stronger system is required.

To model decentralisation, the relative contribution of every player in the system must be taken into account because while the total eort should be as high as possible, the eort must also be as evenly distributed as possible. In practice, however, there are trade-os between maximizing total eort and distributing eort evenly. It is unlikely that every player will have the same capacity to contribute, so maximizing the total eort is likely to come at the cost of a uniform distribution of eort, and vice versa.

With this in mind, we dene in Equation3the normalized total eort (NTE) function based on the total eort and the maximal contribution. If the total eort is high but the maximal eort is also high then the NTE may not be as high as when the total eort is high but the maximal eort is low. P

$$ F(x_{1},\ldots,x_{n})={\frac{\sum_{i=1}^{n}x_{i}}{\operatorname*{m a x}{i}(x{i})}} $$

(3)

The normalised total eort function is scale invariant i.e., F (x₁;:::;x_n) = F (x₁;:::;x_n) for any. This is because we are modelling players who care about decentralisation over total eort. The goal is to capture the fact that in systems that are designed to be decentralised, it is not only the total eort (studied by Varian) that matters but the distribution of eort and, in particular, how much the maximal contribution by a single player is as a portion of the total eort, which our measure captures. Finding a measure that captures both this and the benets of a higher total eort is an open problem, and measures similar to ours (e.g., the work of Kwon et al. [22]) suer from the same limitation.

$$ F(\alpha x_{1},\ldots,\alpha x_{n})= $$

$$ F(x_{1},\ldots,x_{n}) $$

We show in Section4that contributions can still be expected to increase given that other players who prioritize maximising their share of rewards exist. Thus, much like in software security, a decentralised system’s reliability depends on nodes that are primarily concerned with decentralisation (normalised total eort) and nodes that are primarily concerned with higher contributions (and higher rewards) that increase the best shot and total eort. Because the best shot and total eort case have already been studied by Varian, our focus in this paper is the normalised total eort case.

3 Equilibria Between Decentralisation Conscious Players

We begin by studying the Nash equilibria of the NTE game dened below.

Denition 1(Normalized Total Eort Game). We call the normalized to- tal eort game (NTEG) the game consisting of n players with costs (c₁;:::;c_n) 2 n n ⁿ (R⁺), valuations (v₁;:::;vⁿ) 2 (R⁺), contributions (x₁;:::;xⁿ) 2 (R⁺), vi utility functions dened by equations3and1, benet-cost ratios_i= such c_i that1< ::: < n, andPwhere we assume a logarithmic reliability function n i=1xi P (F (x₁;:::;x_n)) = l_n for _maxi(x_i) > 0*. By convention we have* maxi (xi) P (F(0*;:::;* 0)) = 0 i.e., a system with no contributions does not function. P

$$ \big(c_{1},\ldots,c_{n}\big)\in $$

$$ (\mathbb{R}_{+}^{*})^{n} $$

$$ \big(v_{1},\ldots,v_{n}\big):\in:(\mathbb{R}_{+}^{*})^{n} $$

$$ \bigl(x_{1},\ldots,x_{n}\bigr),\in,(\mathbb{R}_{+})^{n} $$

$$ \beta_{i}=\frac{v_{i}}{c_{i}} $$

$$ \beta_{1}:<:\ldots:<:\beta_{n} $$

$$ \textstyle\mathrm{}{P}\big(F(x_{1},\ldots,x_{n})\big);=;\operatorname{l n}\big(\frac{\sum_{i=1}^{n}x_{i}}{\operatorname*{m a x}{i}(x{i})}\big) $$

$$ (x_{i}),>,0 $$

$$ P \left(F (0, \dots , 0)\right) = 0 i. e., a $$

$$ F(x_{1},\ldots,x_{n})={\frac{\sum_{i=1}^{n}x_{i}}{\operatorname*{m a x}{i}(x{i})}} $$

(3)

$$ u_{i}=v_{i}P\big(F(x_{1},\ldots,x_{n})\big)-c_{i}x_{i} $$

(1)

Two-player case We start by considering the simple case of a two-player game and the following theorem, which we prove in AppendixA.

Theorem 1. In a two-player NTEG, the Nash equilibria are for both players to 1 contribute the same eort x₁ = x₂ = x_eqsuch that x_eqmin(¹;₂). 2

$$ x_{1}=x_{2}=x_{e q} $$

$$ x_{e q}\leq\frac{1}{2}\operatorname*{m i n}(\beta_{1},\beta_{2}) $$

Both players contribute the same eort when the equilibrium is played, which is the only possible \decentralised" solution.

Multiplayer case For n > 2 players, we prove the following in AppendixB.

Theorem 2. In a n > 2 player NTEG, there exist two types of equilibrium.

1.(1-value equilibria) players i+1 to n (for 1 i < n) contribute xeqsubject to the constraint expressed by Inequality4and players 1 to i with the smallest benet-cost ratio free ride on them.

$$ 1\leq i<n) $$

$$ x_{e q} $$

$$ \frac{1}{n-i}\beta_{i}\leq x_{\mathit{e q}}\leq\frac{1}{n-i}\beta_{i+1} $$

(4)

2.(2-value equilibria) player i contributes x_m, players (i + 1 to n) contribute xM, where xm< xM, subject to the constraints in Inequality5and Equa- tion6and players 1 to i 1 free ride, for 1 i n (with no players free riding if i = 1*).*

$$ x_{m} $$

$$ x_{M} $$

$$ x_{m},<,x_{M} $$

$$ 1,\leq,i,\leq,n $$

$$ \frac{1}{n-i+1}\beta_{i}<x_{M}<\frac{1}{n-i}\beta_{i} $$

(5)

$$ x_{m}=\beta_{i}-\big(n-i\big)x_{M} $$

(6)

We highlight Lemma1(proven as part of the proof) that we will reuse later.

Lemma 1. If there exist two contributing rational players whose contributions are strictly less than max_i(x_i) and who play their best strategy, then those players must have the same benet-cost ratio.

$$ \ (x_{i}) $$

Unless specied otherwise, we denote by x_eqthe value played by the players or bulk of players in the 1-value or 2-value equilibrium, respectively. For both types of equilibrium, the lower x_eqis the more decentralised the system is, as more players can contribute and the less free-riding there is.

$$ x_{e q} $$

$$ x_{e q} $$

The fact that one equilibrium is for all players to contribute the same amount of eort makes sense as the NTE function encodes the social goal of maximizing decentralisation. It also prevents the perverse eects of any feedback loops that enable some players to contribute increasingly more than other players.

The 2-value equilibrium is less expected. It shows that, even if some players cannot match the other players’ contributions (due to their own costs or valuation), they may still be incentivised to contribute.

3.1 The impact of a reward

The equilibria we have derived above include the case where everyone contributes no eort. Adding a reward function R_i(x₁;:::;x_n) to the utility function, as in Equation7. (e.g., cryptocurrency mining rewards) is a way of explicitly incentivising non-zero contributions, particularly from new players.

$$ R_{i}(x_{1},\ldots,x_{n}) $$

$$ u_{i}=P(F(x_{1},\ldots,x_{n}))v_{i}-c_{i}x_{i}+R_{i}(x_{1},\ldots,x_{n}) $$

(7)

A reward separate from the valuation v models the compensation for the eort invested in the system rather than the benet derived from being able to use the system. In practice, it may be a constant R that can be won by players with a probability proportional to the eort they contribute. Under certain conditions, this is an optimal allocation rule [14] so we restrict ourselves to this case.

$$ R_{i}(x_{1},\ldots,x_{n})=\left{\begin{matrix}{R_{\frac{x_{i}}{\sum_{j=1}^{n}x_{j}}},\operatorname{i f}\operatorname*{m a x}(x_{1},\ldots,x_{n})>0}\ {0,\quad\quad\quad\quad\quad\quad\operatorname{i f}\operatorname*{m a x}(x_{1},\ldots,x_{n})=0}\ \end{matrix}\right. $$

(8)

This removes the x_eq= 0 equilibrium without signicantly aecting other equilibria. In the two-player case, an equilibrium still involves the two players contributing the same value x subject to dierent constraints and under the additional assumptions that R < min(v₁;v₂). This expresses the fact that the player’s valuations of the system must be at least greater than the value of the reward { it would make little sense to gain a reward that is greater than the value of the system functioning. We prove the following theorem in AppendixC.

$$ x_{e q}=0 $$

$$ R<\operatorname*{m i n}(v_{1},v_{2}) $$

Theorem 3. In a two player NTEG with reward R < min(v₁;v₂) there exist innite Nash equilibria where both players contribute the same value x such that

$$ R,<,\operatorname*{m i n}(v_{1},v_{2}) $$

$$ \begin{cases}{\frac{c_{1}}{4R}((R\frac{1-\sqrt{A_{1}^{\prime}}}{2c_{1}})^{2}-\beta_{1}^{2})<x<\frac{c_{1}}{4R}((R\frac{1+\sqrt{A_{1}^{\prime}}}{2c_{1}})^{2}-\beta_{1}^{2})}\ {\frac{c_{2}}{4R}((R\frac{1-\sqrt{A_{2}^{\prime}}}{2c_{2}})^{2}-\beta_{2}^{2})<x<\frac{c_{2}}{4R}((R\frac{1+\sqrt{A_{2}^{\prime}}}{2c_{2}})^{2}-\beta_{2}^{2})}\ \end{cases} $$

(9)

2 2 0 cR1v₁c₁ v₁ 0 cR2v₂c₂ v₂ with₁= ¹ + 4 ( +) and²= ₁ + 4 ( +). _{R c}1 R c₂

$$ \varDelta_{1}^{\prime}=1+4\frac{c_{1}}{R}(\frac{v_{1}^{2}c_{1}}{R}+\frac{v_{1}}{c_{1}}) $$

$$ \varDelta_{2}^{\prime}=1+4\frac{c_{2}}{R}\big(\frac{v_{2}^{2}c_{2}}{R}+\frac{v_{2}}{c_{2}}\big). $$

We leave the multiplayer analysis as future work.

3.2 Social optimum

An insight from Varian’s work is that the equilibria and social optima are not necessarily the same e.g., the total eort social optimum involves players contributing much more than in the Nash equilibrium [27].

In the NTE case, the social optimum is for players to contribute the smallest non-zero amount possible as this maximizes the level of decentralisation while minimizing their costs. If all contributions are equal then in most cases it is also a Nash equilibrium. This convenient outcome is expected from our choice of NTE that reects a desire to ensure that the social goal of decentralisation is met, so the NTE function is well dened in that sense. The only exception is when the benet-cost ratio of some players is too low as they then free-ride.

Figuring out an acceptable minimal contribution can be straightforward when it is possible to impose a minimum contribution. Ethereum’s implementation of proof-of-stake does this, but not all systems impose a minimum contribution.

4 Robustness Of Decentralisation Conscious Players to Variations By Others

In practice, players may leave or join the game, as well as increase or decrease their contributions because of selsh behaviour or, more generally, Byzantine faults. Thus, it is important to analyse how decentralisation conscious players tolerate variations in the actions of other players. We do this by studying how the equilibria for the NTEG change after such events.

In the analysis that follows we will be using a result derived in the proof of Theorem2, which is that for each player j the best response to (xed) contributions of other players is as follows.

$$

1. \mathrm {i f} \sum_ {i \neq j} x _ {i} < \beta_ {j}, \mathrm {c o n t r i b u t e} \min (\max _ {i \neq j} (x _ {i}), \beta_ {j} - \sum_ {i \neq j} x _ {i}) $$

P_i6=j 2.ifi6=jx_{i j}, contribute zero.

$$ \textstyle\sum_{i\neq=j}x_{i}\geq\beta_{j} $$

Equivalently, player’s j best response can be written as in Equation10.

$$ \operatorname*{m a x}{0,\operatorname*{m i n}(\operatorname*{m a x}{i\neq j}(x{i}),\beta_{j}-\sum_{i\neq j}x_{i})} $$

(10)

In this section, we note n the number of contributing players.

4.1 Change in number of players

New player joining

1-value equilibrium We rst consider the case where the players play the 1-value equilibrium described in Theorem2. If one player joins the game, the robustness of the equilibrium depends both on x_eqand on the benet-cost ratio of the 1 new player. From Condition4, we have that x_eq j*; 8*¹ j n. n

$$ x_{e q} $$

$$ \beta $$

$$ x_{e q}\leq\frac{1}{n}\beta_{j},;\forall1\leq j\leq n $$

We proceed as follows. For dierent values of x_eqwe study what would be the new player’s best response x_newand whether they would join the game i.e., contribute a non-zero eort. We then look at whether the introduction of a new player playing x_newdisrupts the equilibrium for the rest of the players i.e., whether having n players play x_eqand one player play x_newis still an equilibrium. We nd that the original n players change their contributions if and only if > ₁ 1 1 and1< xeq<. We prove this result in AppendixD. n+1 n

$$ x_{e q} $$

$$ x_{\mathrm{n e w}} $$

$$ x_{\mathrm{n e w}} $$

$$ x_{e q} $$

$$ x_{\mathrm{n e w}} $$

$$ \frac{1}{n+1}\beta_{1}<x_{\mathit{e q}}<\frac{1}{n}\beta $$

$$ \operatorname{i f}\beta>\beta_{1} $$

Theorem 4. In a NTEG that is in a state of 1-value equilibrium with n play- ers contributing x_eq, the introduction of a new player with benet-cost ratio changes the value played by the other players if and only if > ₁and 1 1 1< xeq<. n+1 n

$$ x_{e q}, $$

$$ \beta $$

$$ \beta,>,\beta_{1} $$

$$ \frac{1}{n+1}\beta_{1}<x_{e q}<\frac{1}{n}\beta $$

2-value equilibrium In the case where the players were initially in a 2-value equilibrium, we have the following theorem, which we prove in AppendixE.

Theorem 5. In a NTEG that is in a state of 2-value equilibrium with player 1 playing x₁ and the other n 1 players playing x_eq, the introduction of a new player with benet-cost ratio does not change the value played by the other Pn players unlessi=1xi< or1< .

$$ x_{1} $$

$$ x_{e q}, $$

$$ \beta $$

$$ \dot{\sum_{i=1}^{n}x_{i}}<\beta $$

$$ \beta_{1}<\beta $$

We now consider how the utility of each player changes following the introduction of a new player. If the new player contributes a strictly positive eort and the value played at equilibrium stays unchanged for the other players it is clear that the introduction of a new player increases everyone’s utility as it increases the reliability of the system without changing anyone’s cost. When the equilibrium is changed, if only one player (player 1) leaves the system, then this is simply a player replacement and the reliability of the system stays the same. Player 1 increases their utility in this case as the reliability of the system is the same as before but their cost is now zero.

However, from the proof of Theorem4we have that a new player could potentially incentivise more than one player to decrease their contribution. Lemma1 tells us that this means that the players would potentially need many iterations before reaching a new equilibrium if they reach one, where only one or two values are played. Although it could be presumed that a new player joining should increase the reliability of the system, this result shows that if one or more players have to decrease their contributions then it is not clear that the nal reliability of the system will be higher with n + 1 player than with the original n players. We study simulations of equilibrium disruption in Section5and leave a rigorous study of the outcome of the new game as an open problem.

Player leaving the game In the case where a player leaves the game, we have the following theorem, which we prove in AppendixF.

Theorem 6. In the NTEG, if the n players are playing a 1 value Nash equi- librium, the removal of a new player with benet-cost ratio_idoes not change the value played by the other players.

$$ \beta_{i} $$

If other contributions stay unchanged, a player leaving the system decreases the reliability of the system as it renders it more centralised. The utilities of the remaining players will therefore always decrease in this case.

4.2 Deviation from an equilibrium

We now consider the case where one player (player k) deviates from the equilibrium and changes their contribution to x_k0. We are concerned with the response of the n 1 other players and what new equilibrium is reached, regardless of whether it will be the best strategy for player k to keep their value x_k0in the new equilibrium (i.e., player k may be irrational). We prove the following theorem in AppendixG

$$ x_{k_{0}} $$

$$ x_{k_{0}} $$

Theorem 7. In the NTEG with n players contributing the same value x_eqat the equilibrium, the deviation of player k with benet-cost ratio_kto a new value x_k0does not change the value played by the other players unless x_k0> x_eq.

$$ x_{e q} $$

$$ \beta_{k} $$

$$ x_{k_{0}} $$

$$ x_{k_{0}}>x_{e q}. $$

In the 2-value equilibrium, the results are very similar. We prove the following theorem in AppendixH.

Theorem 8. In the NTEG with n players playing a 2-value equilibrium where players 2 to n play the same value x_eqat the equilibrium, the deviation of player k with benet-cost ratio_kto a new value x_k0changes the value played by the other players unless in the specic case where player 1 is deviating to a new value xk06= x₁ and for all 2 j n we have (1) xk0< xeq(2)j> (n 2)xeq+ xk0+ max(xk0;xk0) and (3) (n 2)xk0+ xk0< 2.

$$ x_{e q} $$

$$ \beta_{k} $$

$$ x_{k_{0}} $$

$$ x_{k_{0}}\neq x_{1} $$

$$ 2,j,\leq,n $$

$$ ()\:x x_{k_{0}}:<:x_{\mathit q}\ \not(\ )\ \beta_{j}:>:(n\ \mathrm-\ 2)x_{\mathit{e e q}}:+ $$

$$ x_{k_{0}}+\operatorname*{m a x}(x_{k_{0}},x_{k_{0}}) $$

$$ \ (\partial),(n-2)x_{k_{0}}+x_{k_{0}}<\beta_{2} $$

In the case where the players do not change their equilibrium after an irrational player deviates (i.e., xk0< xeq) the utility of players will decrease as reliability will be lower for the same costs and contributions.

$$ \ \(\mathrm{i.e.,},{x_{k_{0}}}<,{x_{e q}}) $$

In the other case, before the other players can adjust their contribution, their utility will also decrease, and in some realistic cases, players may not be able to change their contribution as we discuss in Section6. This is an undesirable eect dened as immunity by Abraham et al. [2] in the context of distributed systems where one or more irrational players can negatively impact the utility of rational players. If players can change their contributions, the reliability functions could go up or down depending on the new value x_eqand the benet-cost of other players (i.e., whether they will free ride).

$$ x_{e q} $$

After the deviation from player k, we have from Condition10that each i (n 2)xeq player i such that x^k0chaⁿges their contribution to x^i;new= 2 _ix_k0(n 2)x_eqor zero if that value is negative, and each player i such that i (n ²)x^eq x_k⁰chaⁿges their contribution to x^k0. 2

$$ x_{k_{0}};\geq;\frac{\beta_{i}-(n-2)x_{\mathrm{}{e q}}}{2} $$

$$ x_{i,\mathrm{n e w}},= $$

$$ \beta_{i}-x_{k_{0}}-\big(n-2\big)x_{e q} $$

$$ \ {x{k_{0}}}\leq\textstyle\frac{\beta_{i}-(n-2)x_{e q}}{2} $$

$$ x_{k_{0}} $$

In Lemma1, we showed that if there exists two contributing rational players whose contributions are strictly less than max_j(x_j), then those players must have the same benet-cost ratio. This is true regardless of the existence of an irrational player. Since we assume that all the benet-cost ratios are dierent, this means that there can be at most one rational player playing strictly less than the maximum value x_M. According to the strategy dened in Condition10, no rational player is incentivised to play more than max_j(x_j). Thus, even after players adjust their contributions we will still have max_j(x_j) = x_k0and, following the deviation, the bulk of the players will align with the deviating players or free ride, except for one rational player. By setting x_k0high enough, the deviating player could ensure that many players switch to free-riding, which could pose a threat to the system if it facilitates one party taking control of the system (e.g., a 51% attack).

$$ \mathrm{m a x}{j}(x{j}) $$

$$ x_{M} $$

$$ x _ {j} \left(x _ {j}\right) $$

$$ {bf_{j}}(x_{j})=x_{k_{0}} $$

$$ x_{k_{0}} $$

4.3 Non-myopic players

Motivated by Brunjes et al. [13], we consider non-myopic players deviating from the equilibrium. The utility function of such players accounts for the eects an action will have on the other players, unlike Nash equilibria that consider the best response of players given that the other players’ strategies are xed.

In the previous section, we have seen that a player deviating from the equilibrium may disrupt the best response of the other players and lead to a new equilibrium. In a Nash equilibrium, assuming that other players keep their contribution unchanged, deviating means that one’s utility is reduced, but this does not account for the possibility of a new equilibrium being reached. A new equilibrium (if reached) may be a better equilibrium for the deviating player if their utility is higher in the new equilibrium.

Does a non-myopic player have incentives to deviate from the equilibria we have derived? We have established that a condition to disrupt the equilibrium is to change one’s contribution to a value x_k0> x_eq. We have also observed that by setting this value high enough, the deviating player can cause some players to free ride. In a NTEG without a reward, the new equilibrium would, therefore, have fewer contributing players with greater contributions. In a 1-value equilibrium, this would mean we have F (x₁;:::;xn) = nnew< n where nnewis the new number of contributing players. However, because x_k0> x_eq, the cost will be higher and this strategy is therefore not rational as the new equilibrium results in less utility for the deviating player and the other players.

$$ x_{k_{0}}>x_{e q} $$

$$ F(x_{1},\ldots,x_{n}),=,n_{\mathrm{n e w}},<,n $$

$$ n_{\mathrm{n e w}} $$

$$ x_{k_{0}}:>:x_{e q}, $$

In a NTEG with reward, however, fewer players implies a greater share of rewards. Thus a non-myopic player may be incentivised to deviate from an existing equilibrium to reach a new one with fewer contributing players.

This suggests that a xed proportional reward may increase centralisation. Designing a protocol with a variable reward such that players would earn similar revenue regardless of the number of players is an open problem due to the pseudonymous nature of systems like cryptocurrencies. Another alternative is to rely on a xed reward but design the system such that it is not possible to increase one’s contribution, as in proof-of-personhood schemes [12].

4.4 Coalition-resistance

A group of miners may decide to form a coalition if this increases their expected gain, even if doing so centralises the system. In this case a coalition is equiv- P alent to having one player contributing X =_i2[i;:::;i]x_ifor all the players 1 c (i₁;:::;i_c) in the coalition instead of having each contributing separately. Because the sum of the eorts stay the same but the maximum eort potentially increases, F (x₁;:::;x_i1;:::;x_ic;:::;x_n) F (x₁;:::;X;:::;x_n). Thus, the utility of decentralisation conscious players decreases when they form a coalition i.e., they are not incentivised to create coalitions.

$$ X boldsymbol{\ {}}=\sum_{i\in[i_{1},\ldots,i_{c}]}_{\boldsymbol{}}x_{i} $$

$$ (i_{1},\ldots,i_{c}) $$

$$ F(x_{1},\ldots,x_{i_{1}},\ldots,x_{i_{c}},\ldots,x_{n})\geq F(x_{1},\ldots,X,\ldots,x_{n}) $$

5 Dynamics Of Decentralisation Conscious Players

As we have shown, there are many possible equilibria, each corresponding to dierent equilibrium values. How an equilibrium is reached i.e., how quickly and how many players reach it, as well as which equilibrium value is reached could depend on several factors that we look at in this section.

(a)

(b)

Fig. 1: Without constraints on contribution changes players can reach an equilibrium (Figure1a) but may also oscillate indenitely (Figure1b).

Methodology Using a Python script, we simulate the NTEG where each player computes their best strategy at each time unit. By iterating over multiple time units we observe how players (simultaneously) re-evaluate their contributions based on the eort of other players in the previous time unit. The scenarios we simulate are not exhaustive but highlight interesting behaviour, the benet-cost ratios were chosen randomly within a range.

Random initial values To observe how an equilibrium is reached, we initialize a NTEG with 10 players to which we assign random initial values (contributions, costs, benets) and look at how they change their contributions until an equilibrium is reached. (The same initial contributions and benet-cost ratios are used for every simulation.) According to the strategy dened by Equation10, no decentralisation conscious player is incentivised to contribute more than other players hence the player that has the maximum contribution in step 1 of the game (set by nature’s move) will be reducing their contribution in the next step. On the other hand, other players with a high enough benet-cost ratio will be incentivised to increase their contributions to the maximum value in step two of the game.

Under ideal conditions i.e., when the maximum contribution x_maxis such that nxmax< mini i, the equilibrium is reached after a few steps. Players with the greatest benet-cost ratios align their contributions to the maximum value (except perhaps for one of them, resulting in a 2-value equilibrium) while the remaining players free ride, as shown in Figure1a.

$$ x_{\mathrm{m a x}} $$

$$ n x_{\operatorname*{m a x}}<\operatorname*{m i n}{i}\beta{i} $$

In other cases, as shown in Figure1b, some players may keep oscillating indenitely. For these players, it must be the case thatj< nxeq, else playing xeq at the same time as other players will be their best strategy and an equilibrium will be reached. Thus whenever everyone is playing x_eqat one time unit, they decrease their contributions to_jnx_eqin the next step. However, after other oscillating players have also decreased their contributions, it is now the best strategy to go back to x_eq, and so on. This is due to players being myopic, not anticipating that other players will increase their contributions at the same time as them.

$$ \beta_{j}<n x_{e q}. $$

$$ x_{e q} $$

$$ x_{e q} $$

$$ \beta_{j}-n x_{e q} $$

$$ x_{e q}, $$

(a) = 0*:* 1

$$ \varDelta=0.1 $$

(b) = 0*:* 3

(c) = 0*:* 5

$$ \varDelta=0.5 $$

Fig. 2: Oscillations disappear with constraints on contribution changes. The speed at which equilibria are reached depends on the constraints (slower with = 0*:* 1, faster with = 0*:* 5), as do the type of equilibria (1-value with = 0*:* 1, 2-value = 0*:* 3 or 0*:* 5) and equilibrium value (greater with = 0*:* 3 or 0*:* 5).

$$ \varDelta=0.1 $$

$$ \Delta = 0. 5) $$

$$ \varDelta=0.1 $$

$$ \varDelta=0.3 $$

$$ \varDelta=0.3\ \mathrm{o r}\ 0.5) $$

Constraints on the rate of change of contributions. To avoid the unrealistic case where players oscillate forever we constrain the change in each player’s contribution from one time unit to another by a factor. This dampens the oscillations and allows players to converge to an equilibrium.

Because aects how quickly players can converge to an equilibrium, the equilibrium that is reached varies with. For example, in the case where = 0*:* 1 participants are allowed to change their contributions by at most 10% from one time unit to another and a 1-value equilibrium is reached, as shown in Figure2a. When = 0*:* 3 or = 0*:* 5, a 2-value equilibrium is reached, as shown in Figures2band2c. Keeping this in mind we will, however, stick to the = 0*:* 1 case in most of the simulations that follow for simplicity as the overall player behaviours i.e., players increasing their contribution or free-riding are the same although the nal equilibrium diers.

$$ \Delta $$

$$ \measuredangle $$

$$ \varDelta=0.1 $$

$$ \varDelta=0.3 $$

$$ \varDelta=0.5 $$

$$ \varDelta=0.1 $$

We have also computed the dierent values of the reliability in each case but did not observe any clear pattern. Whether there is a pattern that is not clearly observable is left as an open problem.

Not only is a constraint on the change in the eort of players useful for them to eciently converge to an equilibrium, it is also realistic. Players in real life are likely to understand the adverse eects of over correcting and are also likely to have constraints on how much they can change their eort (at least upwards) due to the cost of doing so. We discuss this constraint further in the next section, in relation to resource scarcity.

Moreover, every player updating their contributions at the same time is not a realistic assumption either. Bounding the change of contribution of each player from one step to another also helps get closer to a continuous time model.

Constraints on total eort Another constraint that can be implemented is a limit on the overall change in the eort of all players i.e., the total eort. This models the constraint that the stock of resources used to contribute eort (e.g., new hardware) may be limited at any point in time. Figure3ashows that in

(a) = 0*:* 1

$$ \varDelta=0.1 $$

(b) + = 0*:* 05, = 0*:* 4

$$ \varDelta_{+}=0.05,,\varDelta_{-}=0.4 $$

(c) + = 0*:* 4, = 0*:* 05

$$ \Delta_{+}=0.4. $$

Fig. 3: Constraining the total eort can increase free-riding and reduce equilibrium values (Figure2a), as can reductions in contributions being easier than increases (Figures3band3c).

$$ \varDelta_{-}=0.05 $$

this case, some players may not be able to change their contribution enough to converge to the equilibrium and, therefore, switch to free riding.

Since it is usually easier to reduce one’s contribution than to increase it, we also simulate the game with dierent constraints on the increase and the decrease of contributions from one step to another. We see in Figures3band3cthat a 2-value equilibrium is reached, although the relative constraints on increasing and decreasing contributions result in dierent equilibrium values. The value played by the bulk of the player x_eqis higher when there is a greater constraint on the increase of contributions than on the decrease. This is because players can more rapidly reach the new maximum value. As a consequence, the second value played at the equilibrium is smaller.

$$ x_{e q} $$

Disruptions to an equilibrium A new player joining the game when it is in a 1-value equilibrium (which happens according to the conditions dened in Theorem4) can lead to a new equilibrium being reached after a few steps, as shown in Figure4ain the case of a strong constraint.

When an equilibrium is disrupted by a player deviating from the equilibrium, players that increase their contribution to contribute more eort than the equilibrium value incentivise other decentralisation conscious players to free ride or increase their eort to reach a new equilibrium value if it is allowed by their benet-cost ratio. This is shown in Figure4b, in the case of a strong constraint.

6 Discussion

6.1 The role of decentralisation conscious players

Our model and choice of NTE function shows that decentralisation conscious players can help maintain a decentralised system. However, as Theorems7and8 show, decentralisation conscious players only ever increase their eort in response to another player increasing their contribution at the cost of decentralisation. They maintain decentralisation within the constraints of their benet-cost ratio

(a) = 0*:* 1, a new player (b) = 0*:* 1, a player devijoins ates

$$ \Delta=.0 $$

$$ \Delta = 0. 1 $$

Fig. 4: Disruptions to an equilibrium due to a new player joining or a player deviating lead to new equilibriums.

but ignore players that free ride after their benet-cost ratio no longer allows them to contribute.

Because decentralisation conscious players can only maintain a pre-existing level of decentralisation and can be leveraged by selsh players to implement a minimum benet-cost ratio that acts as a form of gate-keeping against players with lower benet-cost ratios, there is a distinction between decentralisation conscious players and altruistic players that operate regardless of their benet-cost ratio. This suggests that new mechanisms dictating how eort is contributed or rewarded may be needed for players to have rational ways of increasing decentralisation outside of purely altruistic behaviour.

6.2 Modelling constraints

Resource scarcity Players contribute based on their benet-cost ratios and, as we have seen in Section5, equilibria depend on the rate of change of contributions. An implicit assumption made by our model is that a player can contribute more (at a cost) should they wish to do so but this may not be possible. For example, cryptocurrency mining hardware has suered from shortages that forced buyers to obtain hardware at signicant premiums and logistical diculties [28]. When resources are unobtainable, it can become impossible to contribute more or continue contributing the same amount (if resources must be replaced), causing involuntary deviations from otherwise rational strategies.

If it is impossible to acquire the resources to contribute, the system will rely on players having a high valuation of the system. Contributors to systems like Tor [25] operating nodes at a loss may demonstrate this but in the case of cryptocurrencies new miners are less likely to have a high valuation of the system because they are unlikely to have a stake in it, unlike miners that have accumulated rewards. Miners in cryptocurrencies that are more centralised due to the high practical costs of mining can, therefore, form an eective oligopoly [16,5].

Can we avoid issues of resource scarcity? One way of avoiding the problematic reliance on resources with variable stock (e.g., stake, hardware) is to opt for mechanisms like proof-of-personhood [12], which is equally distributed (\1 person = 1 vote") and maximizes the NTE, although this has other issues to overcome.

Geographical and political decentralisation Because players contribute based on their benet-cost ratios so the geographical distribution of players will matter if costs vary with location. For example, cryptocurrency mining is concentrated in the few areas where mining is most protable.

Markets are also aected by political power and changes in regulations. China controlled 65% of Bitcoin’s hashpower in 2019 [17] but following new Chinese regulations [8] the share of hashpower in the US has grown due to political stability with respect to Bitcoin mining [3]. The impact of markets and political power on decentralisation adds complexity and uncertainty in models, which may motivate decentralised systems less reliant on other markets e.g., proof-ofstake (based on the cryptocurrency’s native tokens) or proof-of-personhood may be easier to reason about than proof-of-work (energy and hardware markets).

Incomplete and unequal information Our model has assumed perfect information at each step with players changing their contributions based on this information, but players could hide information such as the stock of unused resources they have at their disposal. Attacks such as selsh mining in proof-of-work cryptocurrencies [15] are based on abusing information asymmetry, as are hostile takeovers which use previously unused but available mining capacity [10]. There is also an inherent delay in information propagating through a network. This may result in dierent equilibria as players adapt their contributions based on the information they receive at a point where it may no longer be accurate.

How much this matters is hard to determine. Attacks such as selsh mining have seldom been observed, and eort rarely varies across short time periods. (See the Bitcoin hashrate distribution over short time periods, even if the larger trend is growth [1].) This may be due to issues like acquiring the additional resources needed to contribute more eort, but it may also be to maintain a level of decentralisation as our model suggests miners might do.

6.3 Related Work

There is an important literature on modelling incentives in cryptocurrencies through renements of Nash Equilibria that has been systematized [6]. Although the types of players and games considered vary across papers, none of the papers surveyed (except Varian’s paper [27]) consider the reliability of the system.

Varian’s system reliability paper [27] has previously been extended by Grossklags et al. [18] in the context of investments in security and insurance. Grossklags et al. [19] have also applied Varian’s model to study the dierence between expert and naive players in security games to quantify the impact of information. In this work, we have instead focused on decentralisation and introduced the NTEG, which extends Varian’s model in another direction.

7 Conclusion

We have proposed a model for decentralisation conscious players based on the NTE function we have introduced. The Nash equilibria show what could be expected from such players. Using simulations we have also considered how players may reach an equilibrium, including after disruptions. There is a variety of possibilities for future work and opportunities to apply our model to specic cases. This includes cases with valuations of the system which are hard to precisely dene e.g., ideological commitment, as well as cases with very explicit valuations and dependencies on rewards but complex nancial optimization such as cryptocurrencies. Protocol designers who wish to incorporate rational players, as opposed to honest players, but also wish to incorporate the reliability of the system in addition to short-term rewards could use the NTE function.

Acknowledgments

Alexander Hicks was partially supported by Protocol Labs for this work.

References

1.pools-timeseries,https://www.blockchain.com/charts/pools-timeseries 2.Abraham, I., Dolev, D., Gonen, R., Halpern, J.: Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In: Proceedings of the twenty-fth annual ACM symposium on Principles of distributed computing. pp. 53{62 (2006) 3.Allison, I.: Long in China’s shadow, the US is becoming a Bitcoin mining power again (November 2020),https://www.coindesk.com/ us-becoming-bitcoin-mining-power-again 4.Anderson, R.: Security engineering: a guide to building dependable distributed systems. John Wiley & Sons (2020) 5.Arnosti, N., Weinberg, S.M.: Bitcoin: A natural oligopoly. arXiv preprint arXiv:1811.08572 (2018) 6.Azouvi, S., Hicks, A.: Sok: Tools for game theoretic models of security for cryptocurrencies. arXiv preprint arXiv:1905.08595 (2019) 7.Bano, S., Sonnino, A., Al-Bassam, M., Azouvi, S., McCorry, P., Meiklejohn, S., Danezis, G.: Sok: Consensus in the age of blockchains. In: Proceedings of the 1st ACM Conference on Advances in Financial Technologies. pp. 183{198 (2019) 8.Baydakova, A.: China’s crypto miners struggle to pay power bills as regulators clamp down on OTC desks (November 2020),https://www.coindesk.com/ chinese-miners-struggle-to-pay-for-electricity 9.Bissias, G., Bohme, R., Thibodeau, D., Levine, B.N.: Pricing security in proof-ofwork systems. arXiv preprint ar Xiv:2012.03706 (2020) 10.Bonneau, J.: Hostile blockchain takeovers (short paper). In: International Conference on Financial Cryptography and Data Security. pp. 92{100. Springer (2018) 11.Bonneau, J., Miller, A., Clark, J., Narayanan, A., Kroll, J.A., Felten, E.W.: Sok: Research perspectives and challenges for Bitcoin and cryptocurrencies. In: 2015 IEEE symposium on security and privacy. pp. 104{121. IEEE (2015)

12.Borge, M., Kokoris-Kogias, E., Jovanovic, P., Gasser, L., Gailly, N., Ford, B.: Proofof-personhood: Redemocratizing permissionless cryptocurrencies. In: 2017 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW). pp. 23{ 26. IEEE (2017) 13.Brunjes, L., Kiayias, A., Koutsoupias, E., Stouka, A.P.: Reward sharing schemes for stake pools. arXiv preprint arXiv:1807.11218 (2018) 14.Chen, X., Papadimitriou, C., Roughgarden, T.: An axiomatic approach to block rewards. In: Proceedings of the 1st ACM Conference on Advances in Financial Technologies. pp. 124{131 (2019) 15.Eyal, I., Sirer, E.G.: Majority is not enough: Bitcoin mining is vulnerable. In: International conference on nancial cryptography and data security. pp. 436{454. Springer (2014) 16.Gencer, A.E., Basu, S., Eyal, I., Van Renesse, R., Sirer, E.G.: Decentralization in Bitcoin and ethereum networks. In: International Conference on Financial Cryptography and Data Security. pp. 439{457. Springer (2018) 17.Godbole, O.: Highest in 2 years: 65% of Bitcoin hash power is in China, report nds (December 2019),https://www.coindesk.com/ highest-in-2-years-65-of-bitcoin-hash-power-is-in-china-report-nds 18.Grossklags, J., Christin, N., Chuang, J.: Secure or insure? a game-theoretic analysis of information security games. In: Proceedings of the 17th international conference on World Wide Web. pp. 209{218 (2008) 19.Grossklags, J., Johnson, B., Christin, N.: When information improves information security. In: International Conference on Financial Cryptography and Data Security. pp. 416{423. Springer (2010) 20.Hajdarbegovic, N.: Bitcoin miners ditch ghash.io pool over fears of 51% attack (Apr 2014),https://www.coindesk.com/bitcoin-miners-ditch-ghash-io-pool-51-attack 21.Judmayer, A., Stifter, N., Zamyatin, A., Tsabary, I., Eyal, I., Gazi, P., Meiklejohn, S., Weippl, E.R.: Pay-to-win: Incentive attacks on proof-of-work cryptocurrencies. IACR Cryptol. ePrint Arch. 2019, 775 (2019) 22.Kwon, Y., Liu, J., Kim, M., Song, D., Kim, Y.: Impossibility of full decentralization in permissionless blockchains. In: Proceedings of the 1st ACM Conference on Advances in Financial Technologies. pp. 110{123. AFT ’19, ACM, New York, NY, USA (2019).https://doi.org/10.1145/3318041.3355463,http://doi.acm.org/ 10.1145/3318041.3355463 23.Neudecker, T., Hartenstein, H.: Short paper: An empirical analysis of blockchain forks in Bitcoin. In: International Conference on Financial Cryptography and Data Security. pp. 84{92. Springer (2019) 24.Roughgarden, T.: Selsh routing and the price of anarchy, vol. 174. MIT press Cambridge (2005) 25.Syverson, P., Dingledine, R., Mathewson, N.: Tor: The second generation onion router. In: Usenix Security. pp. 303{320 (2004) 26.Troncoso, C., Isaakidis, M., Danezis, G., Halpin, H.: Systematizing decentralization and privacy: Lessons from 15 years of research and deployments. Proceedings on Privacy Enhancing Technologies 2017(4), 404{426 (2017) 27.Varian, H.: System reliability and free riding. In: Economics of information security, pp. 1{15. Springer (2004) 28.Wong, J.I.: Ethereum miners are renting Boeing 747s to ship graphics cards and AMD shares are soaring (July 2017),https://qz.com/1039809/ amd-shares-are-soaring-ethereum-miners-are-renting-boeing-747s-to-ship-graphics-cards-to-mines/

http://doi.acm.org/10.1145/3318041.3355463 10.1145/3318041.3355463

A Proof of Theorem1

To determine player 1’s best strategy, we rst study the continuous function x₁ 7! u₁(x₁) for a xed x₂ and try to nd its global maximum. There are two cases to consider, depending on whether x₁ x₂ or x₁ > x₂.

$$ x_{1}\mapsto u_{1}(x_{1}) $$

$$ x_{2} $$

$$ x_{1}\leq x_{2} $$

x1 +x2 du1 v1 du1 If x₁ < x₂, we have u₁ = ln()v₁ c₁x₁ and = c₁, so 0 x2 _dx¹ x1 +x2 dx1 i Condition11holds.

$$ x_{1}>x_{2} $$

$$ x_{1}<x_{2} $$

$$ u_{1}=\ln\bigl(\frac{x_{1}+x_{2}}{x_{2}}\bigr)v_{1}-c_{1}x_{1} $$

$$ \frac{d u_{1}}{d x_{1}}=\frac{v_{1}}{x_{1}+x_{2}}!-!c_{1},\ 8! $$

$$ x_{1}+x_{2}\leq\beta_{1} $$

(11)

x1 +x2 du1 1 1 If x₁ > x₂, we have u₁ = ln()v₁ c₁x₁ and = v₁() c₁, _x1 dx¹ _x1 ₊x_{2 x}¹ _du1 so < 0. _dx1

$$ x_{1}>x_{2} $$

$$ u_{1}=\operatorname{l n}(\textstyle{\frac{x_{1}+x_{2}}{x_{1}}})v_{1}-c_{1}x_{1} $$

$$ \frac{d u_{1}}{d x_{1}}<0. $$

$$ \frac{d u_{1}}{d x_{1}}=v_{1}\big(\frac{1}{x_{1}+x_{2}}-\frac{1}{x_{1}}\big)-c_{1} $$

We can, therefore, dene player 1’s strategy as follows.

1.If1< x₂ then (from condition11) u₁ is a decreasing function and player 1’s best strategy is to play x₁ = 0.

$$ \beta_{1}<x_{2} $$

$$ u_{1} $$

$$ x_{1}=0 $$

2.If x₂₁then (from condition11) u₁ is increasing up to min(x₂;₁x₂) so there are two cases to consider.

$$ x_{2}\leq\beta_{1} $$

$$ u_{1} $$

$$ \operatorname*{m i n}(x_{2},\beta_{1}-x_{2}) $$

1 (a)If x₂¹x₂ i.e., if x₂¹, then condition (11) is always satised 2 for x₁ x₂ and hence player 1 best strategy is to play x₁ = x₂. When x₁ > x₂ u₁ decreases so player 1 maximizes u₁ by playing x₂.

$$ x_{2}\leq\beta_{1}-x_{2}\mathrm{{\ i.e} $$

$$ \textstyle{x_{2}\leq\frac{1}{2}\beta_{1}} $$

$$ x_{1}\leq x_{2} $$

$$ x_{1}=x_{2} $$

$$ x_{1}>x_{2}\ u_{1} $$

$$ u_{1} $$

$$ x_{2}. $$

1 (b)If x₂ > 1x₂ or equivalently if1< x₂1: then player 1 best strat- 2 egy is to play x₁ =₁x₂ (after which u₁ starts decreasing according to condition (11)).

$$ x_{2}>\beta_{1}!-!x_{2} $$

$$ {\textstyle\frac{1}{2}}\beta_{1}<x_{2}\leq\beta_{1}. $$

$$ x_{1}=\beta_{1}-x_{2} $$

$$ u_{1} $$

The same analysis can be repeated for u₂, giving the same results. Therefore, 1 there exist innite equilibria where x₁ = x₂ = x^eqand x_eqmin(¹;₂). We 2 now show that these are the only equilibria of the game.

$$ u_{2}, $$

$$ x_{1}=x_{2}=x_{e q} $$

$$ x_{e q}\leq\frac{1}{2}\operatorname*{m i n}(\beta_{1},\beta_{2}) $$

If one of the contributions, say x₂, is zero, then we are in case (2a) of the strategy for player 1 and their best response is also zero. Thus, we have x₁ = 1 x₂ = x^eqsuch that x min(¹;²). 2

$$ x_{2} $$

$$ x_{1},= $$

$$ x_{2}=x_{e q} $$

$$ x\leq{\textstyle\frac{1}{2}}\operatorname*{m i n}(\beta_{1},\beta_{2}) $$

For the rest of this proof, we assume that x₁;x₂ > 0. Proceeding by contradiction, we assume that there exists a Nash equilibrium (x₁₀;x₂₀) for which x₂₀6= x₁₀. Since x₂₀6= x₁₀and x₁₀> 0 by assumption, this means we are in case (2b) of player 1’s strategy and player 1 maximizes u₁ when x₁ =₁x₂₀= x₁₀.

$$ x_{1},x_{2},>,0 $$

$$ (x_{1_{0}},x_{2_{0}}) $$

$$ x_{2_{0}}\neq x_{1_{0}} $$

$$ x_{2_{0}}\neq x_{1_{0}} $$

$$ x_{1_{0}}>0 $$

$$ u_{1} $$

$$ x_{1}=\beta_{1}-x_{2_{0}}=x_{1_{0}} $$

$$ \beta_{2}-x_{1_{0}}=x_{2_{0}} $$

Similarly, we have₂x₁₀= x₂₀. Solving this system of two equations gives us x₁₀+ x₂₀=₁=₂. So unless₁=₂, we have a contradiction.

$$ x_{1_{0}}+x_{2_{0}}=\beta_{1}=\beta_{2} $$

$$ \beta_{1}=\beta_{2} $$

If¹=²= v=c, then we have x₁⁰+x₂⁰= v=c. Again, proceeding by contra- 1 1 diction, we assume that x₁0> v=c. This implies that x₂0< v=c, implying that 2 2 we are in case (2a) of player’s 1 strategy and thus that player 1’s best response 1 is x₁0= x₂0. The analysis is the same if x₁0< v=c, applied to player 2. This 2 proves that players contribute the same at the equilibrium.

$$ x_{1_{0}}!+!x_{2_{0}}=v/c $$

$$ \beta_{1}=\beta_{2}=v/c $$

$$ x_{1_{0}}>{\textstyle\frac{1}{2}}v/c $$

$$ x_{2_{0}}<\textstyle{\frac{1}{2}}v/c. $$

$$ (2\mathrm{a}) $$

$$ x_{1_{0}}\ x_{2_{0}} $$

$$ x_{1_{0}},<,\textstyle{\frac{1}{2}}v/c. $$

B Proof of Theorem2

The analysis of x₁ 7! u₁(x₁) for (x₂;:::;x_n) xed is similar to the analysis done in the two player case.

$$ x_{1}\mapsto u_{1}(x_{1}) $$

$$ (x_{2},\ldots,x_{n}) $$

Pn n x₁+i=2xi du₁ If x₁ < maxi=2(xi), we have u₁ = ln()v₁ c₁x₁ and = ^m _dx1 P v1 du_{1 n} c₁. Hence, 0 i Condition12holds. i=1xi dx₁

$$ x_{1};<;\mathrm{m a x}{i=2}^{n}(x{i}) $$

$$ \ u_{1};=;\operatorname{l n}({\textstyle\frac{x_{1}+\sum_{i=2}^{n}x_{i}}{m}})v_{1}\mathrm-_{1}x_{1} $$

$$ {\frac{d u_{1}}{d x_{1}}}
$$

$$ \frac{v_{1}}{\sum_{i=1}^{n}x_{i}}-c_{1} $$

$$ \frac{d u_{1}}{d x_{1}}\geq0 $$

$$ \sum_{i=1}^{n}x_{i}\leq\beta_{1} $$

(12)

Pn n x₁+i=2xi du₁ 1 If x₁ > max (x), we have u₁ = ln()v₁ c₁^x₁ = v₁(^{Pn i=2} i ^x1 d^x1 xⁱ i=1 1 du¹ ) c1, so < 0. x₁ ^dx₁

$$ x x_{1}>\mathrm{m a x}{i=2}^{n}(x{i}) $$

$$ u_{1}=\ln(\frac{x_{1}+\sum_{i=2}^{n}x_{i}}{x_{1}})v_{1}\ c_{1},-,c_{1}x_{1},\frac{d u_{1}}{d x_{1}}=v_{1}\big(\frac{1}{\sum_{i=1}^{n}x_{i}}-}end{{} $$

As in the two player case, we can establish that player 1’s best strategy for a xed (x₂;:::;x_n) is as follows.

$$ \textstyle\frac{1}{x_{1}}\big)-c_{1},:\ \mathtt{S0}\ \frac{d u_{1}}{d x_{1}}<0. $$

$$ (x_{2},\ldots,x_{n}) $$

Pⁿ n n 1.If maxⁱ⁼²(xⁱ) + Pⁱ⁼²x^{i 1}, contribute maxⁱ⁼²(xⁱ). This is because we n n will always have_i⁼¹x_i ¹as long as x₁ max_i=2(x_i), thus u₁ increases n as x₁ increases up to max_i=2(x_i) and then decreases. The best response is n thus x₁ = maxi₌₂(x_i). P P P

$$ \textstyle\operatorname*{m a x}{i=2}^{n}(x{i})+\sum_{i=2}^{n}x_{i}\leq\beta_{1} $$

$$ \mathrm{n a x}{i=2}^{n}(x{i}) $$

$$ \textstyle\sum_{i=1}^{\prime\prime}x_{i}\leq\beta_{1} $$

$$ x_{1}\leq\ \ \mathrm{m a x}{i=2}^{n}(x{i}) $$

$$ u_{1} $$

$$ x_{1} $$

$$ x_{1}=\mathrm{m a x}{i=2}^{n}(x{i}) $$

$$ \mathrm{n a x}{i=2}^{n}(x{i}) $$

n n n n 2.Ifi=2xi< 1< maxi=2(xi) +i=2xi, contribute1 i=2xi. This is because (from Condition12) u₁ is increasing up to that point, then decreasing. P

$$ \textstyle\sum_{i=2}^{n}x_{i}\ {<}\ \beta_{1}\ {<}\ \operatorname{m a x}{i=2}^{n}(x{i})+\sum_{i=2}^{n}x_{i}, $$

$$ \beta_{1}-\textstyle\sum_{i=2}^{n}x_{i} $$

$$ u_{1} $$

ⁿ 3.Ifⁱ⁼²x^{i 1}then u₁ is decreasing and thus player 1’s best response is to contribute nothing: x₁ = 0.

$$ \textstyle\sum_{i=2}^{n}x_{i}\geq\beta_{1} $$

$$ u_{1} $$

$$ x_{1}=0 $$

The best strategy of every other player is derived in the same way.

It is straightforward to show that for every contributing player, the following holds at the equilibrium.

$$ \forall i\in[1,n]:;\sum_{j=1}^{n}x_{j}\leq\beta_{i} $$

(13)

Additionally, from the strategy dened above, we have that the case where players i + 1 to n (for any 1 i n 1) contribute the same value x such that 1 ^{1 i}xⁱ⁺¹aⁿd others free-ride is a Nash equilibrium. All the players n i n i i + 1 to n are in case (1) of their strategies and thus contribute x whereas all the players 1 to i are in case (3) and contribute zero. It is straightforward that these are the only type of equilibria that exist where all contributing players contribute the same value.

$$ 1\leq i\leq n-1, $$

$$ \textstyle\frac{1}{n-i}\beta_{i}\leq x\leq\frac{1}{n-i}\beta_{i+1} $$

$$ i+1 $$

Now, assume that there exist at least two contributing players i₁ and i₂ who contribute two values x_i1and x_i2at the equilibrium such that x_i16= x_i2. Without loss of generality we assume xi1< xi2. We start by showing that for every other contributing player i, their equilibrium contribution x_iis equal to x_i2. We show this by contradiction: we assume that x_i6= x_i2.

$$ i_{1} $$

$$ x_{i_{1}} $$

$$ i_{2} $$

$$ x_{i_{2}} $$

$$ x_{i_{1}}\neq x_{i_{2}} $$

$$ x_{i_{1}}<x_{i_{2}} $$

$$ x_{i} $$

$$ x_{i}\neq x_{i_{2}}. $$

$$ x_{i_{2}} $$

If xi< xi2, then xi< maxj6=ixjso we must be in case (2) of player i’s strategy P dened above (xi> 0 by assumption). We conclude that xi=i j6=ixj, wh_ich PnP tells us that_i=j=1xj. In a similar way, we have that x_i1=_{i1 j6=i}x_j P₁ n and thus_i1=_j=1x_j=_i, so players i₁ and i have the same benet-cost ratio which contradicts our assumption (Denition1). This also shows that there cannot exist two contributing players whose contributions are strictly less than

$$ x_{i}<\operatorname{m a x}{j\neq i}x{j} $$

$$ x_{i}<x_{i_{2}} $$

$$ (x_{i}>0 $$

$$ x_{i}=\beta_{i}{-}\ !{j\neq i}x{j} $$

$$ \beta_{i}=\sum_{j=1}^{n}x_{j} $$

$$ x_{i_{1}}=\beta_{i_{1}}-\sum_{j\neq i_{1}}x_{j} $$

$$ \beta_{i_{1}}=\sum_{j=1}^{n}x_{j}=\beta_{i} $$

$$ i_{1} $$ max_j(x_j) unless they have the same benet-cost ratio. (This will later be used as Lemma1.)

$$ _j(x(_j $$

It must be that xi> xi2, then xi2< maxjxjand the exact same analysis as above can be applied to x_i2. This leads us to_i2=_i1. This is a contradiction, meaning that x_ix_i2and, therefore, x_i= x_i2.

$$ x_{i}>x_{i_{2}} $$

$$ x_{i_{2}}<\operatorname*{m a x}{j}x{j} $$

$$ x_{i_{2}} $$

$$ \beta_{i_{2}}=\beta_{i_{1}} $$

$$ x_{i}=x_{i_{2}} $$

$$ x_{i}\leq x_{i_{2}} $$

Thus at the equilibrium there can exist only two dierent non-zero contributions possible.

We assume that there exists 1 players contributing x_i1and M = n 1 contributing x_i2. According to player i₁’s’ strategy (case (2)) we have the following.

$$ x_{i_{1}} $$

$$ M=n-1 $$

$$ x_{i_{2}} $$

$$ {dot i^{{}}{\ }^{1}{\mathrm S}^{{}}} $$

(14)

$$ x_{i_{1}}=\beta_{i_{1}}-M x_{i_{2}} $$

(15)

Because player i₁ is a contributing player, we have by assumption that x_i1> i1 0, which implies xi2<. We also have by assumption that xi1< xi2, which M i1 impliesi1Mxi2< xi2, which in turn implies < xi2. ⁿ

$$ i_{1} $$

$$ x_{i_{1}}> $$

$$ x_{i_{2}}<\frac{\beta_{i_{1}}}{M} $$

$$ x_{i_{1}}\mathbf{} $$

$$ \beta_{i_{1}}-M x_{i_{2}}<x_{i_{2}} $$

$$ \frac{\beta_{i_{1}}}{n}<x_{i_{2}} $$

According to condition12, applied to player i₂, we have that Mx_i2+x_{i1 i2}. Replacing the value of x_i1in this inequality leads to_{i1 i2}. We, therefore, i1 i1 i2 have < xi2<. n ^M M

$$ i_{2} $$

$$ M x_{i_{2}}{+}x_{i_{1}}\leq\beta_{i_{2}} $$

$$ x_{i1} $$

$$ \beta_{i_{1}}\leq\beta_{i_{2}} $$

$$ \frac{\beta_{i_{1}}}{n}<x_{i_{2}}<\frac{\beta_{i_{1}}}{M}\leq\frac{\beta_{i_{2}}}{M} $$

It is straightforward to verify that having one player with the smallest benetcost ratio play x_i1and the rest plays x_Mis a Nash equilibrium.

$$ x_{i_{1}} $$

$$ x_{M} $$

C Proof of Theorem3

With the addition of the reward, the utility function for player 1 is the following.

$$ u _ {1} \left(x _ {1}\right) = \left{ \begin{array}{l l} \ln \left(\frac {x _ {1} + x _ {2}}{\max \left(x _ {1}, x _ {2}\right)}\right) v _ {1} - c _ {1} x _ {1} + R \frac {x _ {1}}{x _ {1} + x _ {2}} \mathrm {i f} \max \left(x _ {1}, x _ {2}\right) > 0 \ 0 \mathrm {i f} \max \left(x _ {1}, x _ {2}\right) = 0 \end{array} \right. $$

(16)

$$ \begin{array}{c}{\operatorname{f r}\ x_{1}:<:x_{2},:u_{1}:=:\operatorname{l n}(\frac{x_{1}+x_{2}}{x_{2}})v_{1}:-:c_{1}x_{1}:+:R\frac{x_{1}}{x_{1}+x_{2}}:\operatorname{a n d}:\frac{d u_{1}}{d x_{1}}:=:\frac{v_{1}}{x_{1}+x_{2}}:c-1{}:+}\ {R\frac{x{2}}{(x_{1}+x_{2})^{2}}.}\ \end{array} $$

du1 We solve the inequality > 0, written in terms of X = x₁ + x₂. dx1

$$ X=x_{1}+x_{2} $$

$$ \frac{d u_{1}}{d x_{1}}>0 $$

$$ \frac{d u_{1}}{d x_{1}}>0\Leftrightarrow X^{2}-\frac{v_{1}}{c_{1}}X-\frac{R x_{2}}{c_{1}}<0 $$

(17)

p v¹ 2 Rx 1 v1 Consider¹= () +4 and X = (¹), where X are the roots c1 c12 2 c1 v1 Rx2 of the quadratic equation X² X = 0. We can rewrite inequality17in c1 c1 terms of X as (X X)(X X+) > 0. Since X < X+, the solution to this p v1 inequality is X < X < X+. We also note that1> and hence X < 0. c1 Since we also have X 0, we can conclude the following for a xed x₂.

$$ \varDelta_{1}=(\frac{v_{1}}{c_{1}})^{2}!+!4\frac{R x_{2}}{c_{1}} $$

$$ X_{\pm}=\frac{1}{2}(\frac{v_{1}}{c_{1}}\pm\sqrt{\varDelta_{1}}) $$

$$ X_{\pm} $$

$$ X ^ {2} - \frac {v _ {1}}{c _ {1}} X - \frac {R x _ {2}}{c _ {1}} = 0 $$

$$ X_{\pm} $$

$$ \big(X-X_{-}\big)\big(X-\overset{\circ}{X}_{+}\big)>\overset{\circ}{0} $$

$$ X_{-},<,X_{+} $$

$$ X_{-}<X<X_{+} $$

$$ X_{-}<0 $$

$$ \sqrt {\Delta_ {1}} > \frac {v _ {1}}{c _ {1}} $$

$$ x_{2} $$

$$ X\geq0 $$

$$ \frac{d u_{1}}{d x_{1}}>0\Leftrightarrow x_{1}+x_{2}<\frac{1}{2}\big(\frac{v_{1}}{c_{1}}+\sqrt{\varDelta_{1}}\big) $$

(18)

x1 +x2 x1 du1 1 1 If x₁ > x₂, u₁ = ln()v₁ c₁x₁ ⁺ R and = v₁() _x¹ x^{1 +x2} d^x1 x1 +x2 x1 x2 du1x2 (xx11(R v1) v x2₎ c₁ ₊ R₂. In that case we have > 0 i₂₁c₁ > 0 and, (x1 +x2) dx1 (x1 +x2) du1 therefore, < 0 if R < v₁. dx1p

$$ x_{1}>x_{2},,u_{1}=\ln(\frac{x_{1}+x_{2}}{x_{1}})v_{1}-c_{1}x_{1}+R\frac{x_{1}}{x_{1}+x_{2}}\mathrm{a n d}\frac{d u_{1}}{d x_{1}}=v_{1}\big(\frac{1}{x_{1}+x_{2}}-\frac{1}{x_{1}}\big)- $$

$$ \begin{array}{l}{c_{1}+R\frac{x_{2}}{(x_{1}+x_{2})^{2}}}\ \end{array} $$

$$ \frac{d u_{1}}{d x_{1}}>0 $$

$$ \frac {x _ {2} \left(x _ {1} \left(R - v _ {1}\right) - v _ {1} x _ {2}\right)}{x _ {1} \left(x _ {1} + x _ {2}\right) ^ {2}} - c _ {1} > 0 $$

$$ R<v_{1} $$

$$ \frac{d u_{1}}{d x_{1}}<0 $$

1 v2 Assume that (x₁0;x₂0) are the equilibrium values. If x₁0*>* ( +²) = q2 c2 1 v2 v2 ₂ Rx¹0 ( + () + 4) then x27! u2is decreasing (due to the result derived 2 c₂ c₂ c₂ above and the assumption that R < min(v₁;v₂)) and thus player 2 maximizes their utility by contributing x₂₀= 0. If x₂₀= 0, player 1 is better o contributing a very small amount to be sure to get the reward while minimizing their cost, p 1 v2 so x₁00. This contradicts the condition x₁0*>* ( +₂), which means p2 c2 1 v2 that x₁0< ( +2). The exact same argument can be made to derive 2pc2 1 v₁ x₂0< ( +1). _{2 c}

$$ \left(x_{1_{0}},x_{2_{0}}\right) $$

$$ \textstyle{x_{1_{0}}>\frac{1}{2}\big(\frac{v_{2}}{c_{2}}+\sqrt{\varDelta_{2}}\big)=} $$

$$ x_{2}\mapsto u_{2} $$

$$ \frac {1}{2} \left(\frac {v _ {2}}{c _ {2}} + \sqrt {\left(\frac {v _ {2}}{c _ {2}}\right) ^ {2} + 4 \frac {R x _ {1 0}}{c _ {2}}}\right) $$

$$ R<\operatorname*{m i n}(v_{1},v_{2}), $$

$$ x_{2_{0}}=0.,\mathrm{I f},x_{2_{0}}=0 $$

$$ x_{1_{0}}\approx0 $$

$$ x_{1_{0}},>,\frac{1}{2}(\frac{v_{2}}{c_{2}}+\sqrt{\varDelta_{2}}) $$

$$ x_{1_{0}},<,\textstyle{\frac{1}{2}}(\frac{v_{2}}{c_{2}}+\sqrt{\varDelta_{2}}) $$

$$ \ {x_{2_{0}}<\textstyle{\frac{1}{2}}(\frac{v{1{}}}{c{1}}+\sqrt{\varDelta_{1}})} $$

1 Assume now that x₁⁰6= x₂⁰and, without loss of generality, that max(x₁⁰;x₂⁰) = du1 x₁0. Since R < v₁ then < 0 for x₁ x₂0and hence player 1 best strategy dx1 is to contribute x₁₀x₂₀which contradicts our assumption. We thus conclude that x₁₀= x₂₀.

$$ x_{1_{0}}\neq x_{2_{0}} $$

$$ \operatorname{n a x}(x_{1_{0}},x_{2_{0}})= $$

$$ R<v_{1} $$

$$ x_{1_{0}} $$

$$ \frac{d u_{1}}{d x_{1}}<0 $$

$$ x_{1}\geq x_{2_{0}} $$

$$ x_{1_{0}}\leq x_{2_{0}} $$

$$ x_{1_{0}}=x_{2_{0}} $$

Combining x₁₀= x₂₀= x with the two inequalities derived in the rst part of this proof, we have the following bounds on x. 8 q

$$ x_{1_{0}}=x_{2_{0}}=x $$

$$ \left{ \begin{array}{l} x < \frac {1}{4} \left(\frac {v _ {1}}{c _ {1}} + \sqrt {\left(\frac {v _ {1}}{c _ {1}}\right) ^ {2} + 4 \frac {R x}{c _ {1}}}\right) \ x < \frac {1}{4} \left(\frac {v _ {2}}{c _ {2}} + \sqrt {\left(\frac {v _ {2}}{c _ {2}}\right) ^ {2} + 4 \frac {R x}{c _ {2}}}\right) \end{array} \right. $$

(19)

We now derive a closed-form solution for the constraint on q x. To solve the v1 2 Rx Inequality System19, we write X = () + 4 and, for ease of notation, c1 c1 write c = c₁ and v = v₁. Squaring and expanding X, one nds that 4x = ^{c v 2} (X² ()). A^ccordingly, rewriting the Inequality System19in terms of X R c gives us the following.

$$ X,=,\sqrt{\big(\frac{v_{1}}{c_{1}}\big)^{2}+4\frac{R x}{c_{1}}} $$

$$ c,=,c_{1} $$

$$ v,=,v_{1} $$

$$ 4x\ = $$

$$ \frac{c}{R}(X^{2}-(\frac{v}{c})^{2}) $$

$$ {\frac{c}{R}}X^{2}-X-{\frac{v^{2}}{R c}}-{\frac{v}{c}}<0 $$

(20)

0 c v² v ⁰ With = 1 + 4 ( +), we ha^ve that > ⁰ so the inequality can be R Rc c p 0 100 simplied as (X X⁰)(X X+) < 0 with X⁰ = R. Since X⁰ < X+, 2c ₀ 2 the solution to Inequality20is X⁰ < X < X+. As X⁰ > 0, we have (X⁰) < 0 ₂ X² < (X+) and, therefore, the solutions to the Inequality System19are the 2 2 0 cR1v₁₁ v₁ 0 cR2v₂₂ v₂ following, with₁= ¹ + 4 ( +) and²= 1 + 4 ( +). _Rc c1 Rc c2 8 p p

$$ \varDelta^{\prime}=1+4\frac{c}{R}(\frac{v^{2}}{R c}+\frac{v}{c}) $$

$$ \varDelta^{\prime}>0 $$

$$ (X-X_{-}^{\prime})(X-X_{+}^{\prime})<0 $$

$$ X_{\pm}^{\prime}=R^{\frac{1\pm\sqrt{\varDelta^{\prime}}}{2\ },}}endend{ $$

$$ X_{-}^{\prime}\prec X_{+}^{\prime} $$

$$ \dot{X_{-}^{\prime}}<X<X_{+}^{\prime} $$

$$ X^{2},<,(X_{+}^{\prime})^{2} $$

$$ (X_{-}^{\prime})^{2}< $$

$$ X_{-}^{\prime}>0 $$

$$ \varDelta_{1}^{\prime}=1+4\frac{c_{1}}{R}\big(\frac{v_{1}^{2}}{R c_{1}}+\frac{v_{1}}{c_{1}}\big) $$

$$ \varDelta_{2}^{\prime}=1+4\frac{c_{2}}{R}\big(\frac{v_{2}^{2}}{R c_{2}}+\frac{v_{2}}{c_{2}}\big) $$

$$ \begin{cases}{\frac{c_{1}}{4R}((R\frac{1-\sqrt{A_{1}^{\prime}}}{2c_{1}})^{2}-(\frac{v_{1}}{c_{1}})^{2})<x<\frac{c_{1}}{4R}((R\frac{1+\sqrt{A_{1}^{\prime}}}{2c_{1}})^{2}-(\frac{v_{1}}{c_{1}})^{2})}\ {\frac{c_{2}}{4R}((R\frac{1-\sqrt{A_{2}^{\prime}}}{2c_{2}})^{2})<x<\frac{c_{2}}{4R}((R\frac{1+\sqrt{A_{2}^{\prime}}}{2c_{2}})^{2}-(\frac{v_{2}}{c_{2}})^{2})}\ \end{cases} $$

(21)

D Proof of Theorem4

Consider the strategy of player n + 1 (the new player) as outlined in10. In the Pn 1-value equilibrium we have_i=1x_i= nx_eq.

$$ n+1 $$

$$ \sum_{i=1}^{n}x_{i}=n x_{e q}. $$

1.If nx_eq, player n + 1 is not incentivised to contribute anything so the equilibrium stays unchanged.

$$ n n\boldsymbol{x}_{e q}\geq\beta. $$

2.If nxeq< , there are two cases to consider.

$$ n n\ x_{e q}<\beta $$

(a)If xeq< nxeqthen player n + 1 contributes xeq. Since nxeq< j (from4) this means that for every player 1 j n we are in case (1) of their strategy. They only change their contribution after the introduction of player n + 1 ifjnxeq< xeqor equivalentlyj< (n + 1)xeq. Since 1 _j, there is at least one player who will change their contribution in this case if and only if1< (n + 1)xeq, in which case we also have 1< from xeq< nxeq.

$$ x_{e q},<,\beta-n x_{e q} $$

$$ x_{e q}. $$

$$ n x_{e q},<,\beta_{j} $$

$$ 1\leq j\leq n $$

$$ n+1;\mathrm{i f};\beta_{j}-n x_{e q}<x_{e q} $$

$$ \beta_{j}<(n+1)x_{e q}. $$

$$ \beta_{1}\leq\beta_{j} $$

$$ \beta_{1}<(n+1)x_{e q}, $$

$$ \beta_{1}<\beta $$

$$ x_{e q}<\beta-n x_{e q}. $$

(b)If x_eqnx_eqthen player n + 1 contributes nx_eq. As before, player j only changes their contribution after the introduction of player n+ 1 ifj(n 1)xeq( nxeq) < xeqor equivalently ifj< . This happens only if1< . In this case, we also have1< < (n + 1)xeq from x_eqnx_eq.

$$ x_{e q},\geq,\beta-n x_{e q} $$

$$ \beta-n x_{e q}. $$

$$ n+1\ \mathrm{i f}\ \beta_{j}-(n-1)x_{e q}-(\beta-n x_{e q})<x_{e q} $$

$$ \beta_{i}<\beta $$

$$ \beta_{1}<\beta<(n+1)x_{e q} $$

$$ \beta_{1}<\beta $$

$$ x_{e q}\geq\beta-n x_{e q} $$

A necessary and sucient condition to having one player changing their contri- 1 1 bution is, therefore, > 1and1< xeq<. _n+¹ n

$$ \beta>\beta_{1} $$

$$ \textstyle{\frac{1}{n+1}\beta_{1}<x_{e q}<\frac{1}{n}\beta} $$

E Proof of Theorem5

Pⁿ From Equation6, we havei=1xⁱ=1. For any new player n + 1 playing Pn+1 x_n+1> 0 we will, therefore, have_i=1x_i> ₁, so according to10the best strategy for player 1 would now be to free ride. According to10, the new player Pn contributes if and only ifi=1xi< or equivalently1< . Under this condition, a new player disrupts the equilibrium, which causes player 1 to free ride.

$$ \textstyle\sum_{i=1}^{n}x_{i},=,\beta_{1} $$

$$ n+1 $$

$$ x_{n+1}>0 $$

$$ \textstyle\sum_{i=1}^{n+1}x_{i},>,\beta_{1} $$

$$ \textstyle\sum_{i=1}^{n}x_{i};<;\beta $$

$$ \beta_{1},<,\beta. $$

F Proof of Theorem6

If a player leaves the game by no longer contributing, we have the following. 1 1 1 1 1 1 In the 1 value equilibrium case, since xeq 1<2< ::: <n ⁿ n n (implied by Condition4), a player leaving the game does not change the equilibrium (as specied by10). Hence a player leaving the game does not disrupt the equilibrium.

$$ \textstyle x_{\mathit{e q}};\leq;\frac{1}{n-1}\beta_{1};<;\frac{1}{n-1}\beta_{2};<;\ldots;<;\frac{1}{n-1}\beta_{n} $$

G Proof of Theorem7

By assumption, every player (other than player k) is playing x_eq. After the deviation happens, but before any other changes, players k is playing x_k0and the n 2 other players are still contributing x_eq. Each player’s new best response then becomes x_i;new= maxf0*;min(max(x_eq;x*_k0)); (_ix_k0) (n 2)x_eq)g due to Condition10.

$$ x_{e q}. $$

$$ x_{e q} $$

$$ x_{k_{0}} $$

$$ x_{i,\operatorname{n e w}}=\operatorname*{m a x}{0,\operatorname*{m i n}(\operatorname*{m a x}(x_{\mathit{e q}},x_{k_{0}})),(\beta_{i}-x_{k_{0}})-(n-2)x_{\mathit{e q}}} $$

Consider the following cases.

1.If xk0< xeqthen max(xeq;xk0) = xeq. For each player i we have xk0+ (n P 1)xeqnxeq iand thus (ixk0) (n 2)xeqxeq. (j6=ixj< j still holds with xk0< xeq.) This means each player’s best response is not impacted. Therefore, x_eqis still the equilibrium.

$$ x_{k_{0}}+(n- $$

$$ x_{k_{0}}<x_{e q} $$

$$ \operatorname*{m a x}\bigl(x_{e q},x_{k_{0}}\bigr)=x_{e q}. $$

$$ 1)x_{e q}\leq n x_{e q}\leq\beta_{i} $$

$$ x_{k_{0}},<,x_{e q}.), $$

$$ x_{e q} $$

2.If x_k0> x_eqthen we have that max(x_eq;x_k0) = x_k0. Therefore, Condition10 becomes maxf0*;min(x_k0;_ix_k0(n 2)x_eq)g for each player and for each player i 6= k₀ we have the followin*g.

$$ x_{k_{0}}>x_{e q} $$

$$ \operatorname*{m a x}(x_{e q},x_{k_{0}})=x_{k_{0}} $$

$$ \mathfrak{k}\big{0,\operatorname*{m i n}\big(x x_{k_{0}},\beta_{i}-x_{k_{0}}-\ n-2\big)x_{e q}\big)big $$

$$ i\neq $$

i (n 2)xeq (a)If x^{k0 i}xk0(n 2)xeq, or equivaleⁿtly x^k0, player 2 i’s new best response is to play x_i;new=_ix^k0(n 2)x^eqor 0 if this value is negative. This disrupts the current equilibrium and all the rational players have to change their contribution accordingly.

$$ x_{k_{0}}\geq\beta_{i}-x_{k_{0}}-\big(n-2\big)x_{\ \ell\bar{q}}, $$

$$ x_{k_{0}}\geq\textstyle\frac{\beta_{i}-(n-2)x_{\mathrm{}{e q}}}{2} $$

$$ \mathcal{X}{i,\mathrm{l e w}}=\beta{i}-x_{k_{0}}-\big(n-2\big)\mathcal{X}_{e q} $$

i (n 2)xeq (b)If x^{k0 i}xk0(n 2)x^eq, or equivaleⁿtly x^k0, player i’s 2 best response is to contribute x^k0. Again, the equilibrium is disrupted.

$$ x _ {k _ {0}} \leq \beta_ {i} - x _ {k _ {0}} - (n - 2) x _ {e q}; $$

$$ x_{k_{0}}\leq\textstyle{\frac{\beta_{i}-(n-2)x_{\mathrm{}{e q}}}{2}} $$

$$ x_{k_{\Omega}} $$

To summarize, if a player deviates from the equilibrium and its new contribution is x_k0x_eq, the best responses of other players stay unchanged and the equilibrium is not disrupted. In the other case, if x_k0> x_eq, the equilibrium changes.

$$ x_{k_{0}},leq x_{e q}. $$

$$ x_{k_{0}}>x_{e q} $$

H Proof of Theorem8

Assume that k > 1. In the case where players are in a 2 value equilibrium, according to condition10, player 1 should change its value to either₁(n 2)x_eq x_k0or to max(x_eq;x_k0) or to zero. Thus, player 1 changes their contribution.

$$ k>1 $$

$$ \beta_{1}!-!(n!-!2)x_{e q}- $$

$$ x_{k_{0}} $$

$$ \operatorname*{m a x}(x_{e q},x_{k_{0}}) $$

In the case where player 1 is the deviating player (i.e., k = 1), then the other players change their contribution if and only if there exists a j such that j(n 2)xeqxk0< max(xeq;xk0), orj(n 2)xeqxk0according to Condition10.

$$ (\mathrm{i.e.,\ \ k k,=,1} $$

$$ \beta_ {j} - (n - 2) x _ {e q} - x _ {k _ {0}} < \max \left(x _ {e q}, x _ {k _ {0}}\right) $$

$$ \beta_{j}\leq(n-2)x_{e q}-x_{k_{0}} $$