# Cooperation and control in multiplayer social dilemmas

See allHide authors and affiliations

Edited by Joshua B. Plotkin, University of Pennsylvania, Philadelphia, PA, and accepted by the Editorial Board September 26, 2014 (received for review April 30, 2014)

## Significance

Many of the world’s most pressing problems, like the prevention of climate change, have the form of a large-scale social dilemma with numerous involved players. Previous results in evolutionary game theory suggest that multiplayer dilemmas make it particularly difficult to achieve mutual cooperation because of the lack of individual control in large groups. Herein, we extend the theory of zero-determinant strategies to multiplayer games to describe which strategies maintain cooperation. Moreover, we propose two simple models of alliances in multiplayer dilemmas. The effect of these alliances is determined by their size, the strategy of the allies, and the properties of the social dilemma. When a single individual’s strategic options are limited, forming an alliance can result in a drastic leverage.

## Abstract

Direct reciprocity and conditional cooperation are important mechanisms to prevent free riding in social dilemmas. However, in large groups, these mechanisms may become ineffective because they require single individuals to have a substantial influence on their peers. However, the recent discovery 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 iterated 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 theory to describe strategies that sustain cooperation, including generalized variants of Tit-for-Tat and Win-Stay Lose-Shift. Moreover, we explore two models that show how individuals can further enhance their strategic options by coordinating their play with others. Our results highlight the importance of individual control and coordination to succeed in large groups.

Cooperation among self-interested individuals is generally difficult to achieve (1⇓–3), but typically the free rider problem is aggravated even further when groups become large (4⇓⇓⇓⇓–9). In small communities, cooperation can often be stabilized by forms of direct and indirect reciprocity (10⇓⇓⇓⇓⇓⇓–17). For large groups, however, it has been suggested that these mechanisms may turn out to be ineffective, as it becomes more difficult to keep track of the reputation of others and because the individual influence on others diminishes (4⇓⇓⇓–8). 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 (18⇓⇓⇓–22).

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 (23) 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 coplayer’s payoff, irrespective of the coplayer’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 coplayer’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 (24⇓⇓⇓⇓⇓–30).

ZD strategies are not confined to the repeated prisoner’s dilemma. Recently published studies have shown that ZD strategies also exist in other repeated two player games (29) or in repeated public goods games (31). Herein, we will show that such strategies exist for all symmetric social dilemmas, with an arbitrary number of participants. We use this theory to describe which ZD strategies can be used to enforce fair outcomes or to prevent free riders from taking over. Our results, however, are not restricted to the space of ZD strategies. By extending the techniques introduced by Press and Dyson (23) and Akin (27), we also derive exact conditions when generalized versions of Grim, Tit-for-Tat, and Win-Stay Lose-Shift allow for stable cooperation. In this way, we find that most of the theoretical solutions for the repeated prisoner’s dilemma can be directly transferred to repeated dilemmas with an arbitrary number of involved players.

In addition, we also propose two models to explore how individuals can further enhance their strategic options by coordinating their play with others. To this end, we extend the notion of ZD strategies for single players to subgroups of players (to which we refer as ZD alliances). We analyze two models of ZD alliances, depending on the degree of coordination between the players. When players form a strategy alliance, they only agree on the set of alliance members, and on a common strategy that each alliance member independently applies during the repeated game. When players form a synchronized alliance, on the other hand, they agree to act as a single entity, with all alliance members playing the same action in a given round. We show that the strategic power of ZD alliances depends on the size of the alliance, the applied strategy of the allies, and on the properties of the underlying social dilemma. Surprisingly, the degree of coordination only plays a role as alliances become large (in which case a synchronized alliance has more strategic options than a strategy alliance).

To obtain these results, we consider a repeated social dilemma between *n* players. In each round of the game, players can 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 (Fig. 1*A*): in a group in which *j* of the other group members cooperate, a cooperator receives the payoff *i*) irrespective of the own strategy, players prefer the other group members to cooperate (*j*); (*ii*) within any mixed group, defectors obtain strictly higher payoffs than cooperators (*j*); and (*iii*) mutual cooperation is favored over mutual defection *B*). In the first example, the public goods game (33), cooperators contribute an amount *r* (with *j*), whereas defectors yield

We assume that the social dilemma is repeated, such that individuals can react to their coplayers’ past actions (for simplicity, we will focus here on the case of an infinitely repeated game). 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 nontrivial ways. Nevertheless, as in pairwise games, ZD strategies turn out to be surprisingly simple.

## Results

### Memory-One Strategies and Akin’s Lemma.

ZD strategies are memory-one strategies (23, 36); they only condition their behavior on the outcome of the previous round. Memory-one strategies can be written as a vector *j* of the coplayers cooperated (in the *SI Text*, we present an extension in which players additionally take into account who of the coplayers cooperated). A simple example of a memory-one strategy is the strategy Repeat,

Let us consider a repeated game in which a focal player with memory-one strategy **p** interacts with *t* is **v** is a limit point for

There is a surprisingly powerful relationship between a focal player’s memory-one strategy and the resulting limit distribution of the iterated game. To show this relationship, let *t*. By definition of *t*, and dividing by *t*, yields **1** has been first highlighted by Akin (27) in the context of the pairwise prisoner’s dilemma, we will refer to it as Akin’s lemma. We note that Akin’s lemma is remarkably general, because it neither makes any assumptions on the specific game being played, nor does it make any restrictions on the strategies applied by the remaining

### Zero-Determinant Strategies in Multiplayer Social Dilemmas.

As an application of Akin’s lemma, we will show in the following that single players can gain an unexpected amount of control over the resulting payoffs in a multiplayer social dilemma. To this end, we first need to introduce some further notation. For a focal player *i*, let us write the possible payoffs in a given round as a vector *i*’s coplayers as **1** denote the *i*’s payoff in the repeated game as *i*’s coplayers as **v** as a limit distribution, it follows that *i* applies the memory-one strategy*α*, *β*, and *γ* being parameters that can be chosen by player *i* (with the only restriction that *i*’s strategy thus guarantees that the resulting payoffs of the repeated game obey a linear relationship, irrespective of how the other group members play. Moreover, by appropriately choosing the parameters *α*, *β*, and *γ*, the player has direct control on the form of this payoff relation. As in Press and Dyson (23), who were first to discover such strategies for the prisoner’s dilemma, we refer to the memory-one strategies in Eq. **2** as zero-determinant strategies or ZD strategies.

For our purpose, it will be convenient to proceed with a slightly different representation of ZD strategies. Using the parameter transformation **3** becomes*l* as the baseline payoff of the ZD strategy and to *s* as the strategy’s slope. Both parameters allow an intuitive interpretation: when all players adopt the same ZD strategy **p** such that **5** that each player yields the payoff *l*. The value of *s* determines how the mean payoff of the other group members *ϕ* does not have a direct effect on Eq. **5**; however, the magnitude of *ϕ* determines how fast payoffs converge to this linear payoff relationship as the repeated game proceeds (37).

The parameters *ϕ* of a ZD strategy cannot be chosen arbitrarily, because the entries *SI Text*, we show that exactly those relations **5** can be enforced for which either *l* in the definition of ZD strategies becomes irrelevant) or for which *l* and *s* sufficiently close to 1, any baseline payoff between **6** become increasingly restrictive as the group size *n* increases, larger groups make it more difficult for players to enforce specific payoff relationships.

### Important Examples of ZD Strategies.

In the following, we discuss some examples of ZD strategies. At first, let us consider a player who sets the slope to **5**, such a player enforces the payoff relation *i*’s payoff matches the average payoff of the other group members. We call such ZD strategies fair. As shown in Fig. 2*A*, fair strategies do not ensure that 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. Our characterization **6** implies that all social dilemmas permit a player to be fair, irrespective of the group size. As an example, consider the strategy proportional Tit-for-Tat (*pTFT*), for which the probability to cooperate is simply given by the fraction of cooperators among the coplayers in the previous round*pTFT* simplifies to Tit-for-Tat, which is a fair ZD strategy (23). However, also for the public goods game and for the volunteer’s dilemma, *pTFT* is a ZD strategy, because it can be obtained from Eq. **4** by setting *c* being the cost of cooperation.

As another interesting subclass of ZD strategies, let us consider strategies that choose the mutual defection payoff as baseline payoff, **5** becomes *s* of any surplus over the mutual defection payoff. Moreover, as the slope *s* is positive, the payoffs *i*’s payoffs by cooperating in every round. In analogy to Press and Dyson (23), we call such ZD strategies extortionate, and we call the quantity **5** shows that the extortion factor can be written as *i*. Extortionate strategies 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 *i* performs at least as well as the other group members (as also depicted in Fig. 2*B*). As an example, let us consider a public goods game and a ZD strategy **4** implies*pTFT*. As *s* decreases from 1, the cooperation probabilities of **[6]** by setting *s* close to 1). However, larger groups make extortion more difficult. For example, in public goods games with **[6]** implies that there is an upper bound on *χ* (*SI Text*).

As the benevolent counterpart to extortioners, Stewart and Plotkin described a set of generous strategies for the iterated prisoner’s dilemma (24, 28). Generous players set the baseline payoff to the mutual cooperation payoff *C*). For the example of a public goods game, we obtain a generous ZD strategy *pTFT*, whereas lower values of *s* make

As a last interesting class of ZD strategies, let us consider players who choose **5**, such players enforce the payoff relation

### Stable Cooperation in Multiplayer Social Dilemmas.

Let us next explore which ZD strategies give rise to a Nash equilibrium with stable cooperation. In *SI Text*, we prove that such ZD strategies need to have two properties: they need to be generous (by setting *s* needs to approach 1, suggesting that ZD strategies need to become fair. For the public goods game, this implies that stable cooperation can always be achieved when players cooperate in the first round and adopt proportional Tit-for-Tat thereafter. Interestingly, this strategy has received little attention in the previous literature. Instead, researchers have focused on other generalized versions of Tit-for-Tat, which cooperate if at least *k* coplayers cooperated in the previous round (4, 39, 40). Such memory-one strategies take the form *pTFT* may be the more natural generalization of Tit-for-Tat in large-scale social dilemmas.

In addition to the stable ZD strategies, Akin’s lemma also allows us to characterize all pure memory-one strategies that sustain mutual cooperation. In *SI Text*, we show that any such strategy **p** needs to satisfy the following four conditions*C* after mutual cooperation; the second condition **10** imply that the threshold variants of Tit-for-Tat discussed above are only a Nash equilibrium if they use the most stringent threshold: *WSLS*, because for pairwise dilemmas it corresponds to the Win-Stay, Lose-Shift strategy described by ref. 36. Because of condition **[10]**, *WSLS* is a Nash equilibrium if and only if the social dilemma satisfies *WSLS* provides a stable route to cooperation that is robust to errors.

### Zero-Determinant Alliances.

In agreement with most of the theoretical literature on repeated social dilemmas, our previous analysis is based on the assumption that individuals act independently. As a result, we observed that a player’s strategic options typically diminish with group size. As a countermeasure, subjects may try to gain strategic power by coordinating their strategies with others. In the following, we thus extend our theory of ZD strategies for single individuals to subgroups of players. We refer to these subgroups as ZD alliances. Because the strategic power of ZD alliances is likely to depend on the exact mode of coordination between the allies, we consider two different models: when subjects form a strategy alliance, they only agree on the set of alliance members and on a common ZD strategy that each ally independently applies. During the actual game, there is no further communication between the allies. Strategy alliances can thus be seen as a boundary case of coordinated play, which requires a minimum amount of coordination. Alternatively, we also analyze synchronized alliances, in which all allies synchronize their actions in each round (i.e., the allies cooperate collectively, or they defect collectively). In effect, such a synchronized alliance thus behaves like a new entity that has a higher leverage than each player individually. Synchronized alliances thus may be considered as a boundary case of coordinated play that requires substantial coordination.

To model strategy alliances, let us consider a group of **p** during the repeated game. Because the ZD strategy needs to allow allies to differentiate between the actions of the other allies and the outsiders, we need to consider a more general state space than before. The state space now takes the form *S* corresponds to the focal player’s own play in the previous round, **p** again needs to specify a cooperation probability *i* in a strategy alliance as**4** and **11** are equivalent.

Similarly to the case of single individuals, we can apply Akin’s lemma to show that strategy alliances enforce a linear relationship between their own mean payoff *SI Text*)**12** for which either *l* and *SI Text*), such that the allies are stronger affected by what the other allies do, as opposed to the actions of the outsiders. For single player alliances, **13** again simplifies to the previous condition **6**. However, as the alliance size **13** becomes easier to satisfy. Larger alliances can therefore enforce more extreme payoff relationships. For the example of a public goods game, we noted that single players cannot be arbitrarily extortionate when

In a similar way, we can also analyze the strategic possibilities of a synchronized alliance. Because synchronized alliances act as a single entity, they transform the symmetric social dilemma between *n* independent players to an asymmetric game between **4**. By applying Akin’s lemma to Eq. **14**, we conclude that synchronized alliances enforce **12** for strategy alliances. Surprisingly, we even find that for reasonable alliance sizes, *l* and **13** (see *SI Text* for details). Thus, for the two models of ZD alliances considered here, the exact mode of coordination is irrelevant for the alliance’s strategic power unless the alliance has reached a substantial size.

Table 1 gives an overview of our findings on ZD strategies and ZD alliances in multiplayer social dilemmas. It shows that, although 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 ZD alliances then allows players to increase their strategic scope. The impact of a given ZD alliance, however, depends on the specific social dilemma: although ZD alliances can become arbitrarily powerful in public goods games, their strategic options remain limited in the volunteer’s dilemma.

## Discussion

When Press and Dyson (23) discovered the new class of ZD strategies for the repeated prisoner’s dilemma, this came as a big surprise (24, 25): after more than five decades of research, it seemed unlikely that any major property of the prisoner’s dilemma has been overlooked. For repeated multiplayer dilemmas the situation is different. Although various Folk theorems guarantee that cooperation is also feasible in large groups (42, 43), there has been considerably less theoretical research on the evolution of cooperation in repeated multiplayer dilemmas (4, 5, 39, 40). This lack of research may be due to the higher complexity: the mathematics of repeated *n*-player dilemmas seems to be more intricate, and numerical investigations are impeded because the time to compute payoffs increases exponentially in the number of players (5). Nevertheless, we showed here that many of the results for the repeated prisoner’s dilemma can be directly transferred to general social dilemmas, with an arbitrary number of involved subjects. The foundation for this progress is a new framework, provided by Akin’s lemma and the theory of Press and Dyson.

Using this framework, we extended the theory of repeated multiplayer dilemmas into three directions. The first and most immediate direction is our finding that ZD strategies exist in all social dilemmas. These strategies allow players to unilaterally 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 other group members. In particular, we showed that any social dilemma allows players to be fair, extortionate, or generous. Each of these strategy classes has its own particular strengths: extortionate strategies give a player a relative advantage compared with the other group members; fair strategies help to avoid further inequality within a group; and generous strategies allow players to revert to mutual cooperation when a coplayer defected by accident. At the same time, ZD strategies are remarkably simple. For example, to be fair in a public goods game, players only need to apply a rule called proportional Tit-for-Tat: if *j* of the *pTFT* to the own advantage or to the advantage of the others.

As the second direction, we explored which ZD strategies and which pure memory-one strategies can be used to sustain cooperation in multiplayer dilemmas. Among ZD strategies, such strategies need to be generous (such that players never try to outperform their peers) (27, 28), but at the same time they must not be too generous. The right degree of generosity depends on the size of the group but not on the specific social dilemma being played. As a rule of thumb, we obtain that in larger groups, subjects are required to show less generosity.

As the last direction, we extended the concept of zero-determinant strategies from single players to subgroups of players, to which we refer to as ZD alliances. Depending on the degree of coordination, we explored two forms of ZD alliances: members of a strategy alliance only agree on using a common ZD strategy during the game, but they do not coordinate each of their decisions; members of a synchronized alliance, on the other hand, act as a single entity—they either all cooperate or they all defect in a given round. The effect of such ZD alliances depends on the size of the alliance, the applied strategy, and the properties of the underlying social dilemma. In general, we find that by coordinating their play with others, subjects can increase their strategic options considerably. The exact mode of coordination, however, only turns out to play a minor role: As long as the size of the ZD alliance is below half the group size, strategy alliances and synchronized alliances have the same strategic power. In addition to their static properties, ZD strategies for the prisoner’s dilemma also have a remarkable dynamic component (23, 44): when a player commits himself to an extortionate ZD strategy, then adapting coplayers learn to cooperate over time. Numerical simulations in the SI show an analogous result for multiplayer dilemmas: when ZD alliances apply strategies with a positive slope, they can trigger a positive group dynamics among the outsiders. The magnitude of this dynamic effect again depends on the size of the alliance, and on the applied strategy of the allies.

Here, we focused on ZD strategies; but the toolbox that we apply (in particular Akin’s lemma) is more general. As an example, we identified all pure memory-one strategies that allow for stable cooperation, including the champion of the repeated prisoner’s dilemma, Win-Stay Lose-Shift (36, 45). We expect that there will be further applications of Akin’s lemma to come. Such applications may include, for instance, a characterization of all Nash equilibria among the stochastic memory-one strategies or an analysis of how alliances are formed and whether evolutionary forces favor particular alliances over others (46, 47).

Overall, our results reveal how single players in multiplayer games can increase their control by choosing the right strategies and how they can increase their strategic options by joining forces with others.

## Acknowledgments

C.H. gratefully acknowledges generous funding by the Schrödinger scholarship of the Austrian Science Fund (J3475).

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. Email: hilbe{at}fas.harvard.edu.

Author contributions: B.W. initiated the project; C.H., B.W., A.T., and M.A.N. designed research; C.H., B.W., A.T., and M.A.N. performed research; and C.H., B.W., A.T., and M.A.N. wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission. J.B.P. is a guest editor invited by the Editorial Board.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1407887111/-/DCSupplemental.

Freely available online through the PNAS open access option.

## References

- ↵.
- Hardin G

- ↵.
- Olson M

- ↵.
- Nowak MA

- ↵
- ↵.
- Hauert C,
- Schuster HG

- ↵
- ↵.
- Santos FC,
- Pacheco JM

- ↵
- ↵.
- Yang W, et al.

- ↵
- ↵.
- Axelrod R

- ↵.
- Alexander R

- ↵.
- Wedekind C,
- Milinski M

- ↵
- ↵
- ↵.
- van Veelen M,
- García J,
- Rand DG,
- Nowak MA

- ↵
- ↵
- ↵.
- Ostrom E

- ↵
- ↵
- ↵.
- Hilbe C,
- Traulsen A,
- Röhl T,
- Milinski M

- ↵.
- Press WH,
- Dyson FJ

- ↵.
- Stewart AJ,
- Plotkin JB

- ↵
- ↵.
- Hilbe C,
- Nowak MA,
- Sigmund K

- ↵.
- Akin E

- ↵.
- Stewart AJ,
- Plotkin JB

- ↵
- ↵
- ↵.
- Pan L,
- Hao D,
- Rong Z,
- Zhou T

- ↵
- ↵.
- Kagel JH,
- Roth AE

- Ledyard JO

- ↵
- ↵.
- Milinski M,
- Sommerfeld RD,
- Krambeck H-J,
- Reed FA,
- Marotzke J

- ↵
- ↵
- ↵
- ↵.
- Kurokawa S,
- Ihara Y

- ↵
- ↵.
- Sigmund K

- ↵.
- Friedman J

- ↵.
- Fudenberg D,
- Tirole J

- ↵
- ↵
- ↵.
- Peleg B,
- Sudhölter P

- ↵

## Citation Manager Formats

## Article Classifications

- Biological Sciences
- Evolution

- Social Sciences
- Social Sciences