Zero-determinant alliances in

Zero-determinant alliances in multiplayer social dilemmas arXiv:1404.2886v1 [q-bio.PE] 10 Apr 2014 Christian Hilbel, Ame Traulsen2, Bin Wu2 & Martin A. Nowalc" Program for Evolutionary Dynamics, Harvard University, Cambridge, MA 02138, USA 2 EvolutionaryTheory Group, Max-Planck-Institute for Evolutionary Biology, August-Thienemann-StraBe 2, 24306 Plan, Germany 3 Department of Organismic and Evolutionary Biology, Department of Mathematics, Harvard University, Cambridge, MA 02138 April 11, 2014 Direct reciprocity and conditional cooperation are important mechanisms to prevent free riding in social dilemmas. But in large groups these mechanisms may become ineffective, because they require single individuals to have a substantial influence on their peers. How- ever, the recent discovery of the powerful class of zero-determinant strategies in the iterated prisoner's dilemma suggests that we may have underestimated the degree of control that a single player can exert. Here, we develop a theory for zero-determinant strategies for multiplayer social dilemmas, with any number of involved players. We distinguish several particularly interesting subclasses of strategies: fair strategies ensure that the own payoff matches the average payoff of the group; extortionate strategies allow a player to perform above average; and generous strategies let a player perform below average. We use this the- ory to explore how individuals can enhance their strategic options by forming alliances. The effects of an alliance depend on the size of the alliance, the type of the social dilemma, and on the strategy of the allies: fair alliances reduce the inequality within their group; extor- tionate alliances outperform the remaining group members; but generous alliances increase welfare. Our results highlight the critical interplay of individual control and alliance forma- tion to succeed in large groups. Keywords: evolutionary game theory; zero-determinant strategies; cooperation; public goods game; volunteer's dilemma; EFTA01074265 Cooperation among self-interested individuals is generally difficult to achieve (1, 2), but typically the free rider problem is aggravated even further when groups become large (3—8). In small com- munities, cooperation can often be stabilized by forms of direct and indirect reciprocity (9-16). For large groups, however, it has been suggested that these mechanisms may turn out to be in- effective, as it becomes more difficult to keep track of the reputation of others, and because the individual influence on others diminishes (3-7). To prevent the tragedy of the commons, and to compensate for the lack of individual control, many successful communities have thus established central institutions that enforce mutual cooperation (17-20). However, a recent discovery suggests that we may have underestimated the amount of control that single players can exert in repeated games. For the repeated prisoner's dilemma, Press and Dyson (21) have shown the existence of zero-determinant strategies (or ZD strategies), which allow a player to unilaterally enforce a linear relationship between the own payoff and the co- player's payoff — irrespective of the co-player's actual strategy. The class of zero-determinant strategies is surprisingly rich: For example, a player who wants to ensure that the own payoff will always match the co-player's payoff can do so by applying a fair ZD strategy, like Tit-for-Tat. On the other hand, a player who wants to outperform the respective opponent can do so by slightly tweaking the Tit-for-Tat strategy to the own advantage, thereby giving rise to extortionate ZD strategies. The discovery of such strategies has prompted several theoretical studies, exploring how different ZD strategies evolve under various evolutionary conditions (22-28). However, ZD strategies are not confined to pairwise games. In a recently published study, it was shown that ZD strategies also exist in repeated public goods games (29); and herein we will show that such strategies exist for all symmetric social dilemmas, with an arbitrary number of participants. We also use this theory to demonstrate how zero-determinant strategists can even further enhance their strategic options by forming alliances. As we will show, the impact of an alliance depends on its size, the type of the social dilemma and on the applied strategy of the allies: while fair alliances reduce inequality within their group, extortionate alliances strive for unilateral advantages, with larger alliances being able to enforce even more extortionate relationships. These results suggest that when a single individual's strategic options are limited, forming an alliance may result in a considerable leverage. To obtain these results, we consider a repeated social dilemma between it players. In each round of the game players can independently decide whether to cooperate (C) or to defect (D). A player's payoff depends on the player's own decision, and on the decisions of all other group members (see Fig. S1A): in a group in which j of the other group members cooperate, a co- operator receives the payoff /kb whereas a defector obtains bj. We assume that payoffs satisfy the following three properties that are characteristic for social dilemmas (corresponding to the Individual -centered' interpretation of altruism in (30)): (0 Irrespective of the own strategy, play- ers prefer the other group members to cooperate (ai+i > aj and b7+1 > bj for all j). (ii) Within 2 EFTA01074266 B C 3 2 1 0 -1 Number of cooperators among co-players n. n.2 .... 2 1 0 Cooperator's payoff Defectors payoff an-, an-2 a2 at ao bn-r bn-2 b2 b, be Public goods game Defector bream arc04 Ccoper101aio-cr 0 2 4 8 8 10 limber of cooperating op-players Alliance 2 .1 a. Volunteers Dilemma boWee,7:-b IMooperator od 0 2 4 6 8 10 Number of cooperating co-players Outsiders Figure S I: Illustration of the model assumptions for repeated social dilemmas. (A) We consider symmetric social dilemmas in which each player can either cooperate or defect. The player's payoff depends on the own decision, and on the number of other group members who decide to cooperate. (B) We will discuss two particular examples: the public goods game (in which payoffs are proportional to the number of cooperators), and the volunteers dilemma (as the most simple example of a nonlinear social dilemma). (C) Alliances are defined as a collection of individuals who coordinate on a joint ZD strategy. We refer to the set of group members that are not part of the alliance as outsiders. Outsiders are not restricted to any particular strategy; in particular, they may choose a joint strategy themselves. any mixed group, defectors obtain strictly higher payoffs than cooperators (bin > aj for all j). (iii) Mutual cooperation is favored over mutual defection (an_ t > b,,). To illustrate our results, we will discuss two particular examples of multiplayer games (see Fig. S I B). In the first example, the public goods game (31), cooperators contribute an amount c > 0 to a common pool, knowing that total contributions are multiplied by r (with 1 Cr< n) and evenly shared among all group mem- bers. Thus, a cooperator's payoff is aj = rc(j + 1)/n — c, whereas defectors yield bj = raj In. In the second example, the volunteer's dilemma (32), at least one group member has to volunteer to bear a cost c > 0 in order for all group members to derive a benefit b > c. Therefore, cooperators obtain aj = b — c (irrespective of j) while defectors yield bi = b if j ≥ 1 and bo = 0. Both examples (and many more, such as the collective -risk dilemma, (6, 7, 33)) are simple instances of 3 EFTA01074267 multiplayer social dilemmas. We assume that the social dilemma is repeated, such that individuals can react to their co- players' past actions (for simplicity, we will focus here on the case of an infinitely repeated game, but our results can easily be extended to the finite case, see Supporting Information). As usual, payoffs for the repeated game are defined as the average payoff that players obtain over all rounds. In general, strategies for such repeated games can become arbitrarily complex, as subjects may condition their behavior on past events and on the round number in non-trivial ways. Neverthe- less, as in pairwise games (21), zero-determinant strategies are surprisingly simple — they depend on the outcome of the last round only. In contrast to most previous studies on repeated games, however, we do not presume that individuals act in isolation. Instead, we allow subjects to form an alliance, which can be considered as a collection of players who coordinate on a joint strategy (see Fig. SIC). In the following, we will discuss how the strategic power of such an alliance de- pends on the number of involved players, on the social dilemma, and on the applied ZD strategy of the allies. Results Zero-determinant strategies in large-scale social dilemmas. ZD strategies are particular memory- one strategies (4, 21, 34, 35); they only condition their behavior on the outcome of the previous round. Memory-one strategies can be written as a vector (ps,j), where psi denotes the probability to cooperate in the next round, given that the player previously played S E (C, D}, and that j of the co-players cooperated. ZD strategies have a particular form (see also Supporting Information): players with a ZD strategy set their cooperation probabilities such that Pet'? PD,j = 1 + [( 1 — s)(i — — ne (b2-F1 a3)] c6[(1 — s)(i — 71om .(b) 43-01, (1) where a j and bi are the specific payoffs of the social dilemma (as outlined in Fig. 1), and where 1, s, and > 0 are parameters that can be chosen by the player. While these ZD strategies may appear inconspicuous, they give players an unexpected control over the resulting payoffs of the game, as we will show below. Instead of presuming that players act in isolation, as in previous models of zero-determinant strategies (21-29) we explicitly allow subjects to form alliances, and to coordinate on some joint ZD strategy. Let k be the number of allies, with 1 < k < n — 1 (in particular, this covers the case k = 1 of solitary alliances). In the Supporting Information we prove that if each of the allies 4 EFTA01074268 applies the same ZD-strategy with parameters 1, 8, and 4), then payoffs satisfy the equation = sAITA + (1 - 8415 where TrA is the mean payoff of the allies, Tr _A is the mean payoff of all outsiders, and SA_ s(rt — 1) — (k — 1) n — k (2] (3) Relation [2] suggests that by using a ZD strategy, alliances exert a direct influence on the payoffs of the outsiders. This relation is remarkably general, as it is independent of the specific social dilemma being played, and as it is fulfilled irrespective of the strategies that are adopted by the outsiders (in particular, outsiders are not restricted to memory-one strategies; it even holds if some or all of the outsiders coordinate on a joint strategy themselves). We call the parameter 1 the baseline payoff, s the slope of the applied ZD strategy, and 5,4 the effective slope of the alliance. In the special case of a single player forming an alliance, k = 1, the effective slope of the alliance according to Eq. [3) simplifies to 5„4 = s. The parameters 1, s, and 0 of a ZD strategy cannot be chosen independently, as the entries psj of a ZD strategy are probabilities that need to satisfy 0 ≤ psj ≤ 1. In general, the admissible parameters depend on the specific social dilemma being played. In the Supporting Information we show that exactly those relations [2] can be enforced for which either &A = s = 1 (in which case the parameter I in the definition of ZD strategies is irrelevant), or for which the parameters 1 and 5„4 satisfy max { bi _ k) (61 a3_1)} ≤ i ≤ min { aj + Al(n t)(b3+1 al)} , (4] where the maximum and minimum is taken over all possible group compositions, 0 ≤ j ≤ n - 1. It follows that feasible baseline payoffs are bounded by the payoffs for mutual cooperation and mutual defection, bo ≤ I ≤ an_1, and that the effective slope needs to satisfy the inequality —1/(n — ≤ sA ≤ 1. Moreover, as social dilemmas satisfy bj+i > aj for all j, condition [4] implies that the range of enforceable payoff relations is strictly increasing with the size of the al- liance — larger alliances are able to enforce more extreme relationships between the payoffs of the allies and the outsiders. In the following, we will highlight several special cases of ZD strategies, and we discuss how subjects can increase their strategic power by forming alliances. Fair alliances. As a first example, let us consider alliances that apply a ZD strategy with slope 8„4 = s = 1. By Eq. [2], such alliances enforce the payoff relation TrA = Tr_A, such that the allies' mean payoff matches the mean payoff of the outsiders. We call such ZD strategies (and the alliances that apply them) fair. As shown in Figure 2A, fair strategies do not ensure that 5 EFTA01074269 all group members get the same payoff — due to our definition of social dilemmas, unconditional defectors always outperform unconditional cooperators, no matter whether the group also contains fair players. Instead, fair players can only ensure that they do not take any unilateral advantage of their peers. Interestingly, it follows from Eq. [3] that fair alliances consist of fair players: because 8A = 1 implies s = 1, each player i of a fair alliance individually enforces the relation rra = r_i. It also follows from our characterization [4] that such fair ZD strategies exist for all social dilemmas — irrespective of the particular payoffs and irrespective of the group size. As an example, let us consider the strategy proportional ft-for-Tat (pTFT), for which the probability to cooperate is simply given by the fraction of cooperators among the co-players in the previous round, pTFTsd — [5) n — 1* For pairwise games, this definition of pTFT simplifies to the classical Tit-for-Tat strategy. How- ever, also for the public goods game and for the volunteer's dilemma, pTFT is a ZD strategy (because it can be obtained from Eq. [I] by setting s = 1 and 0 = 1/c, with c being the cost of cooperation). As s = 1, alliances of pTFT players are fair, and they enforce TrA = ir_A. Inter- estingly, this strategy has received little attention in the previous literature. Instead, researchers have focused on other generalized versions of lit-for-Tat, which cooperate if at least in co-players cooperated in the previous round (3, 36), i.e. psj = 0 if j < in and psi = 1 if j > in. Unlike p TFT, these threshold strategies neither enforce a linear relation between payoffs, nor do they induce fair outcomes, suggesting that pTFT may be the more natural generalization of Tit-for-Tat for large social dilemmas. Extortionate alliances. As another interesting subclass of ZD strategies, let us consider strategies that choose the mutual defection payoff as baseline payoff, I = bo, and that enforce a positive slope 0 < sA < 1. For such strategies, relation [2] becomes ir _A = sAfrA + (1 — sA)bo, implying that the outsiders only get a fraction sA of any surplus over the mutual defection payoff. Moreover, as the slope sA is positive, the payoffs TrA and Tr—A are positively related. As a consequence, the collective best reply for the outsiders is to maximize the allies' payoffs by cooperating in every round. In analogy to Press and Dyson (21), we call such alliances extortionate, and we call the quantity x = 1/sA the extortion factor. Extortionate alliances are particularly powerful in social dilemmas in which mutual defection leads to the lowest group payoff (as in the public goods game and in the volunteer's dilemma): in that case, they enforce the relation if_A ≤ TrA; on average, the allies perform at least as well as the outsiders (as also depicted in Figure 2B). Similarly to the results for fair alliances, extortionate alliances consist of extortionate players: an alliance that enforces the baseline payoff I = bo and a slope 0 < sA < 1 requires the allies to use ZD strategies with I= bo and 0 < s < 1, such that each player i individually enforces the relation 6 EFTA01074270 Fair Alliance B Extortionate Alliance C Generous Alliance Alliance (k=ft) iramekeememe Outsiders (n-k=12) 3 2 1 Alliance (k=8) Outsiders (n-k=12) 1 Outsiders (n-k=12) Alliance (k=8) 0 0 0 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 Round Number Round Number Round Number Figure S2: Characteristic dynamics of payoffs over the course of the game for three different alliances. Each panel depicts the payoff of each individual group member (thin lines) and the resulting average payoffs (thick lines) for the alliance (blue) and for outsiders (red). (A) An alliance that adopts a fair strategy ensures that the payoff of the allies matches the mean payoff of the outsiders. This does not imply that all outsiders yield the same payoff. (B) For games in which mutual defection leads to the lowest group payoff, extortionate alliances ensure that their payoffs are above average. (C) In games in which mutual cooperation is the social optimum, generous alliances let their co-players gain higher payoffs. The three graphs depict the case of a public goods game with r = 4, c = 1, group size n = 20, and alliance size k = 8. For the strategies of the outsiders we have used random memory-one strategies, were the cooperation probabilities were independently drawn from a uniform distribution. For the strategies of the allies, we have used (A) pT F7', (B)pET with s = 0.8, (C) pec with s = 0.8. IT-i = slrq + - s)bo. For the specific example of a public goods game, let us consider the ZD strategy pE1 with 1 = 0, (b = 1/c, and 0 < s < 1, for which Eq. [1] becomes 423 = 4nr - (1 - s) pEs = WL7 — (1 — s)i [6] In the limit of s i 1, these extortionate strategies approach the fair strategy pT F7'. However, as s decreases from 1, the cooperation probabilities of pEz are increasingly biased to the own advantage (with the probabilities ppi decreasing more rapidly than the probabilities pf.,Ti). As with fair strategies, such extortionate strategies exist for all repeated social dilemmas. However, in large groups the power of alliances to extort their peers depends on the social dilemma, and on the size of the alliance (as generally described by condition [4]). For example, for single-player alliances (k = 1) in the public goods game, the feasible extor- tion factors x are bounded when groups become large, with Xmax = — 1)r/((n — 1)r — being the maximum extortion factor (see also (29)). To be able to enforce arbitrarily high extor- tion factors, players need to form an alliance such that the fraction of alliance members exceeds a critical threshold. By solving condition [4] for the case of extortionate coalitions with infinite 7 EFTA01074271 extortion factors (i.e., I = 0 and sA = 0), this critical threshold can be calculated explicitly as k r — 1 n r Only for alliances that have this critical mass, there are no bounds to extortion. [7) Generous alliances. As the benevolent counterpart to extortioners, Stewart and Plotkin were first to describe a set of generous strategies for the iterated prisoner's dilemma (22, 26). Unlike extortioners, generous alliances set the baseline payoff to the mutual cooperation payoff I = a while still enforcing a positive slope 0 < sA < 1. This results in the payoff relation Tr_A = sArA + (1 — sA)a„_1, such that a generous alliances accept a larger share of any loss (compared to the mutual cooperation payoff a.„_1). In particular, for games in which mutual cooperation is the optimal outcome (as in the public goods game and in the prisoner's dilemma, but not in the volunteer's dilemma), the payoff of a generous player satisfies rA < _A (see also Fig. 2C depicting the case of a public goods game). As with fair and extortionate alliances, generous alliances consist of players that are individually generous. For the example of a public goods game, we obtain a particularly simple generous ZD strategy pGe by setting I = rc — c, = 1/c, and 0 < s < 1, such that Pg'7i = +(1 8)Q1—.÷1 nee raj = n-1 [8] In parallel to the extortionate strategy discussed before, these generous strategies approach pTFT in the limit of s = 1, whereas they enforce more generous outcomes for s < 1. Again, generous strategies exist for all social dilemmas, but the extent to which players can be generous depends on the particular social dilemma, and on the size of the alliance. Equalizers. As a last interesting class of ZD strategies, let us consider alliances that choose s = (k. — 1)1(n — 1), such that by Eq. [3] the effective slope becomes sA = 0. By Eq. [2], such alliances enforce the payoff relation ir_A = &meaning that they have unilateral control over the mean payoff of the outsiders (for the prisoner's dilemma, such equalizer strategies were first discovered by (37)). However, as with extortionate and generous strategies, equalizer alliances need to reach a critical size to be able to determine the outsiders' payoff; this critical size depends on the particular social dilemma, and on the imposed payoff! (the exact condition can be obtained from [4] by setting sA = 0). For the example of a public goods game, a single player can only set the co-players' mean score if the group size is below n < 2r/(r — 1). For larger group sizes, players need to form 8 EFTA01074272 Strategy class Typical property Prisoner's dilemma Public goods game Volunteer's dilemma Fair strategies Extortionate strategies Generous strategies Equalizers = 1T—A ITA IT-A C 7.01 IT-A > ?TA 7T-A = 1 Always exist Always exist Always exist Always exist Always exist In large groups, single players cannot be arbitrarily extortionate, but sufficiently large alliances can be arbitrarily extortionate In large groups, single players cannot be arbitrarily generous, but sufficiently large alliances can be arbitrarily generous May not be feasible for single players, but is always feasible for sufficiently large alliances Always exist Even large alliances cannot be arbitrarily extortionate Do not ensure that own payoff is below average Only feasible if the size of the alliance is k = n — 1, can only enforce I = b — c Table I: Strategic power of different ZD strategies for three different social dilemmas. In the repeated prisoner's dilemma, single players can exert all strategic behaviors (21, 26, 27). Other social dilemmas either require players to form alliances in order to gain sufficient control (as in the public goods game), or they only allow for limited forms of control (as in the volunteer's dilemma). alliances, with k > (n — 2)(r — 1) (9) n n + (n — 2)r being the minimum fraction of alliance members that is needed to dictate the outsiders' payoff. Although the right hand side of Eq. [91 is monotonically increasing with group size, equalizer alliances are always feasible; in particular, alliances of size k = n — 1 can always set the payoff of the remaining player to any value between 0 and re — c. Strategic power of different ZD strategies. Table 1 gives an overview for these four strategy classes for three examples of social dilemmas. It shows that while generally ZD strategies exist for all group sizes, the power of single players to enforce particular outcomes typically diminishes or disappears in large groups. Forming alliances allows players to increase their strategic scope. The impact of a given alliance, however, depends on the specific social dilemma: while alliances can become arbitrarily powerful in public goods games, their strategic options remain limited in the volunteer's dilemma. While fair, extortionate, and generous alliances enforce different payoff relations, simulations suggest that each of these strategy classes has its particular strength when facing unknown oppo- 9 EFTA01074273 Extortionate Fair Generous Alliance Alliance Alliance • S..- 10 T. 0 5 esCA O. al g 2 es v a) to CC 1 8 go 0.03 " 0.0 0.02 >c o.oi S 2.0 ao 1.5 ro c - a'? 1.0 m¢ ° B 0.5 0.0 C -s- t st - - - -• 1 2 3 4 5 6 Size of Alliance Figure S3: The effect of different alliance strategies and various alliance sizes. Each panel shows the outcome of simulated public goods games in which the alliance members interact with n — k random co-players (uniformly taken from the set of memory-one strategies). We compare the success of different alliances along three dimensions: the relative payoff advantage of the alliance (defined as xt4/Tr_A), the payoff inequality within a group (defined as the mean variance between payoffs of all group members), and the absolute payoff of the alliance (as given by IrA). Simu- lations suggest that (A) extortionate alliances gain the highest relative payoff advantages, (B) fair alliances reduce inequality within their group, and (C) sufficiently large generous alliances get the highest payoffs. For the simulations, we have used a public goods game (r = 3, c = 1) in a group of size n = 7; data was obtained by averaging over 500 randomly formed groups. The strategy of the alliance members was pT F7', pEx (with s = 0.85), and pee (with s = 0.85), respectively. nents (Figure 3). Forming an extortionate alliance gives the allies a relative advantage compared to the outsiders, and by increasing the alliance's size, allies can enforce more extreme relationships. 10 EFTA01074274 Forming a fair alliance, on the other hand, is an appropriate measure to reduce the payoff inequal- ity within a group — while the other two behaviors, generosity and extortion, are meant to induce unequal payoffs (to the own advantage, or to the advantage of the outsiders members, respec- tively), fair players actively avoid generating further inequality by matching the mean payoff of the outsiders. Generous alliances, however, are most successful in increasing the absolute payoffs. While it is obvious that generous alliances are beneficial for the outsiders (and that this positive effect is increasing in the size of the alliance), Figure 3 suggests that even the allies themselves may benefit from coordinating on a generous alliance strategy. Fair and extortionate alliances are programmed to fight back when being exploited; this is meant to reduce the outsiders' payoffs, but it also reduces the payoffs of the other allies. Therefore, when the alliance has reached a critical size, it is advantageous to agree on a generous alliance strategy instead (but without being overly altruistic), as it helps to avoid self-destructive vendettas. This somewhat unexpected strength of generous strategies is in line with previous evolution- ary results for the iterated prisoner's dilemma. For this pairwise dilemma, several studies have reported that generosity, and not extortion, is favored by selection (25-27). Such an effect has also been confirmed in a recent behavioral experiment, in which human cooperation rates against generous strategies were twice as high as against extortioners, although full cooperation would have been the humans' best response in both cases (38). Our results suggest that in multiplayer dilemmas, generous alliances are able to induce a similarly beneficial group dynamics. In the Supporting Information we show that if a generous alliance has reached a critical mass, it be- comes optimal for outsiders to become generous too (independent of the specific social dilemma, and independent of the strategy of the remaining outsiders). Once this critical mass is achieved, generosity proves self-enforcing. Discussion When subjects lack individual power to enforce beneficial outcomes, they can often improve their strategic position by joining forces with others. Herein, we have used and expanded the theory of zero-determinant strategies (21, 25, 26) to explore the role of such alliances in repeated dilemmas. We have found that three key characteristics determine the effect of an alliance of ZD strategists: the underlying social dilemma, the size of the alliance, and the strategy of the allies. While subjects typically have little influence to transform the underlying dilemma, we have shown that they can considerably raise their strategic power by forming larger alliances, and they can achieve various objectives by choosing appropriate strategies. Our approach is based on the distinction between alliance members (who agree on a joint ZD strategy), and outsiders (who are not restricted to any particular strategy, and who may form an alliance themselves). This distinction allowed us to show the existence of particularly powerful 11 EFTA01074275 alliances, and to discuss their relative strengths. As an interesting next step of research, we plan to investigate how such alliances are formed in the first place (which is typically at the core of traditional models of coalitions, e.g. (39)), and whether evolutionary forces would favor particular alliances over others (40). The results presented herein suggest that subjects may have various motives to join forces. As particular examples, we have highlighted extortionate alliances (who aim for a relative payoff advantage over the outsiders), fair alliances (who aim to reduce the inequality within their group), and generous alliances (who are able to induce higher payoffs as they avoid costly vendettas after accidental defections). Whether such alliances emerge and whether they are stable thus needs to be addressed in light of the respective aim of the alliance: when subjects are primarily interested in low inequality, then forming a fair alliance is an effective means to reach this aim; and once a fair alliance is formed, inequity-averse subjects have little incentives to leave (even if leaving the alliance would allow them to gain higher payoffs). While we have focused on the effects of alliances in multiplayer social dilemmas, it should be noted that our results on ZD strategies also apply for solitary alliances, consisting of single players only. Thus, even if players are unable to coordinate on joint strategies, zero-determinant strategies are surprisingly powerful. They allow players to dictate linear payoff relations, irrespective of the specific social dilemma being played, irrespective of the group size, and irrespective of the counter-measures taken by the outsiders. In particular, we have shown that any social dilemma allows players to be fair, extortionate, or generous. At the same time, zero-determinant strategies are remarkably simple. For example, in order to be fair in a public goods game (or in a volunteer's dilemma), players only need to apply a rule called proportional Tit-for Tat pTFT: if j of the n —1 other group members cooperated in the previous round, then cooperate with probability jfin — 1) in the following round. Extortionate and generous strategies can be obtained in a similar way, by slightly modifying pTFT to the own advantage or to the advantage of the outsiders. While these results were derived for the special case of infinitely repeated games, they can be extended to the more realistic finite case. In finitely repeated games, end-game effects may prevent alliances to enforce a perfect linear relation between payoffs; but it is still possible to enforce an arbitrarily strong correlation between payoffs, provided that the game is repeated sufficiently often. Similarly, we show in the Supporting Information, that it is not necessary that all alliance members coordinate on the same ZD strategy, and that different alliance members may apply different strategies. However, we have focused here on the case of symmetric alliances with a joint strategy, because they are most powerful: any payoff relationship that can be enforced by asymmetric alliances with different ZD strategies, can also be enforced by a symmetric alliance. Overall, our results reveal how single players in multiplayer games can increase their strategic power by forming beneficial alliances with others, helping them to regain control in large-scale social dilemmas. 12 EFTA01074276 Acknowledgments CH gratefully acknowledges generous funding by the SchrOdinger stipend J3475 of the Austrian Science Fund. References [ I] G. Hardin. The tragedy of the commons. Science, 162:1243-1248, 1968. [2] M. Olson. The Logic of Collective Action: Public Goods and the Theory of Groups. Harvard Univer- sity Press, revised edition, 1971. [3] R. Boyd and P. J. Richerson. The evolution of reciprocity in sizeable groups. Journal of Theoretical Biology, 132:337-356, 1988. [4] C. Hauert and H. G. Schuster. Effects of increasing the number of players and memory size in the iterated prisoner's dilemma: a numerical approach. Proceedings of the Royal Society B, 264:513-519, 1997. [5] S. Suzuki and E. Akiyama. Evolution of indirect reciprocity in groups of various sizes and comparison with direct reciprocity. Journal of Theoretical Biology, 245(3):539-552, Apr 2007. [6] F. C. Santos and J. M. Pacheco. Risk of collective failure provides an escape from the tragedy of the commons. Proceedings of the National Academy of Sciences USA, 108:10421-10425, 2011. [7] M. Abou Chakra and A. Traulsen. Evolutionary dynamics of strategic behavior in a collective -risk dilemma. PLoS Computational Biology, 8:e1002652, 2012. [8] W. Yang, W. Liu, A. Villa, M. Tuanmu, G. He, T. Dietz, and J. Liu. Nonlinear effects of group size on collective action and resource outcomes. Proceedings of the National Academy of Sciences USA, 110:10916-10921,2013. [9] R. L. Trivers. The evolution of reciprocal altruism. The Quarterly Review of Biology, 46:35-57, 1971. [10] R. Axelrod. The Evolution of Cooperation. Basic Books, New York, NY, 1984. [II] R. Alexander. The Biology of Moral Systems. Aldine de Gruyter, New York, 1987. [12] C. Wedekind and M. Milinski. Cooperation through image scoring in humans. Science, 288:850-852, 2000. [13] J. Henrich, R. Boyd, S. Bowles, C. F. Camerer, E. Fehr, H. Gintis, and R. McElreath. Cooperation, reciprocity and punishment in fifteen small scale societies. American Economic Review, 91:73-78, 2001. [14] M. A. Nowak and K. Sigmund. Evolution of indirect reciprocity. Nature, 437:1291-1298, 2005. [ I 5] M. van Veelen, J. Garcia, D. G. Rand, and M. A. Nowak. Direct reciprocity in structured populations. Proceedings of the National Academy of Sciences USA, 109:9929-9934, 2012. [16] B. M. Zagorsky, J. G. Reiter, K. Chatterjee, and M. A. Nowak. Forgiver triumphs in alternating prisoner's dilemma. PLoS One, page DOI: 10.137 I/joumal.pone.0080814, 2013. [17] T. Yamagishi. The provision of a sanctioning system as a public good. Journal of Personality and Social Psychology, 51:110-116, 1986. [18] E. Ostrom. Governing the Commons: The Evolution of Institutions for Collective Action. Cambridge Univ. Press, 1990. 13 EFTA01074277 [19] K. Sigmund, H. De Silva, A. Traulsen, and C. Hauert. Social learning promotes institutions for governing the commons. Nature, 466:861-863, 2010. [20] F. Guala. Reciprocity: Weak or strong? What punishment experiments do (and do not) demonstrate? Behavioral and Brain Sciences, 35:1-15, 2012. [21] W. H. Press and F. D. Dyson. Iterated prisoner's dilemma contains strategies that dominate any evolutionary opponent. Proceedings of the National Academy of Sciences USA, 109:10409-10413, 2012. [22] A. J. Stewart and J. B. Plotkin. Extortion and cooperation in the prisoner's dilemma. Proceedings of the National Academy of Sciences USA, 109:10134-10135,2012. [23] P. Ball. Physicists suggest selfishness can pay. Nature, page doi:10.1038/nature.2012.11254, 2012. [24] C. Hilbe, M. A. Nowak, and K. Sigmund. The evolution of extortion in iterated prisoner's dilemma games. Proceedings of the National Academy of Sciences USA, 110:6913-6918, 2013. [25] E. Akin. Stable cooperative solutions for the iterated prisoner's dilemma. arXiv, page 1211.0969v2, 2013. [26] A. J. Stewart and J. B. Plotkin. From extortion to generosity, evolution in the iterated prisoner's dilemma. Proceedings of the National Academy of Sciences USA, in press, 2013. [27] C. Hilbe, M. A. Nowak, and A. Traulsen. Adaptive dynamics of exortion and compliance. PLoS One, 8:e77886, 2013. [28] A. Szolnoki and M. Perc. Evolution of extortion in structured populations. Physical Review E, 89:022804,2014. [29] L. Pan, D. Hao, Z. Rong, and T Zhou. Zero-determinant strategies in the iterated public goods game. arXiv, page 1402.3542, 2014. [30] B. Kerr, P. Godfrey-Smith. and M. W. Feldman. What is altruism? Trends in Ecology and Evolution, 19(3):135-140, Mar 2004. [31] J. O. Ledyard. Public goods: A survey of experimental research. In John H Kagel and Alvin E Roth, editors, The Handbook of Experimental Economics. Princeton Univ. Press, Feb 1995. [32] A. Diekmann. Volunteer's dilemma. Journal of conflict Resolution, 29:605-610, 1985. [33] M. Milinski, R. D. Sommerfeld, H.-J. Krambeck, F. A. Reed, and J. Marotzke. The collective -risk so- cial dilemma and the prevention of simulated dangerous climate change. Proceedings of the National Academy of Sciences USA, 105(7):2291-2294,2008. [34] M. A. Nowak and K. Sigmund. A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner's Dilemma game. Nature, 364:56-58, 1993. [35] K. Sigmund. The calculus of selfishness. Princeton Univ. Press, 2010. [36] S. Kurokawa and Y. Ihara. Emergence of cooperation in public goods games. Proceedings of the Royal Society B, 276:1379-1384, 2009. [37] M. C. Boerlijst, M. A. Nowak, and K. Sigmund. Equal pay for all prisoners. American Mathematical Monthly, 104:303-307, 1997. [38] C. Hilbe, T. Rohl, and M. Milinski. Extortion subdues human players but is finally punished in the prisoner's dilemma. Nature Communications, In press, 2014. [39] B. Peleg and P. Sudholter. Introduction to the theory of cooperative games. Springer, Berlin, Heidel- berg, New York, 2003. [40] M. Mesterton-Gibbons, S. Gavrilets, J. Gravner, and E. Akcay. Models of coalition or alliance forma- 14 EFTA01074278 lion. Journal of Theoretical Biology, 274:187-204,2011. 15 EFTA01074279 Supporting Information: Zero-determinant alliances in multiplayer social dilemmas Christian Hilbel, Ame Traulsen 2, Bin Wu2 & Martin A. Nowak" 3 Program for Evolutionary Dynamics, Harvard University, Cambridge, MA 02138, USA 2 EvolutionaryTheory Group, Max-Planck-Institute for Evolutionary Biology, August-Thienemann-Strafe 2, 24306 Plan, Germany 3 Department of Organismic and Evolutionary Biology, Department of Mathematics, Harvard University, Cambridge, MA 02138 In the following, we develop a theory of zero•determinant strategies (ZD strategies) and alliances for general multiplayer social dilemmas. We begin by defining the setup of our model of repeated social dilemmas (Section 1). Thereafter, we derive the existence and the properties of ZD strategies for solitary alliances with a single player (Section 2), and then for general alliances with an arbitrary number of players (Section 3). Moreover, we explore which ZD strategies give rise to stable Nash equilibria, and we discuss which alliances are self•enforcing when subjects strive for high payoffs (Section 4). As applications, we study alliances in the repeated public goods game and in the repeated volunteer's dilemma (Section 5). The appendix contains the proofs for our results. 1 Setup of the model: Repeated multiplayer dilemmas 17 2 ZD strategies for solitary players 18 3 ZD strategies for alliances 20 4 Self-enforcing alliances 21 5 Applications 23 5.1 Public goods games 23 5.1.1 Solitary players 23 5.1.2 Alliances 24 5.2 Volunteer's Dilemma 25 A Appendix: Proofs 25 16 EFTA01074280 1 Setup of the model: Repeated multiplayer dilemmas We consider repeated social dilemmas between n players (as illustrated in Fig. I of the main text). In each round, players may either cooperate (C) or defect (D), and the players' payoffs for each round depend on their own action, and on the number of cooperators among the other group members. Specifically, in a group with j other cooperators, a cooperator receives the payoff a1, whereas a defector obtains bd. To qualify as a social dilemma, we assume that one-shot payoffs satisfy the following three conditions: (i) Independent of the own action, players prefer their co-players to be cooperative, aj+1 > ai and bj+1 > bi for all j with 0 ≤ j < n — I. IS 11 (it) Within each mixed group, defectors strictly outperform cooperators, > (xi for all j with 0 < j < - 2. (ii) Mutual cooperation is preferred over mutal defection, an-1 > b0. is'21 As particular examples of such social dilemmas, we discuss the linear public goods game (e.g. (31)) and the volunteer's dilemma (32) in Section 5. Let us assume that the social dilemma is repeated for Af rounds (in the main manuscript, we have focused on the special case M —> co). For such repeated games, a player's strategy needs to specify how to act in given round, depending on the outcomes of the previous rounds. Given the strategies of all group members, let us denote player i's expected payoff in round in as 71I (ft* and the average payoff of his co-players as n;(310 = Ei#1 ari (in)/(n — 1). If the social dilemma is repeated for Al rounds, we define payoffs for the repeated game as the average payoff per round, M-1 ri = Iri(m). Al A-0 m=0 al-1 At A—,m=Il 1541 For infinitely repeated games, payoffs are then defined by taking the limit Al oo For simplicity, we assume that these limits exist (which holds, for example, under the realistic assumption that players some- times commit implementation errors, (35)). While in general, strategies for repeated games can be arbitrarily complicated, ZD strategies are a subset of a particularly simple class of strategies called memory-one strategies (21, 34, 35). In finitely repeated n-player games, such strategies can be written as a vector P= (po: pan_i, pan_2, • • • ,pc.0; PD,n-1113D.n-2 • • • ,PD.0), 17 1551 EFTA01074281 where po is the player's probability to cooperate in the first round, and ps.i is the probability to cooperate in round in ≥ 2, given that the player previously played S E {C, D}, and that j of his co-players cooperated. In infinitely repeated games, the outcome of the first round can often be neglected; in that case one may drop the entry for po from the representation of memory-one strategies (21, 22, 24-29), yielding P= (Pan-1, Pan 2 PC.0; PD.n-19PD.n-2 • • • ,PD.0)• [S6] If the group contains only players with memory-strategies, the calculation of payoffs according to [541 becomes particularly simple. In that case, the repeated game can be described as a Markov chain, as the outcome in the next round only depends on the outcome of the previous round (4, 34, 35). While the assumption of memory-one strategies often simplifies calculations, we will show below that the properties of ZD strategies hold irrespective of the strategies of the other group members (in particular, ZD strategists do not require their co-players to apply memory-one strategies). 2 ZD strategies for solitary players As specified in the main text, ZD strategies are particular memory-one strategies. We say that a player adopts a ZD strategy, if the player chooses three constants 1, s, and 4, 0 0, and then calculates the respective cooperation probabilities in [S6] as PC,/ PD,J — — 1 -F [(1 — 3)(1 — ni) — .7.j (634.1 ck,)] 4(1 - s)(I — 1/2) + — n 1 (1/2 aj—L)]. It is the following property of ZD strategies that is central to our analysis: [571 Proposition 1 (ZD strategies enforce a linear relation between payoffs.) Suppose player i applies a ZD strategy with parameters 1,.s, and ¢ > 0 in a repeated game with M rounds. Then payoffs obey the relation — sic — (1 —4)1l 1 IS81 0111 In particular, in the case of infinitely repeated games, M oo, payoffs satisfy = sr, + (1 — s)l. [S9] It is worth to highlight several features of Proposition I. First, the Proposition makes no assumptions on the strategies of the other group members, nor does it make restrictions on the specific social dilemma. Player i can thus enforce linear relations of the form [581 and [591, independent of the behavior of i's co-players, and independent of the exact strategic situation (in fact, the proof of Proposition I does not make use of the assumption that the game is a social dilemma). In Figure S4, we illustrate this result for two different social dilemmas (the public goods game and the volunteer's dilemma), and for two different ZD strategies (a generous and an extortionate ZD strategy). Second, while we have focused on infinitely repeated games in the main text, relation [S8] shows how our results generalize for finitely many rounds. Even in the finite 18 EFTA01074282 A Average payoff of co-players x-. fro'n-c.reln [O. Public Goods Game • I¢-c.re-q iin-l)rdti.(n-t}rorn-c) B Average payoff of co-players x_, (0,0 Payoff of Payoff of focal player focal player Volunteers Dilemma ,b-cf(n-1)) Figure S4: Illustration of ZD-strategies for (A) the linear public goods game and (B) the volun- teer's dilemma. The blue-shaded area represents all feasible payoffs, with the x-axis representing the payoff of player i, and with the y-axis representing the mean payoff of i's co-players. The dashed diagonal gives the payoff combinations for which as = r_i. In both graphs, the strategy of player i is fixed to some zero-determinant strategy, whereas for the co-players we have sampled 10° random memory-one strategies. Red dots represent the resulting payoff combinations, and the grey line gives the prediction according to Eq. (S9]. For both graphs, we have considered an in- finitely repeated game in a group of size xi = 4. Parameters: (A) Public goods game with r = 2.4 and c = 1. For the strategy of player i we have used a generous ZD strategy with parameters 1 = re — c, s = 2/3, 0 = 1/2. (B) Volunteer's dilemma with b = 1.5, c = 1; player 'i applies an extortionate strategy with parameters /= 0, s = 9/10. sb = 1/2. case, player i can enforce an arbitrarily strong correlation between the players' payoffs, provided that the round number Ili is sufficiently large compared to the parameter 0. Third, Proposition I gives a natural interpretation for the three parameters 1, a and 0. The baseline payoff corresponds to the players' payoffs if all group members apply the same ZD strategy (in which case r_i = r,); the slope a determines how strong the payoffs r, and are related; and by (S8] the parameter 0 determines the rate of convergence with Al. A player cannot enforce arbitrary payoff relations (S9] because the parameters 1, a and 0 need to be set such that all cooperation probabilities in IS7] are in the unit interval. We thus say that a payoff relation (1,$) is enforceable, if there is a 0 7 0 such that 0 ≤ ps,j ≤ 1 for all S E (C, D} and all j with 0 ≤ j ≤ it - 1. The following gives a characterization of the possible payoff relations that a single player can enforce. Proposition 2 (Characterization of enforceable payoff relations) For a given social dilemma, the payoff relation (1, s) is enforceable if and only if either a = 1 or 05j <n max -1 (bi — 1=4i= (b3 art)} ≤ 0< ≤ min -1 {a., -F 0J+1 — el.i)) • [S10] j<n In particular, enforceable payoff relations satisfy - t ≤ s ≤ 1, and if s < 1 then bo ≤ I < a„_ t. 19 EFTA01074283 A Public Goods Game Slope • B Slope,Dilemma n=10 n = 5 n=4 n = 3 Baseline r I I I Baseline ,c-c payoff payoff Figure S5: Enforceable payoff relations for (A) the linear public goods game and (B) the vol- unteer's dilemma. A pair (1, s) is enforceable for a given group size n if the point is within the respectively shaded area. The set of enforceable pairs for large n is a subset of the the respective set for smaller n, i.e. the set of enforceable pairs shrinks with increasing group size. Parameters: (A) Linear public goods game with r = 2.4, c = 1. (B) Volunteer's dilemma with b = 1.5, c = 1. As a corollary, we note that if for a given slope s the baseline payoffs Si and /2 are enforceable, then so is any baseline payoff between ti and /2. Figure 55 gives an illustration of the enforceable payoff relations, again for the two examples of a public goods game and a volunteer's dilemma. In particular, it shows that the space of enforceable payoff relations shrinks with group size. Proposition 2 confirms that this effect can be observed for all social dilemmas (more specifically, for all games that satisfy bj+i > aj). Thus, in larger groups, a single player has less strategic options to enforce particular payoff combinations. 3 ZD strategies for alliances To extend this result for single subjects to alliances, let us suppose the first k players form an alliance A = {1 ..... and they agree on a joint zero•determinant with parameters /, s, 4 Thus, each of the allies E A enforces the relation tr_i = Slii -I- (1 - .$)1. Summing up over all allies 1 ≤ i ≤ k yields k k 1— 1 (iri + irk) + IL(liki-i + • • • + irn) = s(irr ... irk) k(1 s)1. [Sill - Rearranging these terms then implies 74:+1 + ... + ir. _ s(n — 1) — (k - 1) Cr 1 + ... -i- Trk )-F ( s(n — 1) — (k — 1)) 1 1, [5121 n — k n — k k n — k or, in a more intuitive notation, r -.4 = sAff.4 + (1 - 54)1, [S131 20 EFTA01074284 with .2r4 being the mean payoff of the allies, ir_4 being the mean payoff of the outsiders, and $4 n — k s(n — 1) — (k — 1) [SI41 being the effective slope of the alliance. Thus the results for a single ZD strategist natur