2023 [1]Richard Willis [1] King’s College London, London, United Kingdom
2]Google DeepMind, London, United Kingdom 3]University of Sussex, Sussex,
United Kingdom

# Resolving social dilemmas with minimal reward transfer

<EMAIL_ADDRESS>Yali Du<EMAIL_ADDRESS>Joel Z. Leibo
<EMAIL_ADDRESS>Michael Luck<EMAIL_ADDRESS>*  [  [

###### Abstract

Multi-agent cooperation is an important topic, and is particularly challenging
in mixed-motive situations where it does not pay to be nice to others.
Consequently, self-interested agents often avoid collective behaviour,
resulting in suboptimal outcomes for the group. In response, in this paper we
introduce a metric to quantify the disparity between what is rational for
individual agents and what is rational for the group, which we call the
general self-interest level. This metric represents the maximum proportion of
individual rewards that all agents can retain while ensuring that achieving
social welfare optimum becomes a dominant strategy. By aligning the individual
and group incentives, rational agents acting to maximise their own reward will
simultaneously maximise the collective reward. As agents transfer their
rewards to motivate others to consider their welfare, we diverge from
traditional concepts of altruism or prosocial behaviours. The general self-
interest level is a property of a game that is useful for assessing the
propensity of players to cooperate and understanding how features of a game
impact this. We illustrate the effectiveness of our method on several novel
games representations of social dilemmas with arbitrary numbers of players.

###### keywords:

Game Theory, Social Dilemma, Reward Transfer, Cooperation

## Acknowledgement

This work was supported by UK Research and Innovation [grant number
EP/S023356/1], in the UKRI Centre for Doctoral Training in Safe and Trusted
Artificial Intelligence (www.safeandtrustedai.org) and a BT/EPSRC funded iCASE
Studentship [grant number EP/T517380/1].

##  1 Introduction

Social dilemmas are situations in which individuals can either act selfishly
for their personal gain, or act in a prosocial manner to help the collective,
which delivers more benefits overall. The problem with social dilemmas is that
it does not pay to be nice to others; individuals have incentives to act in
ways that undermine socially optimal outcomes. As a result, self-interested
agents will shirk collective behaviour, leading to poor outcomes for everyone.
Although every agent prefers the mutual collective behaviour over mutual
selfish behaviour, individually they are powerless to bring this about. This
tension between collective and individual rationality is characterised by
agents who engage in selfish behaviour outperforming agents engaged in
collective behaviour within a group, but prosocial groups outperforming
selfish groups.

For example, suppose a group of villagers has unrestricted access to a wood,
and each villager can profit from logging trees. The number of trees that can
be harvested at a sustainable level is limited, however, and the wood will
degrade if excessive logging takes place. The collective does best when the
wood is managed sustainably, which maximises the number of trees that can be
logged over time, but the villagers individually profit from each additional
tree they harvest. This particular social dilemma represents a common pool
resource, and is known as a _tragedy of the commons_.

Social dilemmas are important because they occur in many diverse situations,
and there remain examples of failures to enact collective action in the world
today. Real world social dilemmas include the routine administration of
antibiotics to farm animals, which benefits the farmer at the expense of
increasing antibiotic resistance, with negative impacts upon society.
Similarly, in file sharing networks, where users can either act for personal
gain by downloading files or help the network by uploading files, there exist
so called _free-riders_ who do not contribute. Consequently, methods to
resolve such dilemmas, achieved by causing all agents to prefer to take
collective action, are important.

While humans have developed biases, norms, institutions and other mechanisms
that help them to cooperate in such situations
ostrom92__covenants_with_and_without_a_sword ;
dietz03__the_struggle_to_govern_the_commons , it isn’t clear that artificial
agents will develop the same behaviours. As the prevalence of artificial
agents continues to rise in the world, it is increasingly important to find
solutions applicable to them. The algorithms used by artificial agents
typically make decisions based on logic and mathematics, so we believe there
is a need for solutions that apply to instrumentally rational agents.

Many solutions to social dilemmas have been developed
apt14__selfishness_level_of_strategic_games ;
deng18__disarmament_games_with_resources ;
nowak06__five_rules_for_the_evolution_of_cooperation ;
hughes18__inequity_aversion_improves_cooperation_in_intertemporal_social_dilemmas
; hughes20__learning_to_resolve_alliance_dilemmas_in_manyplayer_zero-sum_games
, but they typically have specific requirements to be applicable, such as
relying upon agents to have prosocial preferences, which limits their
applicability. We argue a solution should require only a single agreement
between participants, be able to scale to an arbitrary number of agents,
require only the incentives present in the scenario, and not require agents to
have private knowledge of, or previous experience with, others. To our
knowledge, only a potential application of trading in shares of future rewards
schmid22__learning_to_participate_through_trading_of_reward_shares  could meet
these criteria.

In this paper, therefore, we propose a solution that resolves social dilemmas
while addressing the issues highlighted above. The key principle underpinning
our approach is that if we sufficiently align the individual and group
incentives, then rational agents maximising their own rewards will also
maximise the group rewards. Using an approach from game theory, we represent
social dilemmas abstractly as games. We say that an agent _defects_ when it
acts selfishly, and that it _cooperates_ when it acts to improve social
outcomes. To align individual incentives, we introduce the concept of the
agents committing to share proportions of their future game rewards with each
other, a technique that we label _reward transfer_. By engaging in reward
transfer, an agent incentivises the recipients to help it prosper which,
paradoxically, can lead to a net profit for the transferring agent if it
causes a beneficial behavioural change in the recipients.

We investigate two specific instances of reward transfer, first when all
agents exchange the same proportion of their reward with each other. We show
that a sufficiently large amount of reward transfer from all agents is
guaranteed to resolve a social dilemma, and we determine the minimum
proportion that must be exchanged to do so. Second, we investigate the general
case, when each player may transfer any amount of their reward to any other
player, and introduce a method to find the minimum transfer arrangement that
will resolve a social dilemma. By determining the maximum amount of their own
reward that agents may keep for themselves while resolving a social dilemma,
we quantify, for a given game, the discrepancy between what is rational for
the individual compared to the collective. If, in order to take prosocial
actions, individuals can only retain a small amount of self-interest, then
cooperation is challenging in this game. Conversely, if agents can keep a
large proportion of their own rewards, needing only to transfer small
proportions to others, then the game is conducive to collective action. This
provides our work with a descriptive element. By determining the minimal
amount of reward that must be transferred to others, agents can use our
results as a prescriptive efficient solution to social dilemmas, by entering
the proposed transfers contract, which makes cooperation rational for all.

Concretely, we make the following contributions: we propose a novel
formalisation of social dilemmas and what it means to resolve them; we develop
a metric quantifying the minimum proportion of future rewards that must be
exchanged by all agents to resolve a social dilemma; we develop a second, more
general metric which represents the maximum self-interest agents can retain
under reward transfers to resolve a dilemma; we then introduce novel multi-
player social dilemma games and provide results for them.

The paper is structured as follows. In Section 2 we review existing work on
game metrics and on solutions to facilitating collective action in social
dilemmas. Our main contribution is developed in Section 3, and we provide
results in Section 4. Finally, we conclude with a discussion in Section 5.

##  2 Related work

We begin by comparing the descriptive element of our work to other game
theoretical metrics which quantify properties of a game in Section 2.1. The
rest of the discussion looks at mechanisms to achieve collective action in
social dilemmas, and we position our work relative to them. We start with
norms and strategic play (Sections 2.2 and 2.3), which are behavioural
solutions that discourage antisocial behaviour, often through punishing
offenders. We then deal with approaches which lead learning algorithms to
cooperate in social dilemmas via the use of intrinsic rewards in Section 2.4.
Next, we consider how we can extend games with notions of commitments in
Section 2.5. The final Subsection 2.6 discusses extending games with reward
transfer, which is the same mechanism we use in our work.

###  2.1 Metrics

Metrics are used to quantify and describe features of a game. Certain metrics
specify how difficult it is to achieve a certain outcome. For example, _K-
implementation_ deng16__complexity_and_algorithms_of_kimplementation
determines how costly it would be for a third party to provide additional
incentives to make a particular game outcome dominant. The _selfishness level_
of a game measures the willingness of the players to cooperate
apt14__selfishness_level_of_strategic_games ; it is the smallest fraction of
the social welfare of each outcome that needs to be offered to each player so
that a social optimum is realised in a pure Nash equilibrium. The selfishness
level both describes some aspect of a game and suggests a solution to
achieving a social optimum by providing players with sufficient additional
incentives. Our work is closely related, but our solution concept is more
general, because we can, in effect, offer different amounts to different
players within the same game outcome. The selfishness level uses a model of
altruism based upon elias10__sociallyaware_network_design_games  and finds
equivalent results for the models of altruism proposed in
chen08__altruism_selfishness_and_spite_in_traffic_routing ;
chen11__the_robust_price_of_anarchy_of_altruistic_games ;
caragiannis10__the_impact_of_altruism_on_the_efficiency_of_atomic_congestion_games
. Though we do not base our solution concept on altruism, one of our metrics
has a similar form to that of Chen and Kempe
chen08__altruism_selfishness_and_spite_in_traffic_routing .

Other metrics measure a notion of the price a group of agents pays when they
seek a particular solution concept instead of a social optima. The Price of
Anarchy koutsoupias09__worstcase_equilibria , Price of Stability
anshelevich04__the_price_of_stability_for_network_design_with_fair_cost_allocation
and Price of Pareto Optimality
elkind20__price_of_pareto_optimality_in_hedonic_games  measure the ratio
between the best Nash equilibrium, the worst Nash equilibrium or worst Pareto
optimal outcome (respectively) and a social welfare optimum. Although these
metrics assess the quality of certain game outcomes, they say little about how
such outcomes are achieved. In our work, we find values that make a single
social welfare dominant, but we could alternatively be satisfied to find a
value that made one of the above metrics equal to one.

###  2.2 Norms

Societies, often have collective expectations of behaviours that are enforced.
For example, most communities expect their members to dispose refuse
appropriately, and littering likely attract social sanctions, such as being
called out. These expected behaviours are called _norms_. Successful norms are
self-sustaining, because it is beneficial to follow them, or because the
agents internalise the behaviours. A norm can be supported by _punishment_ ,
whereby any agent who violates the norm is penalised by other members of their
group. Norms can be viewed as a soft constraint: an agent is not forced to
undertake the behaviour prescribed by a norm, but they usually will because it
is typically in their best interests to do so.

Axelrod axelrod86__an_evolutionary_approach_to_norms , and Mahmoud et al.
mahmoud10__an_analysis_of_norm_emergence_in_axelrods_model  investigated when
a norm can be evolutionary stable. Researchers have investigated how to
determine the most effective norms to promote a given set of values
montes21__valueguided_synthesis_of_parametric_normative_systems ;
sierra21__value_alignment  or experimentally found norms which lead to the
reciprocity of cooperation ohtsuki06__the_leading_eight . Others have
investigated the societal effects when agents have either guilt or fairness
norms
pereira17__social_manifestation_of_guilt_leads_to_stable_cooperation_in_multiagent_systems
;
lorini18__the_longterm_benefits_of_following_fairness_norms_under_dynamics_of_learning_and_evolution
. Limitations of norms include the fact that they are not always beneficial to
society, such as norms around gender roles, and they can be difficult to
introduce and establish. We are interested in solutions to social dilemmas
that are not dependent upon shared behavioural expectations, so that they can
be immediately utilised by novel groups of agents.

###  2.3 Strategic play

Repeated games and games involving a temporal component can permit cooperative
strategies if they are enforceable via punishment
jacq20__foolproof_cooperative_learning . In the famous example, _Tit-For-Tat_
axelrod80__effective_choice_in_the_prisoners_dilemma  plays the action its
partner chose in the previous round, and thus reciprocates cooperation while
minimising any exploitation from a defecting partner. In a two player repeated
game social dilemma, a strategy can be robust to exploitation attempts if it
only recalls the result of the last game
press12__iterated_prisoners_dilemma_contains_strategies_that_dominate_any_evolutionary_opponent
. In these circumstances, a strategy can stabilise cooperation with a partner
by ensuring that their opponent does best under mutual cooperation, and that
it is costly for their opponent to outperform them
hilbe13__evolution_of_extortion_in_iterated_prisoners_dilemma_games ;
stewart13__from_extortion_to_generosity_evolution_in_the_iterated_prisoners_dilemma
. Unfortunately, it can be difficult to detect when an opponent is defecting,
and other players still have an incentive to defect if they can avoid
punishment. Strategic play is therefore difficult in settings with hidden
information. Our approach uses incentives instead of punishments to prevent
opponents from defecting.

The success of a strategy depends upon the other strategies it encounters. It
can be useful to consider how the composition of strategies in a population
will change over time, using techniques such as evolutionary game theory or
replicator dynamics hofbauer03__evolutionary_game_dynamics ;
nowak04__evolutionary_dynamics_of_biological_games . Using these techniques,
it is possible to investigate conditions that can lead to the emergence of
cooperation in a population
nowak06__five_rules_for_the_evolution_of_cooperation . Unfortunately, the
existence of punishment actions does not guarantee that it will be used in
support of cooperation, as it can also be used by selfish agents to punish
cooperators to prevent them from succeeding
rand11__the_evolution_of_antisocial_punishment_in_optional_public_goods_games
.

Due to backwards induction, cooperation can often only be a Nash equilibrium
if games are infinitely repeated, and if they are, then according to the _folk
theorem_ leyton-brown08__essentials_of_game_theory  , there become infinitely
many Nash equilibria, which can lead to players disagreeing over their
preferred equilibria. Consequently, strategic play can add cooperative
equilibria, because it only increases the range of strategies available to the
players, it does not remove equilibria that lead to poor outcomes. Our
solution is effective in zero-shot single-round games and avoids the need for
punishment.

###  2.4 Reward shaping

A rational, self-interested agent only cares about the rewards it receives in
a game, but agent designers can include additional factors beyond the game
reward to influence agent behaviour. For example, in reinforcement learning
literature, _reward shaping_ modifies a player’s reward function during
training to include auxiliary intrinsic rewards that encourage certain
behaviours.

When an intrinsic reward is proportional to the mean collective reward
peysakhovich17__prosocial_learning_agents_solve_generalized_stag_hunts_better_than_selfish_ones
, it is regarded as a _prosocial reward_ , and has been shown to help
reinforcement learning agents converge to a better equilibrium in a social
dilemma called Stag Hunt (Table 1(c)). McKee et al.
mckee20__social_diversity_and_social_preferences_in_mixedmotive_reinforcement_learning
generate different degrees of prosocial rewards in mixed-motive games; they
train populations with homogeneous and heterogeneous preferences and find some
evidence that heterogeneous populations achieve more equal payoffs.

According to Haeri haeri21__rewardsharing_relational_networks_in_multi-
agent_reinforcement_learning_as_a_framework_for_emergent_behavior , an agent
can be considered to have a relationship with another specific agent if it has
a personal reward term that depends upon the reward of the other agent. In the
general case, a weighted graph can be used to specify the relationships
between all agents; Haeri investigates how different relationship networks
lead to differences in performance. Rather than specifying the form of the
reward shaping by hand, they can be determined via an optimisation process,
for example by using a genetic algorithm to optimise a reward network
wang19__evolving_intrinsic_motivations_for_altruistic_behavior .

Alternatively, using reward shaping so that agents receive a negative
intrinsic reward when they achieve lower than average rewards creates an
incentive for the group to prefer egalitarian rewards
hughes18__inequity_aversion_improves_cooperation_in_intertemporal_social_dilemmas
. This can be an effective approach in social dilemmas where agents have
access to a punishment mechanism: when an agent benefits from selfish
behaviour, the other agents receive lower than average rewards, and their
intrinsic reward motivates them to punish the selfish agent. In this way,
punishment helps to prevent agents from learning selfish behaviour.

While reward shaping has proven effective at promoting collective behaviour in
social dilemmas, it often does not explain where the additional rewards come
from, relying upon an innate disposition of the agents themselves. By
adjusting behaviour to include factors beyond the game reward, intrinsic
motivations may not be rational for a self-interested agent to include, which
may consequently be of limited value with a group of self-interested,
independent agents. Our approach similarly modifies the rewards to agents, in
order to shape their behaviour, but it does so using only the extrinsic game
rewards.

###  2.5 Commitments and contracts

In social dilemmas, the key question is how to ensure mutual cooperation. One
option is to use _binding agreements_ , or contracts, between players, which
are known as _cooperative games_ in game theory literature. Hughes et al.
hughes20__learning_to_resolve_alliance_dilemmas_in_manyplayer_zero-sum_games
demonstrate how extending a stochastic game to include a protocol for agreeing
joint action contracts improves outcomes in social dilemmas. If contracts can
include a _side payment_ , then an agent can be paid to take an action that
benefits another. Building on this, Christoffersten et al.
christoffersen22__get_it_in_writing  formalised contracts for stochastic games
to include payments. While it isn’t clear how much should be transferred, a
fixed point about which players of a two-player game could negotiate the fair
value of a joint action, called the Coco value, has been proposed
sodomka13__cocoq . While joint action contracts provide assurance of
behaviour, they can be burdensome to specify: Not only must an agent be able
to specify the contracts it would enter for all possible joint actions in all
possible states, if it is costly to write a contract, then agents will incur a
cost for each timestep they enter one.

Instead of a joint commitment to play certain actions, Deng and Conitzer
propose that a player could alternatively commit unilaterally to avoid playing
certain (possibly mixed) strategies, a method called _disarmament_
deng17__disarmament_games ; deng18__disarmament_games_with_resources . By
removing all non-prosocial actions, or at least reducing the probability that
an agent may play them, better social outcomes can be achieved. Deng and
Conitzer deng17__disarmament_games ; deng18__disarmament_games_with_resources
introduce a negotiation protocol that leads to improvements in the expected
welfare of the participants, but disarmament cannot resolve all social
dilemmas.

###  2.6 Reward transfer

Reward transfer is a technique whereby agents send and receive reward from
each other in a zero-sum manner. An agent might choose to transfer reward to
another in order to influence the behaviour of the recipient, so that the
transferee may benefit. Explicitly adding an action that allows a player to
gift reward to their peers has been investigated in a tragedy of the commons
scenario lupu20__gifting_in_multiagent_reinforcement_learning  and in
coordination games
wang21__emergent_prosociality_in_multiagent_games_through_gifting . Yang et
al. yang20__learning_to_incentivize_other_learning_agents  optimise the
transferred reward to shape the behaviour of learning algorithms to improve
the overall reward to the gifting agent. Similar to the limitations on
contracts (Section 2.5), if reward is transferred at the granularity of
individual actions, then a strategy needs to include the transfers it would
make for all joint actions for all states, which is burdensome. Our solution
is simpler in that this decision is made only once, before the game is played.

An alternative to specifying payments for actions is to take a stake in the
future outcomes of an agent through the trading of reward shares, as suggested
by Schmid et al.
schmid22__learning_to_participate_through_trading_of_reward_shares . Their
approach is most similar to our, but we offer a simpler method involving
players choosing to donate their rewards rather than acquiring an interest in
the rewards of the other players. By determining the limiting amount of shared
interest required, our work is equipped with a descriptive element, and should
reward transfer be costly, minimises such cost by identifying the smallest
amount required to be transferred. Gemp et al. gemp22__d3c  develop an
algorithm to reduce the Price of Anarchy through reward shaping (here called
_loss-sharing_). During training, the players learn a loss sharing matrix that
increases the social welfare of the worst case Nash equilibrium solution. This
is an equivalent mechanism to ours, but they focus on a method for use with
learning algorithms in stochastic games, in which they trade off minimising
transfers with minimising the Price of Anarchy.

##  3 Methodology

We review normal-form games and formalise the notion of a social dilemma in
Sections 3.1 and 3.2. In Section 3.3 we introduce our reward transfer concept,
and we present two metrics which describe properties of a social dilemma game
in Sections 3.4 and 3.5. We conclude with a discussion in Section 3.6.

###  3.1 Preliminaries

The normal-form game, also known as the strategic or matrix form, is a
representation of every player’s utility for every state of the world, in the
special case where states of the world depend only on the players’ combined
actions. A (finite, _n_ -person) normal-form game is a tuple $(N,A,\vv{R})$,
where:

  * •

$N$ is a finite set of $n$ players, indexed by $i$.

  * •

$A=A_{1}\times...\times A_{n}$ , where $A_{i}$ is a finite set of actions
available to player $i$. Each tuple $\vv{a}=(a_{1},...,a_{n})\in A$ is called
an action profile.

  * •

$\vv{R}=(R_{1},...,R_{n})$ where $R_{i}:A\rightarrow\mathbb{R}$ is a real-
valued reward (or payoff) function for player $i$.

Normal-form games are naturally represented by an _n_ -dimensional matrix. An
action $a^{*}_{i}$ is a player’s best response to the fixed action profile of
their opponents if it maximises their reward. An action profile is a _Nash
equilibrium_ if, for all agents $i$, $a_{i}$ is a best response to
$\vv{a_{-i}}$. An action profile is _dominant_ if, for all agents $i$, $a_{i}$
is the best response to all possible opponent action tuples.

We introduce the notion of collective good, represented by a _social welfare
metric_ , $SW:\mathbb{R}^{n}\rightarrow\mathbb{R}$, indicating the benefit
overall to a group. An action profile is a _social welfare optimum_ if it
maximises the social welfare metric. In this paper for social welfare, we use
the utilitarian metric, $U$, which measures the unweighted sum of rewards
obtained by all players, as follows.

$U(\vv{r})=\sum_{i=1}^{n}r_{i}$ (1)

Where $\vv{r}=(r_{1},...,r_{n})$, is a tuple of individual rewards.

###  3.2 Social dilemmas

We begin by formalising what it means for a game to be a social dilemma so
that we are then able to demonstrate how our proposed solution directly
addresses their core challenges. We describe a new formalism for what
constitutes a social dilemma and what it means to resolve one. At the end of
this section, we mention other existing formalisations from literature, and in
Section 3.6 we discuss the advantages of our characterisation.

A social dilemma is a game in which all players have the option to take
prosocial actions (to cooperate) at a (potential) cost to themselves. That is
to say that while the benefit to their group is higher when players cooperate,
the benefit to an individual player from cooperating is lower than when it
defects. The players therefore face a choice between acting for the benefit of
the group or in their own interests.

A social dilemma can therefore be defined as a situation in which, for all
agents: (i) the social welfare of the group is strictly greater when an agent
chooses to cooperate than when it chooses to defect, regardless of the actions
of the other agents; and (ii) each agent does better individually when it
defects than when it cooperates. We also include the condition (iii) that all
agents prefer the outcome of mutual cooperation compared to mutual defection.
This reflects the fact that the social welfare increase from cooperation is
distributed widely, rather than being captured by only a subset of agents.

Consider a general-sum normal-form game, where each agent faces a choice to
either cooperate, $C$, or defect, $D$. In what follows, for convenience, we
write $\vv{a_{-i}}$ to represent the tuple of actions of all players other
than player $i$, and we define ⌢ as a coupling operation that inserts $a_{i}$
into $\vv{a_{-i}}$ such that  $\ignorespaces\vv{a}=a_{i}^{\frown}\vv{a_{-i}}$
. For a given social welfare metric, $SW(\vv{r})$, we define a strict social
dilemma as follows. For any action profile $\vv{a}\in A$:

$\displaystyle\forall i\quad
SW(R(C^{\frown}\vv{a_{-i}}))>SW(R(D^{\frown}\vv{a_{-i}}))$
$\displaystyle\forall i\quad
R_{i}(D^{\frown}\vv{a_{-i}})>R_{i}(C^{\frown}\vv{a_{-i}})$
$\displaystyle\forall i\quad R_{i}((C,C,...,C))>R_{i}((D,D,...,D))$

A _strict_ social dilemma is characterised by a unique, pure Nash equilibrium
in which all players defect, and is both Pareto inferior and a social welfare
minimum. This follows from the fact that defect is a dominant strategy for
every agent, the social welfare strictly decreases with each defect action and
every player prefers the mutual cooperation outcome.

A _partial_ social dilemma can be said to occur when each agent may benefit
from defecting, depending on the choices of their opponents. In this respect,
there exists at least one action profile $\vv{a_{-i}}$ that would lead to an
agent preferring to defect. Thus, while there is always a personal cost to
cooperation in a strict social dilemma, this is not always the case in a
partial social dilemma. For a partial social dilemma, the second inequality
above can therefore be softened as follows.

$\forall i\
\;\exists\vv{a_{-i}}:R_{i}(D^{\frown}\vv{a_{-i}})>R_{i}(C^{\frown}\vv{a_{-i}})$

Table 1 shows three matrix games that are commonly considered social dilemmas
in the literature macy02__learning_dynamics_in_social_dilemmas ;
leibo17__multiagent_reinforcement_learning_in_sequential_social_dilemmas .
Under our definition, Prisoner’s Dilemma (Table 1(a)) is an example of a
strict social dilemma, while Chicken (Table 1(b)) and Stag Hunt (Table 1(c))
are examples of partial social dilemmas.

| $C$ | $D$
---|---|---
$C$ | $3,3$ | $0,4$
$D$ | $4,0$ | $1,1$
(a) Prisoner’s Dilemma

| $C$ | $D$
---|---|---
$C$ | $3,3$ | $1,4$
$D$ | $4,1$ | $0,0$
(b) Chicken

| $C$ | $D$
---|---|---
$C$ | $4,4$ | $0,3$
$D$ | $3,0$ | $1,1$
(c) Stag Hunt

Table 1: Social Dilemmas

A social dilemma remains a social dilemma under positively-scaled linear
transformations. Different measures of social welfare admit different games;
for example, Chicken is still a partial social dilemma under the egalitarian
metric, which returns the minimum reward of all players, but Prisoner’s
Dilemma and Stag Hunt are not social dilemmas under this metric because our
formulation of social dilemmas excludes games where cooperation could be
harmful to the collective.

We say that a social dilemma is _resolved_ if an action profile that maximise
the social welfare is dominant. Rational players will always take a dominant
action, so this definition of resolving guarantees that a social welfare
optimum will occur. Previous works have used alternative notions of resolving
a social dilemma, such as the selfishness level of a game
apt14__selfishness_level_of_strategic_games  which defines it to be when a
social optimum is realized in a pure Nash equilibrium. Gemp et al. gemp22__d3c
minimise the Price of Anarchy koutsoupias09__worstcase_equilibria . In what
follows, we use our definition of resolving a social dilemma, but equivalent
results could be obtained using a different notion, such as one of the above
definitions.

While others have defined social dilemmas previously, we believe that our
formalisation, which focuses on costly prosocial choices, represents the
underlying dynamics of these dilemmas. For example, Macy and Flache
macy02__learning_dynamics_in_social_dilemmas  consider them to be normal-form
games with payoffs satisfying certain conditions, but some of their conditions
are justified only if players hold particular beliefs. In turn, Hughes et al.
hughes18__inequity_aversion_improves_cooperation_in_intertemporal_social_dilemmas
draw upon the work of Schelling
schelling73__hockey_helmets_concealed_weapons_and_daylight_saving  and
generalise the Macy and Flache definition to apply to _n_ -player Markov
games. However, both Hughes et
al.hughes18__inequity_aversion_improves_cooperation_in_intertemporal_social_dilemmas
and Schelling
schelling73__hockey_helmets_concealed_weapons_and_daylight_saving  include
within their definition games with social optima which occur when a certain
number of players defect. In other words, cooperation is not guaranteed to be
prosocial. We return to these alternative definitions of a social dilemma, and
what it means to resolve them in Section 3.6, after we have introduced our
mechanism.

###  3.3 Reward transfer

As discussed above, the core difficulty of social dilemmas is that prosocial
actions are personally costly. Agents need to be sufficiently motivated to
care about others for collective action to become more attractive than selfish
behaviour. To address this, an agent needs to provide some kind of incentive
for others to care about its own well-being, and it can do so by sharing the
reward it gains from their combined actions.

Consider the villagers in our tragedy of the commons example in Section 1.
Suppose that the villagers enter into a contract to donate a proportion of the
wood they harvest to be shared equally among the other villagers. Now, each
villager has a reduced incentive to harvest more trees than is sustainable,
for two reasons. First, they now only get to keep a fraction of the proceeds,
as they must share their profits with others. Second, if they refrain from
behaviour that degrades the wood, there will be greater numbers of trees to be
harvested in the future, and the individual in question will be entitled to a
proportion of the increased yields that the other villagers obtain. If this
effective tax level is correctly set, then the villagers will now care
sufficiently about their neighbours to refrain from unsustainable logging.

Thus, in this section, we introduce a mechanism by which agents can _commit_
to transfer proportions of their reward to each other. This mechanism requires
the existence of _transferable utility_ , which is a common currency equally
valued by all players, and the ability for the agents to enter into _binding
agreements_. We consider two cases, first where a group of agents enter a
_contract_ to transfer a fixed proportion of their future rewards to each
other, and second, the general case, where each agent is free to specify
different proportions of their future reward to commit to transfer to each
other agent. In what follows, our examples typically involve games with non-
negative rewards, but under reward transfer negative game rewards, or losses,
are treated the same way.

###  3.4 Reward exchange

Formally, when all players enter into a contract to retain a proportion
$s\in[0,1]$ of their future rewards, and to equally divide the remainder
equally amongst the other agents, we call this concept _reward exchange_. In
this way, each agent receives a proportion $\frac{1-s}{n-1}$ of the future
reward of all other agents. The _post-transfer reward_ to agent $i$,
$r_{i}^{\prime}$, is the retained part of their individual game reward,
$r_{i}$, plus any reward received from others, and is given by:

$\displaystyle r_{i}^{\prime}(\vv{r},s)$ $\displaystyle=$ $\displaystyle
sr_{i}+\frac{1-s}{n-1}\sum_{j\neq i}r_{j}$ (2)

This formulation is similar to the concept of _prosocial_ rewards of
Peysakhovich and Lerer
peysakhovich17__prosocial_learning_agents_solve_generalized_stag_hunts_better_than_selfish_ones
, a form of reward shaping in which an agent modifies only its own reward by
including an extra intrinsic reward term. However, our notion of reward
transfer, involves only a redistribution of the _extrinsic_ game rewards, and
allows an agent to impact the rewards of other agents (in addition to its own
reward). Reward exchange is also similar to the model of altruism proposed by
Chen and Kempe chen08__altruism_selfishness_and_spite_in_traffic_routing .
Their model can be thought of as agents transferring a proportion of their
rewards into a common fund, which is then distributed equally amongst all
agents. In their mechanism, therefore, an agent will receive a proportion
$\frac{1}{n}$ of its own rewards that it transferred to the fund. The
difference in our approaches will be relevant in Section 3.5.

Consider again Prisoner’s Dilemma (Table 1(a)), in which the players agree to
retain $s=\frac{3}{4}$ of their payoffs, as shown in Table 2(a). At this
point, both players are ambivalent between playing cooperate or defect. This
occurs because each player stands to gain only $s$ as much from a possible
defect action, and cooperating increases the reward of their opponent, of
which they are entitled to a proportion $(1-s)$. If the players retain an
amount $s<\frac{3}{4}$, cooperation is dominant for them both, and the dilemma
is resolved. However, for any value of $s>\frac{3}{4}$, the players retain too
much self-interest, and stand to gain from defecting, so the dilemma remains
unresolved. In Chicken and Stag Hunt (Tables 2(b) and 2(c), cooperation is
weakly dominant for both players when $s=\frac{2}{3}$, which resolves the
dilemma.

We call the limiting value of $s$ that resolves the dilemma the _symmetrical
self-interest level_ of a game, denoted  $\ignorespaces s^{*}$ , because each
player retains the same self-interest in the own reward and exchanges an equal
amount with all other players. In Section 3.5 we will generalise the transfers
by relaxing the symmetrical nature. Table 2 shows the post-transfer reward for
the three example social dilemmas at their symmetrical self-interest level.

| $C$ | $D$
---|---|---
$C$ | $3,3$ | $1,3$
$D$ | $3,1$ | $1,1$
(a) Prisoner’s Dilemma, $s=\frac{3}{4}$

| $C$ | $D$
---|---|---
$C$ | $3,3$ | $2,3$
$D$ | $3,2$ | $0,0$
(b) Chicken, $s=\frac{2}{3}$

| $C$ | $D$
---|---|---
$C$ | $4,4$ | $1,2$
$D$ | $2,1$ | $1,1$
(c) Stag Hunt, $s=\frac{2}{3}$

Table 2: symmetrical self-interest level for the social dilemmas

Formally, the symmetrical self-interest level of a game is the maximum
proportion of their own reward $s$ that players can retain while resolving the
social dilemma. Writing the reward function returning the post-transfer reward
to player $i$ as $R^{\prime}_{i}(\vv{r},s)$, we have:

$s^{*}=\max\\{s\mid\forall i\quad
R^{\prime}_{i}(C^{\frown}\vv{a_{-i}},s)>R^{\prime}_{i}(D^{\frown}\vv{a_{-i}},s)\\})$

The symmetrical self-interest level of a game is invariant to linear
transformations of the game rewards and exists for all social dilemmas under
the utilitarian metric (Equation (1)), which follows from the fact that when
every player retains $s=\frac{1}{n}$ of their rewards, Equation (2) reduces
to:

$r_{i}^{\prime}(\vv{r},\frac{1}{n})=\frac{1}{n}\sum_{j=0}^{n}{r_{j}}=\frac{1}{n}U(\vv{r})$
(3)

Consequently, each player wants to maximise the utilitarian metric, and since
cooperation increases the social welfare, there is a unique social welfare
maximum of mutual cooperation. The symmetrical self-interest level therefore
has a lower bound, and $s^{*}\in[\frac{1}{n},1]$. We therefore expect that,
everything else being equal, increasing the number of players of a game will
decrease its symmetrical self-interest level.

The symmetrical self-interest level of a game can be viewed as a measure of
the willingness of the players to cooperate; it quantifies the disparity
between the individual and group incentives. A high symmetrical self-interest
level indicates that the players need to care a little about each other to
achieve a socially optimal outcome, whereas a low symmetrical self-interest
level suggests that the players have strong incentives to shirk prosocial
behaviour. Importantly, if we can determine the symmetrical self-interest
level, we may also be able to find a way to resolve social dilemmas, through
agents exchanging a proportion $\frac{1-s}{n-1}$ of their future rewards with
each other.

We note that the symmetrical self-interest level of finitely iterated normal-
form games is the same as for a single round game. This due to the finite
nature of the game permitting a backwards induction process where a player
realises that in the last round they will play as they would in a single round
game. Consequently, in the penultimate round, the strategies of the players
will not impact their play in the following round, so there is no reason to
deviate from the best single round strategy here either. This logical
reasoning continues until the current round, and will only change if
sufficient reward is to be exchanged such that their play in the final round
is altered.

###  3.5 Generalised reward transfer

So far, we have assumed that each player divides their relinquished reward
equally amongst their opponents. This, in effect, measures how much of the
combined group reward that the players need in order to act for the
collective. A benefit of this approach is that it is simplistic, requiring
only a single parameter. However, it may be possible to be more efficient, and
find ways of reducing the amount of future reward needing to be promised to
others by exploiting the game structure. For example, in a situation that is
spacially located, agents may only be impacted by their local neighbourhood,
needing only need to share rewards with those closest to them to incentivise
cooperation. In this case, it may not be efficient to be transferring reward
to agents that are further away.

We now look at the general case of reward transfer and define the _reward
transfer matrix_ , $\mathbf{T}$, which specifies the proportion of their game
reward that the row player transfers to the column player. The tuple of post-
transfer rewards, $\vv{r^{\prime}}$, is given by the game rewards, $\vv{r}$,
multiplied by the reward transfer matrix, $\vv{r^{\prime}}=\mathbf{T}\vv{r}$.

$\mathbf{T}=\begin{vmatrix}t_{1,1}&t_{1,2}&\cdots&t_{1,n}\\\
t_{2,1}&t_{2,2}&\cdots&t_{2,n}\\\ \vdots&\vdots&\ddots&\vdots\\\
t_{n,1}&t_{n,2}&\cdots&t_{n,n}\end{vmatrix}$ (4)

Where $\forall i\;\forall j\;t_{i,j}\in[0,1]$, which means that a player can
transfer at most all their reward to a player, and cannot transfer a negative
proportion. Furthermore, we require that $\forall i\;\sum_{j}{t_{i,j}}=1$,
which means that each row sums to one and the total amount of reward is
conserved during the transfer. For convenience, we alternatively denote the
diagonal elements $t_{i,i}$ by $\Sigma_{i}$ to emphasise that they are the
remaining proportion of game reward that player $i$ gets to keep for
themselves, after transfers to others, because in general $\forall
i\;\Sigma_{i}=1-\sum_{j\neq i}t_{i,j}$. We refer to these diagonal values as
the self-interest of the players. The columns need not sum to one, however, so
any reward conserving distribution is permissible. Reward exchange is
therefore a case of generalised reward transfer using a symmetrical reward
transfer matrix of the following form.

$\mathbf{T}=\begin{vmatrix}s&\frac{1-s}{n-1}&\cdots&\frac{1-s}{n-1}\\\
\frac{1-s}{n-1}&s&\cdots&\frac{1-s}{n-1}\\\ \vdots&\vdots&\ddots&\vdots\\\
\frac{1-s}{n-1}&\frac{1-s}{n-1}&\cdots&s\end{vmatrix}$

As for reward exchange, we are interested in the smallest amount of reward
that each player must transfer to resolve a dilemma. We wish to find the
limiting solution that minimises the transfers the worst-case player must
commit to. Out of all possible reward transfer matrices that make cooperation
dominant for all players, we find the transfer matrix with the largest minimum
of diagonal elements. This is the matrix with the greatest amount of self-
interest that the agent(s) with the least self-interest can retain, and we
call the value of its minimum diagonal element the _general self-interest
level_ of the game, denoted by $g^{*}$. In other words, while still resolving
the dilemma, all players can retain at least $g^{*}$ of their own reward.
Formally, writing $\dot{\Sigma}=min_{i}(\Sigma_{i})$ and the reward function
returning the post-transfer reward to player $i$ as
$R^{\prime}_{i}(\vv{r},\mathbf{T})$, we have.

$g^{*}=\max\\{\dot{\Sigma}\mid\forall i\quad
R^{\prime}_{i}(C^{\frown}\vv{a_{-i}},\mathbf{T})>R^{\prime}_{i}(D^{\frown}\vv{a_{-i}},\mathbf{T})\\}$

We refer to a reward transfer matrix that achieves the general self-interest
level as a _minimal reward transfer matrix_ , and we denote it as
$\mathbf{T}^{*}$. As demonstrated in Equation (3), the symmetrical self-
interest level is guaranteed to exist for a social dilemma. The general self-
interest level is therefore also guaranteed to exist, because we can always
use the reward transfer matrix equivalent to the symmetrical self-interest
level, but we may be able to find larger values for the general self-interest
level. The general self-interest level of a game is likewise invariant under
linear transformations of the game rewards. We now illustrate this metric with
two possible three-player variants of Prisoner’s Dilemma.

Previously, we looked at a two-player Prisoner’s dilemma (Table 1(a)) and
found the symmetrical self-interest level to be $s^{*}=\frac{3}{4}$. The
payoffs for this game can be constructed using the following rules: a player
gains a reward of 1 when they defect, and gives a reward of 3 to their
opponent when they cooperate. Using similar rules, we create two three-player
variants. In both of the variants, a player who defects gains a reward of 1,
as before. In the first version (Table 3), cooperate now divides the reward of
3 equally among both opponents, giving each $\frac{3}{2}$, which we call
Symmetrical-3PD. In the second version (Table 4), cooperate gives a reward of
3 to the player with index  $\ignorespaces i+1\mod n$ , which we call
Cyclical-3PD. In this latter case, cooperating only increases the reward of
_one_ other agent.

Table 3: Symmetrical-3PD

| $C$ | $D$
---|---|---
$C$ | $3,3,3$ | $\frac{3}{2},4,\frac{3}{2}$
$D$ | $4,\frac{3}{2},\frac{3}{2}$ | $\frac{5}{2},\frac{5}{2},0$
(a) Player 3 cooperates

| $C$ | $D$
---|---|---
$C$ | $\frac{3}{2},\frac{3}{2},4$ | $0,\frac{5}{2},\frac{5}{2}$
$D$ | $\frac{5}{2},0,\frac{5}{2}$ | $1,1,1$
(b) Player 3 defects

Table 4: Cyclical-3PD

| $C$ | $D$
---|---|---
$C$ | $3,3,3$ | $3,4,0$
$D$ | $4,0,3$ | $4,1,0$
(a) Player 3 cooperates

| $C$ | $D$
---|---|---
$C$ | $0,3,4$ | $0,4,1$
$D$ | $1,0,4$ | $1,1,1$
(b) Player 3 defects

While the symmetrical self-interest level for both these games is
$s^{*}=\frac{3}{5}$, the general self-interest level of Symmetrical-3PD is
$g^{*}=\frac{3}{5}$ and of Cyclical-3PD is $g^{*}=\frac{3}{4}$. The minimal
reward transfer matrices are, respectively:

$\mathbf{T}^{*}=\begin{vmatrix}\nicefrac{{3}}{{5}}&\nicefrac{{1}}{{5}}&\nicefrac{{1}}{{5}}\\\
\nicefrac{{1}}{{5}}&\nicefrac{{3}}{{5}}&\nicefrac{{1}}{{5}}\\\
\nicefrac{{1}}{{5}}&\nicefrac{{1}}{{5}}&\nicefrac{{3}}{{5}}\end{vmatrix}\text{
and
}\mathbf{T}^{*}=\begin{vmatrix}\nicefrac{{3}}{{4}}&0&\nicefrac{{1}}{{4}}\\\
\nicefrac{{1}}{{4}}&\nicefrac{{3}}{{4}}&0\\\
0&\nicefrac{{1}}{{4}}&\nicefrac{{3}}{{4}}\end{vmatrix}$

In Cyclical-3PD, the minimal reward transfer matrix permits the players to
retain a larger proportion of their own rewards compared to the symmetrical
self-interest level. This is because the game rewards to each player only
depend on their own action and the action of one other player. Consequently,
each player only needs to offer a proportion of their rewards to the player
who impacts their game reward, and they need not offer any rewards to the
other player. The situation is different for Symmetrical-3PD, where each
player has to incentivise both opponents to cooperate, so the general self-
interest level is greater. Note that for this game, the minimal reward
transfer matrix is not unique, and we are free to choose the off-diagonal
elements to be any value within bounds so long as the columns and rows sum to
one. The reason for the columns needing to sum to one, in addition to the
rows, is that in this game, post-reward transfer a player gains
$\nicefrac{{3}}{{5}}$ when they defect, so they need to benefit at least as
much when they cooperate, which means receiving at least $\nicefrac{{2}}{{5}}$
of their opponents’ rewards. This can only happen for every player when all
columns sum to one. We return to these games and find the symmetrical and
general self-interest levels as a function of the number of players in Section
4.

Given a social dilemma game, we can find the minimal reward transfer matrix by
ensuring that there is no action profile with an incentive for a player to
defect, which makes mutual cooperation dominant. We do this by finding
inequality constraints for the parameters of $\mathbf{T}$. We achieve this by
requiring that for all possible action profiles, if a player has an incentive
to defect in the original game, then the players who would be (negatively)
impacted by them defecting are transferring reward sufficient to remove this
incentive. In each of the $2^{n}$ possible action profiles, on average,
$\frac{n}{2}$ players are cooperating. We therefore form $n\cdot 2^{n-1}$
inequality constraints, in addition to the bound constraints for each
parameter. These constraints can be passed to an optimisation algorithm to
find the $n^{2}$ parameters of $\mathbf{T}$ which maximises $\dot{\Sigma}$.
Unfortunately, due to taking the minimum of the diagonals, the problem is non-
linear, so a linear program is not suitable. The complexity of this is small,
however, ($\approx O(n)$) compared to the size of the problem, which requires
a matrix with $2^{n}$, each with a tuple of $n$ elements. Note that for
cyclically symmetrical games, such as Cyclical-3PD, each row in the reward
transfer matrix is a permutation of the first row. In this simpler case, there
are only $n-1$ parameters to find. Algorithm 1 describes a program to find the
minimal reward transfer matrix for a social dilemma.

Algorithm 1 An algorithm to compute the minimal reward transfer matrix

optimisation algorithm, $Opt$

normal-form game social dilemma, $N$, with $n$ players

set of all possible joint actions, $A$

$reward$ $transfer$ $matrix$, $T=matrix(n$ by $n)$

$objective$ $function,Obj(T)=maximise(minimum_{i}(t_{i,i}))$

$bounds,B=list(t_{i,j}\in[0,1]$ for $i$ in $1...n$ for $j$ in $1...n)$

$constraints=list()$

for each $joint$ $action,\vv{a}\in A$ do

for $i$ in $1...n$ do

if $\vv{a}[i]=C$ then

$\ignorespaces\triangleright$ compute the change in reward for all players if
player $i$ plays D

$diff=N[D^{\frown}\vv{a_{-i}}]-N[C^{\frown}\vv{a_{-i}}]$

if $diff[i]>0$ then $\ignorespaces\triangleright$ if player $i$ would benefit
from this

$\ignorespaces\triangleright$ add a constraint that the other players must
transfer

$\ignorespaces\triangleright$ sufficient reward to eliminate the gain

$constraints\leftarrow diff\cdot T[:,i]<0$

end if

end if

end for

end for

$T^{*}=Opt(T,Obj,B,constraints)$

$g^{*}=min(diag(T^{*}))$

###  3.6 Discussion

We now return to our discussion from Section 3.2 regarding the formalisation
of a social dilemma, and the definition of what it means to resolve one. The
formalisation proposed by Hughes et al.
hughes18__inequity_aversion_improves_cooperation_in_intertemporal_social_dilemmas
includes games where cooperation is not guaranteed to increase the social
welfare. We argue that while such games can manifest elements of a social
dilemma, these complex games are better viewed as a combination of a pure
social dilemma game with another type of game in which players benefit from
coordinating their actions, such as adding Volunteer’s Dilemma (Table 5(a)) or
subtracting Coordination game (Table 5(b)).

Table 5: Other games

|  At least 2 players cooperate | Otherwise
---|---|---
$C$ | $0$ | $-1$
$D$ | $2$ | $-1$
(a) Volunteer’s Dilemma

|  All players take the same action | Otherwise
---|---|---
$C$ | $1$ | $0$
$D$ | $1$ | $0$
(b) Coordination game

In order to illustrate the differences, we introduce a game, which we call
_Too Many Cooks in Prison_ , as shown in Table 6. One interpretation of this
game could be individuals in society deciding whether to comply with tax laws
(cooperate) or practice tax evasion. The government is able to fund public
goods, which are more efficient at delivering utility to society than
individual spending. However, while there are certain high value projects that
the government will preferentially deliver if funded, but there are decreasing
returns on these projects, so that if the government receives too much in
revenue, it will waste the money on white elephant projects.

Table 6: Too Many Cooks in Prison

| $C$ | $D$
---|---|---
$C$ | $2,2,2$ | $\frac{3}{2},4,\frac{3}{2}$
$D$ | $4,\frac{3}{2},\frac{3}{2}$ | $\frac{5}{2},\frac{5}{2},0$
(a) Player 3 cooperates

| $C$ | $D$
---|---|---
$C$ | $\frac{3}{2},\frac{3}{2},4$ | $0,\frac{5}{2},\frac{5}{2}$
$D$ | $\frac{5}{2},0,\frac{5}{2}$ | $0,0,0$
(b) Player 3 defects

This game features the payoffs of Symmetrical-3PD (Table 3) minus those of a
coordination game (Table 5(b)). Because the social welfare is maximised when
only two out of three players cooperate, this is not a pure social dilemma by
our definition, but it is under that of Hughes et al.
hughes18__inequity_aversion_improves_cooperation_in_intertemporal_social_dilemmas
. Nevertheless, there are strong individual incentives to shirk prosocial
actions, and defect is a weakly dominant strategy in this game, so a player
will only cooperate if they are incentivised to do so. While it is necessary
but not sufficient to incentivise the players to desire a social welfare
optimum, because they also need to coordinate on a particular outcome. Too
Many Cooks in Prison is a symmetrical game, so it is not possible to use
reward exchange (Section 3.4) to make a social welfare optimum a dominant
outcome, because reward exchange does not alter this symmetry, which is also
the case for the models of altruism in literature
elias10__sociallyaware_network_design_games ;
chen08__altruism_selfishness_and_spite_in_traffic_routing ;
chen11__the_robust_price_of_anarchy_of_altruistic_games ;
caragiannis10__the_impact_of_altruism_on_the_efficiency_of_atomic_congestion_games
. Table 7 shows the game using reward exchange (Equation (2)) $s=\frac{3}{5}$,
which is the limiting value that makes the social optima of $(D,C,C)$,
$(C,D,C)$ and $(C,C,D)$ also Nash equilibria.

Table 7: Too Many Cooks in Prison with reward exchange

| $C$ | $D$
---|---|---
$C$ | $2,2,2$ | $2,3,2$
$D$ | $3,2,2$ | $2,2,1$
(a) Player 3 cooperates

| $C$ | $D$
---|---|---
$C$ | $2,2,3$ | $1,2,2$
$D$ | $2,1,2$ | $0,0,0$
(b) Player 3 defects

Under the notion of resolving a social dilemma provided by Apt and Schafer
apt14__selfishness_level_of_strategic_games , this would qualify as there is a
social welfare maximising pure Nash equilibrium. This is insufficient to
guarantee that the played action profile will maximise social welfare,
however, because of two reasons. First, if there are multiple pure social
welfare maximising Nash equilibria, as is the case here, the players will face
an equilibrium selection problem. If they are not able to coordinate, they do
not know which of the social optima they should go for. Second, even if there
were only one pure Nash equilibrium, if it is not dominant, the players may
still fail to take their appropriate action if they had reason to believe that
other player(s) may deviate from their action. This is the difficulty in Stag
Hunt (Table 1(c)). Generalised reward transfer (Section 3.5) can be used to
make a social welfare optimum dominant, if the players choose which outcome to
coordinate on in advance. Table 8 shows Too Many Cooks in Prison using the
following (minimal) reward transfer matrix, which makes the action profile
$\vv{a}=(D,C,C)$ dominant.

$\mathbf{T}^{*}=\begin{vmatrix}\frac{3}{11}&\frac{4}{11}&\frac{4}{11}\\\
0&\frac{3}{11}&\frac{8}{11}\\\ 0&\frac{8}{11}&\frac{3}{11}\end{vmatrix}$

Table 8: Resolved Too Many Cooks in Prison

| $C$ | $D$
---|---|---
$C$ | $\frac{6}{11},\frac{30}{11},\frac{30}{11}$ | $\frac{9}{22},\frac{30}{11},\frac{85}{22}$
$D$ | $\frac{12}{11},\frac{65}{22},\frac{65}{22}$ | $\frac{15}{22},\frac{35}{22},\frac{30}{11}$
(a) Player 3 cooperates

| $C$ | $D$
---|---|---
$C$ | $\frac{9}{22},\frac{85}{22},\frac{30}{11}$ | $0,\frac{5}{2},\frac{5}{2}$
$D$ | $\frac{15}{22},\frac{30}{11},\frac{35}{22}$ | $0,0,0$
(b) Player 3 defects

Users should therefore specify which solution concept to resolve a social
dilemma is appropriate for the situation. For example, if the players have
access to a coordinating device, and can therefore play a correlated
equilibrium leyton-brown08__essentials_of_game_theory , the symmetrical self-
interest level of the game would be $s=\frac{3}{5}$, and reward exchange at
such a level would be an appropriate solution. In the general case, without
access to a correlating signal, only general reward transfer is appropriate,
and the above minimal reward transfer matrix gives $g^{*}=\frac{3}{11}$.

Social dilemmas are intrinsically connected to notions of fairness. The
general self-interest level is entirely focused on guaranteeing a social
welfare optima, regardless of the fairness of such an outcome. For
illustration, consider the game of Prisoner’s Dilemma where we have multiplied
the rewards to player 1 in all outcomes by a factor of 3 and subtracted an
infinitesimal amount $\epsilon$ from their unilateral defection outcome, so
that cooperate increases the social welfare and the game conforms to our
definition of a social dilemma. We call this game Scaled-PD, and it is
displayed in Table LABEL:table:scaled_pd_a.

Table 9: Scaled-PD

| $C$ | $D$
---|---|---
$C$ | $6,6$ | $2,2$
$D$ | $\frac{6-\epsilon}{2},\frac{6-\epsilon}{2}$ | $2,2$
(b) With
$\mathbf{T}^{*}=\begin{vmatrix}\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}\\\
\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}\end{vmatrix}$

In order to resolve Scaled-PD, a reward transfer matrix
$\mathbf{T}=\begin{vmatrix}\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{18}}\\\
\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}\end{vmatrix}$ is sufficient, which
leaves $\nicefrac{{8}}{{18}}$ reward from the row player unaccounted for. The
row player is not able to allocate this to themselves, however, or they would
have an incentive to defect. They therefore must grant this _excess reward_ to
an opponent, which they are free to choose in general, but in this instance
they only have one opponent, so they must transfer their excess reward to the
column player. In what follows, we refer to the minimal reward transfer matrix
as the matrix that maximises the minimum of the diagonals while resolving a
dilemma, as before, but we will not require that the rows sum to one. It is
informative to appreciate that excess reward exists, and that there are
therefore many possible valid minimal reward transfer matrices with different
transfer distributions. In order to be a valid transfer matrix, the players
will need to determine how to distribute their excess reward. This will become
relevant in Section 4.2 when we analyse additional games with excess reward.

Retuning to Scaled-PD, because it is a two-player game, there is only one
possible minimal reward transfer matrix, which leaves both players receiving
the same post-transfer reward, as in Table 9(b). In some sense this is a fair
result, in that both players have equal outcomes, but in another sense, this
is not fair to the row player, whose rewards are a factor of three greater
than the column player in the base game, and they could therefore argue that
they should receive a larger share of the rewards in the transformed game. The
row player might reasonably propose the reward transfer matrix given in Table
LABEL:table:scaled_pd_c, where they maintain a three to one ratio of rewards
to the column player in the resulting dominant action profile $(D,C)$, yet
still greatly benefit the column player who will receive close to their
maximum reward in the unmodified game, at the cost of only an infinitesimal
loss of social welfare.

In this work, we do not concern ourselves with the fairness of the resulting
reward distribution, and we leave this as further work, however, we have a
couple of suggestions to tackle this issue. First, users could use the general
self-interest level to describe the ease of achieving cooperation within a
game, and utilise additional metrics to quantify the fairness of the post-
reward transfer outcomes. Second, to alleviate this issue, the players could
create a pseudo player, called _the lawyer_ , who receives the excess rewards
and then redistributes this reward after the game among the players who
cooperated in a pre-arranged manner. This would enable a player to receive
some of their excess rewards without incentivising them to defect, because
this would make them ineligible for any transfers from the lawyer. For
example, the players could agree on a fairness metric that they wish to
increase, and task the lawyer with distributing the excess rewards in such a
way that the chosen fairness metric is maximised. In the case of Scaled-PD,
the post-transfer reward tuple using the minimal transfer matrix in the mutual
cooperation outcome is $(6,2)$, leaving 4 excess reward. Suppose the players
agreed before the game that the pseudo player should redistribute the reward
to minimise the function $\|r_{r}-2r_{c}\|$, then the lawyer would transfer 2
reward to both players, making the final rewards received $(8,4)$. A natural
choice for a fairness metric may be the Shapley value
shapley88__a_value_for_n_person_games , which is intuitively the average
marginal contribution an individual makes to their coalition. This concept has
previously been applied to cooperative games
bachrach10__the_good_the_bad_and_the_cautious .

It is not possible for reward transfer to be rational for all possible beliefs
in partial social dilemmas111We are talking about the subjective probability a
player may have over the strategy that their opponent(s) may play, not
Bayesian games
harsanyi04__games_with_incomplete_information_played_by_bayesian_players_iiii
which feature incomplete information.. As an example, consider the game of
Chicken in Table 1(b). If a player holds the belief that their opponent will
cooperate, they will anticipate that they can play defect and receive a reward
of 4. In this case, they will not be prepared to offer any reward to their
opponent, because they do not need to incentivise cooperation. Therefore, it
would not be rational for them to commit to the minimal reward transfer matrix
to resolve Chicken, as they would then only receive a reward of 3.

We conclude by contrasting our work against what we believe are the closest
alternatives in literature. As a solution to achieving cooperation in social
dilemmas, our reward transfer mechanism works the same way as that of Gemp et
al. gemp22__d3c , in that each player have a convex combination of the rewards
of other players. The algorithm they propose, _D3C_ aims to minimise the Price
of Anarchy using a novel method for approximating local Nash equilibria, and
uses gradient descent to find the strategies and loss sharing matrix. However,
by trading off the group loss against minimising the reward transfer, D3C may
not achieve a social welfare optimum, as suggested by their experiments in
stochastic games which, while improving on the behaviour of independent,
selfish agents, fail to achieve the same social welfare as optimal cooperative
strategies. Furthermore, minimising the Price of Anarchy may leave the players
with an equilibrium selection problem. For example, the Price of Anarchy of
the Coordination game (Table 5(b)) is one, yet both defect and cooperate are
rational actions for the players. Even if all Nash equilibria maximise the
social welfare, unless there is a unique, pure equilibrium, the players may
fail to coordinate, similar to the discussion above of Too Many Cooks in
Prison (Table 6) with reward exchange. The approach taken by Schmid et al.
schmid22__learning_to_participate_through_trading_of_reward_shares  could also
be adapted to achieve the same mixing of rewards as reward transfer. However,
our approach involves players choosing to donate their rewards to their
opponents, in order to incentivise them to cooperate, instead of actively
acquiring a stake in the rewards of the other players via trading. Perhaps
more importantly, compared to these two papers, we focus on determining the
greatest amount of self-interest that the players are able to maintain while
resolving the social dilemma. This provides our work with a descriptive
element; and if reward transfer is expensive, it minimises costs by
identifying the smallest amount to be transferred.

From a descriptive perspective, the work of Apt and Schafer
apt14__selfishness_level_of_strategic_games  is closest, because the
selfishness level is also a property of a game that describes the alignment
between individual and group rewards. However, by offering all players the
same additional reward in each outcome, they are not able to take advantage of
the particular incentive structures of a game, and may therefore miss more
efficient solutions, as we demonstrated in Section 3.5 with Cyclical-3PD.
Additionally, as a prescriptive method, it does not explain where the
additional reward that incentivises collective originates from.

##  4 Experiments

In Section 4.1 we introduce four ways to generalise the two-player social
dilemma games of Prisoner’s Dilemma, Chicken and Stag Hunt (Table 1), to _n_
-player variants, and in Section 4.2 we compare their symmetrical self-
interest level with their general self-interest level as a function of the
number of players in. We also introduce an arbitrary social dilemma, and solve
it using Algorithm 1. We conclude with a brief discussion in Section 4.3.

###  4.1 Game setup

We first generalise symmetrical and cyclical variants (as foreshadowed in
Section 3.5) of two-player social dilemma games, to be played by _n_ -players.
We refer to Prisoner’s Dilemma, Chicken and Stag Hunt (Table 1) as _base_
games, and we use the suffices _-nPD, -nCH_ and _-nSH_ , respectively, to
denote which base game a variant is using. We then introduce two new social
dilemma matrix game variants, one which is symmetrical under permutation and
one which has a special player which makes the game fully asymmetrical.

The variants all payoffs parameterised by two variables, $c$ and $d$. For
every base game, when a player cooperates, they contribute an amount $c$ to
their opponent. They additionally may gain a reward of $d$ under certain
conditions, as summarised in Table 10, which depends on the joint-action of
them and their opponent for the three base games.

Table 10: Cyclical _n_ -player game variants Game | Reward | Trigger condition
---|---|---
Prisoner’s | c | Opponent cooperated
Dilemma | d | Player defected
Chicken | c | Opponent cooperated
| d | The player and their opponent took opposing actions
Stag Hunt | c | Opponent cooperated
| d | The player and their opponent took the same action

Using values of $c=3$ and $d=1$, we obtain the base game payoffs as in Table
1. In order to represent social dilemmas, we require $c>d$ when Prisoner’s
Dilemma is the base game, otherwise we require $c>2d$.

Symmetrical The symmetrical variant represents each player simultaneously
playing the two-player base game with each of their opponents. Their chosen
action used for all pair games, and their payoff from each game is multiplied
by a fraction $\frac{1}{n-1}$. When we aggregate their returns, the salient
point is the proportion of their opponents who cooperated, which we write as
$n_{c}$. Table 11 summarises their rewards given this variable.

Table 11: Symmetrical _n_ -player game variants Game | Action | Player reward
---|---|---
Prisoner’s | C | $cn_{c}$
Dilemma | D | $d+cn_{c}$
Chicken | C | $cn_{c}+d(1-n_{c})$
| D | $(c+d)n_{c}$
Stag Hunt | C | $(c+d)n_{c}$
| D | $cn_{c}+d(1-n_{c})$

Cyclical To make the cyclical _n_ -player variants of the two-player, each
player $i$ receives a payoff from Table 10 with their opponent being player at
index $i+1\mod n$. For example, in Cyclical-nCH, if player 1 defects and
player 2 cooperates, player 1 will receive a reward of $c+d$. The reward to
player 2 will depend upon the action of player 3 if there are $n>2$ players,
or player 1 otherwise.

Circular The next game we introduce is called _Circular_. This game is played
by $n\geq 3$, arranged in a circular graph, so that player 1 is connected to
player $n$ and player 2, player 2 is connected to players 1 and 3, and so on.
Each player chooses their action, and then plays $n-1$ individuals games with
every opponents, as per the Symmetrical variant. In Circular, however, rewards
are scaled by a factor $\frac{1}{2}^{distance}$, where the distance is the
minimum number of edges required to connected them. Therefore, player 1 has a
weighting of $\frac{1}{2}$ when playing with players $n$ and 2, a weighting of
$\frac{1}{4}$ when playing with players $n-1$ and 3, and so on.

Tycoon Our final game variant is called _Tycoon_ , and it is asymmetric
because it privileges one player over the others. In this variant, player 1 is
the tycoon and interacts with each of the other $n-1$ players. Players $2...n$
gain the reward of the base game, treating player 1 as their opponent. Player
1 plays the base game simultaneously with each opponent, using the same action
in each game, and receives the sum of their rewards in all base games.

Arbitrary social dilemma The above games are all relatively simple to solve
algebraically, because the inequality constraints necessary to prevent players
from having an incentive to switch to defect are identical for a given player
in all action profiles where they cooperate. This is because the payoffs have
a set structure where the benefits and losses from defecting are consistent.
In order to demonstrate Algorithm 1, we constructed the following three-player
social dilemma game shown in Table 12. Here, there is no systematic change in
payoffs, so it is tedious to solve by hand.

Table 12: Arbitrary social dilemma

| $C$ | $D$
---|---|---
$C$ | $9,6,7$ | $2,9,7$
$D$ | $8,4,8$ | $3,2,1$
(a) Player 3 cooperates

| $C$ | $D$
---|---|---
$C$ | $1,6,12$ | $0,5,2$
$D$ | $8,2,8$ | $1,2,0$
(b) Player 3 defects

###  4.2 Results

We now present the results for the games described above. These results have
been determined algebraically by exploiting the fixed structure of the
payoffs, and verified by our implementation of Algorithm 1. Table 13 shows the
symmetrical self-interest level and general self-interest level as functions
of the game parameters and the number of players, except for the circular
variant, where we show the limit that the general self-interest level
decreases to for large $n$.

Table 13: Self-interest levels Game | Symmetrical, $s^{*}$ | General, $g^{*}$
---|---|---
Symmetrical-nPD | $\frac{c}{c+d(n-1)}$ | $\frac{c}{c+d(n-1)}$
Symmetrical-nCH | $\frac{c-d}{c+d(n-2)}$ | $\frac{c-d}{c+d(n-2)}$
Symmetrical-nSH | $\frac{c-d}{c+d(n-2)}$ | $\frac{c-d}{c+d(n-2)}$
Cyclical-nPD | $\frac{c}{c+d(n-1)}$ | $\frac{c}{c+d}$
Cyclical-nCH | $\frac{c-d}{c+d(n-2)}$ | $\frac{c-d}{c}$
Cyclical-nSH | $\frac{c-d}{c+d(n-2)}$ | $\frac{c-d}{c}$
Tycoon-nPD | $\frac{c}{c+d(n-1)}$ | $\frac{c}{c+d(n-1)}$
Tycoon-nCH | $\frac{c-d}{c+d(n-2)}$ | $\frac{c-d)}{c+d(n-2)}$
Tycoon-nSH | $\frac{c-d}{c+d(n-2)}$ | $\frac{c-d}{c+d(n-2)}$
Circular-nPD | $\frac{c}{c+d(n-1)}$ | $\lim_{n\to\infty}\frac{c}{c+4d}$
Circular-nCH | $\frac{c-d}{c+d(n-2)}$ | $\lim_{n\to\infty}\frac{c-d}{c+3d}$
Circular-nSH | $\frac{c-d}{c+d(n-2)}$ | $\lim_{n\to\infty}\frac{c-d}{c+3d}$

For all variants, the symmetrical self-interest level is the same given a base
game. This is because the ratio of potential benefit from defecting compared
to cooperating is constant, and the impact on the social welfare is the same.
A symmetrical reward transfer matrix is unable to exploit the fact that, for
some of the games, only a subset of opponents is impacted.

Results for Symmetrical In this setting, the general self-interest level is
equal to the symmetrical self-interest level, and every diagonal element is
equal to the value of $g^{*}$ in Table 13. The off-diagonals in the reward
transfer matrix can be of any value, within bounds, so long as the columns sum
to one. In this way, each player cares about themselves equal to the general
self-interest level, and one minus this value about their opponents, but it
does not matter which combination of specific opponents.

Results for Cyclical The cyclical variant gives rise to a minimal reward
transfer matrix with only one off-diagonal element being non-zero; that of the
opponent whose cooperate action benefits the player themselves. The minimal
reward transfer matrices for Cyclical-nPD is the first matrix below, and the
second matrix applies to the other base games. We use the subscript $P$ to
refer to Prisoner’s Dilemma and $C,S$ to refer to Chicken and Stag Hunt.

$\displaystyle\mathbf{T}^{*}_{P}$
$\displaystyle=\frac{1}{c+d}\begin{vmatrix}c&d&0&\cdots&0&0&0\\\
0&c&d&\cdots&0&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
0&0&0&\cdots&0&c&d\\\ d&0&0&\cdots&0&0&c\\\ \end{vmatrix}$
$\displaystyle\mathbf{T}^{*}_{C,S}$
$\displaystyle=\frac{1}{c}\begin{vmatrix}c-d&d&0&\cdots&0&0&0\\\
0&c-d&d&\cdots&0&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
0&0&0&\cdots&0&c-d&d\\\ d&0&0&\cdots&0&0&c-d\\\ \end{vmatrix}$

Because each player only needs to transfer reward to one player, the general
self-interest level remains constant as the number of players increases. This
differs greatly compared to the symmetrical self-interest level, which tends
to zero as $n$ approaches infinity.

Results for Circular The circular variants have a general self-interest level
that decreases to the value given in Table 13. At this point, the minimal
transfer matrix for Circular-nPD (first) and the other base game variants
(second) have the following forms.

$\displaystyle\mathbf{T}^{*}_{P}$
$\displaystyle=\frac{1}{c+4d}\begin{vmatrix}c&2d&0&\cdots&\cdots&\cdots&0&2d\\\
2d&c&2d&0&\cdots&\cdots&0&0\\\ 0&2d&c&2d&0&\cdots&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
0&0&\cdots&0&2d&c&2d&0\\\ 0&0&\cdots&\cdots&0&2d&c&2d\\\
2d&0&\cdots&\cdots&\cdots&0&2d&c\\\ \end{vmatrix}$
$\displaystyle\mathbf{T}^{*}_{C,S}$
$\displaystyle=\frac{1}{c+3d}\begin{vmatrix}c-d&2d&0&\cdots&\cdots&\cdots&0&2d\\\
2d&c-d&2d&0&\cdots&\cdots&0&0\\\ 0&2d&c-d&2d&0&\cdots&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
0&0&\cdots&0&2d&c-d&2d&0\\\ 0&0&\cdots&\cdots&0&2d&c-d&2d\\\
2d&0&\cdots&\cdots&\cdots&0&2d&c-d\\\ \end{vmatrix}$

Despite every player being impacted by the actions of all players, they only
need to transfer reward to those whom maximally impact them. All other players
are induced to cooperate by their respective neighbours. When each player
incentivises their nearest players to cooperate, total mutual cooperation is
dominant, and this is the most efficient way to achieve it. This result can be
found analytically using the observation that the game is symmetrical under
permutation.

Results for Tycoon The tycoon variants give rise to a minimal reward transfer
matrix of the following form.

$\displaystyle\mathbf{T}^{*}_{P}$
$\displaystyle=\frac{1}{c+d(n-1)}\begin{vmatrix}c&d&d&\cdots&d&d\\\
d&c&0&\cdots&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
d&0&0&\cdots&c&0\\\ d&0&0&\cdots&0&c\\\ \end{vmatrix}$
$\displaystyle\mathbf{T}^{*}_{C,S}$
$\displaystyle=\frac{1}{c+d(n-2)}\begin{vmatrix}c-d&d&d&\cdots&d&d\\\
d&c-d&0&\cdots&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
d&0&0&\cdots&c-d&0\\\ d&0&0&\cdots&0&c-d\\\ \end{vmatrix}$

Note that only the first row, representing the tycoon, sums to 1. This is
because the tycoon is the limiting factor, who must incentivise all $n-1$
other players to cooperate. For Tycoon-nPD, in order that cooperation is
dominant for the non-tycoon players, their self-interest cannot risk above
$\frac{c}{d}$ times the reward transfer proportion that the tycoon offers
them. Collectively, the other players incentivise the tycoon to cooperate,
which they achieve by each offering the tycoon $\frac{d}{c+d(n-1)}$. Each non-
tycoon player is left with $\frac{d(n-2)}{c+d(n-1)}$ excess reward, which they
can freely distribute to any player other than themselves. In fact, there is
no requirement that each player transfer exactly $\frac{d}{c+d(n-1)}$ to the
tycoon, the salient point is that the tycoon receives at least
$\frac{d(n-1)}{c+d(n-1)}$ in total, it does not matter what proportion they
receive from a particular player. We give two example matrices for Tycoon-nPD,
the first maximising the reward to the tycoon, the second distributes all the
surplus reward equally to the non-tycoon players.

$\displaystyle\mathbf{T}_{P}$
$\displaystyle=\frac{1}{c+d(n-1)}\begin{vmatrix}c&d&d&\cdots&d&d\\\
d(n-1)&c&0&\cdots&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
d(n-1)&0&0&\cdots&c&0\\\ d(n-1)&0&0&\cdots&0&c\\\ \end{vmatrix}\text{ or }$
$\displaystyle\mathbf{T}_{P}$
$\displaystyle=\frac{1}{c+d(n-1)}\begin{vmatrix}c&d&d&\cdots&d&d\\\
d&c&d&\cdots&d&d\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
d&d&d&\cdots&c&d\\\ d&d&d&\cdots&d&c\\\ \end{vmatrix}$

For this game, therefore, the general self-interest level is equal to the
symmetrical self-interest level, as can clearly be seen by the second matrix
above, which is identical to the exchange matrix. However, the general self-
interest level demonstrates that there are a range of possible solutions,
which leave different players better or worse off after reward-transfers.

Results for the Arbitrary social dilemma The minimal transfer matrix, rounded
to three decimal places, is as follows

$\mathbf{T}^{*}=\begin{vmatrix}0.487&0.209&0.304\\\ 0.375&0.487&0\\\
0.478&0&0.487\end{vmatrix}$

Note that only the first row sums to one, so players 2 and 3 have excess
rewards that they may assign to either of their opponents. The symmetrical
self-interest level for this game is $s^{*}=0.364$, while $g^{*}=0.487$.

###  4.3 Discussion

For all the variants, we observe that the symmetrical self-interest level and
general self-interest level of Chicken and Stag Hunt are identical. In
Chicken, the task is to prevent players defecting against a cooperating
opponent. In Stag Hunt, the challenge is to prevent players from preferring to
defect against opponents believed to be defecting. Despite this difference,
due to the relative values to be gained or lost (a personal gain of $d$ at the
expense of $c-d$ to the opponent), the minimal reward transfer matrices are
the same.

By analysing the minimal transfer matrix, we are able to understand something
about the game structure. As we saw in the Cyclical and Circular variants, for
a given player, only the players who maximally impact them need to be
incentivised. Perhaps this is a trend for many games, and the minimal reward
transfer matrices may have a tendency to be sparse. While this observation
would be interested in that it would mean that players typically only need
transfer reward to a few others, minimising the total number of transfers, we
leave this observation for further work.

##  5 Conclusion

In this paper, we considered the problem of incentivising collective action in
social dilemmas. We introduced a mechanism where agents can enter a binding
agreement to transfer a proportion of their future rewards to each other. In
doing so, previously selfish agents now have a reason to prefer that their
partners achieve high rewards, which makes prosocial actions more attractive.
This mechanism is used in two ways, first to define two metrics that describe
the alignment between what is individually rational, and what is collectively
rational, and second, as a possible solution to social dilemmas that makes
cooperation the rational choice for all agents.

The first metric, called the symmetrical self-interest level, assumes that all
players exchange the same proportion of their rewards with each other, and is
comparable to other metrics in literature
apt14__selfishness_level_of_strategic_games . It represents the maximum amount
of self-interest that players can maintain while resolving a social dilemma
under such an exchange scheme. The benefit of this metric is that it is simple
to compute, as it only has one parameter. The second metric, called the
general self-interest level, relaxes the requirement that all players exchange
the same proportion of reward and allows players to transfer reward in an
unrestricted fashion. This can allow more efficient solutions to be found,
where the players need to transfer less reward by carefully considering which
opponents whose behaviour they benefit from influencing. We introduced an
algorithm to determine the general self-interest level and find an optimal
scheme of transfers for normal-form game representations of social dilemmas.
Potential applications of these metrics include the field of mechanism design,
whereby modifications to a game can be assessed for their impact on
collaboration.

The limitations of our approach include a requirement that the players have
access to a common currency, equally valued by all players, and the capability
to enter binding agreements. Unfortunately, the terms of the binding agreement
to transfer rewards are not guaranteed to be rational for all possible player
beliefs, which could limit the effectiveness of reward transfer as a solution
to social dilemmas. Finally, we have presented our method for the case that we
have a single social optima under mutual cooperation, which is not the case
for all games. However, we believe that our method can be generalised to
include other definitions of social dilemmas, like we did in Section 3.6. In
this case, if there are multiple outcomes that maximise the social welfare,
the players will have to agree in advance which social optimum to make
dominant. Once chosen, the procedure to make that outcome dominant will be
equivalent to Algorithm 1, merely targetting a different outcome.

Directions for future work include developing methods to compute the metrics
for other classes of games, such as Markov games, Bayesian games and robust
games. The limiting values used in this paper are sufficient to make
cooperation a dominant strategy, but if different solution concepts are
appropriate, the method can be adjusted to target the relevant outcomes. This
may make general reward transfer more widely applicable if using a different,
less strict definition of resolving. In this paper, we also discussed how
there is a need for metrics that assess the fairness of the post-transfer game
rewards to the unmodified game rewards. Additionally, it may be the case that
the minimal transfer matrix is typically fairly sparse, which would be
interesting and potentially useful in understanding the structure of a game.

It is worth noting that while those engaging in mutual cooperation benefit
from doing so, it is not always the case that this is better for society if
there are negative impacts on those excluded, such as in the case of collusion
between firms. See dafoe20__open_problems_in_cooperative_ai  for a more
detailed overview of the potential harms of cooperation.

## Competing interests

The authors have no relevant financial or non-financial interests to disclose
beyond the grant information detailed on the title page.

## References

  *   * (1) Ostrom, E., Walker, J., Gardner, R.: Covenants with and without a Sword: Self-Governance Is Possible. American Political Science Review 86(2), 404–417 (1992). https://doi.org/10.2307/1964229
  * (2) Dietz, T., Ostrom, E., Stern, P.C.: The Struggle to Govern the Commons. Science 302(5652), 1907–1912 (2003). https://doi.org/10.1126/science.1091015
  * (3) Apt, K.R., Schaefer, G.: Selfishness Level of Strategic Games. Journal of Artificial Intelligence Research 49, 207–240 (2014). https://doi.org/10.1613/jair.4164
  * (4) Deng, Y., Conitzer, V.: Disarmament Games with Resources. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, pp. 981–988. AAAI Press, New Orleans, Louisiana, USA (2018). https://doi.org/10.1609/aaai.v32i1.11443
  * (5) Nowak, M.A.: Five Rules for the Evolution of Cooperation. Science 314(5805), 1560–1563 (2006). https://doi.org/10.1126/science.1133755
  * (6) Hughes, E., Leibo, J.Z., Phillips, M., Tuyls, K., Dueñez-Guzman, E., Castañeda, A.G., Dunning, I., Zhu, T., McKee, K., Koster, R., Roff, H., Graepel, T.: Inequity aversion improves cooperation in intertemporal social dilemmas. In: 32nd Conference on Neural Information Processing Systems, pp. 3330–3340. Curran Associates, Inc., Montréal, Canada (2018)
  * (7) Hughes, E., Anthony, T.W., Eccles, T., Leibo, J.Z., Balduzzi, D., Bachrach, Y.: Learning to Resolve Alliance Dilemmas in Many-Player Zero-Sum Games. In: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, pp. 538–547. International Foundation for Autonomous Agents and Multiagent Systems, Auckland, New Zealand (2020)
  * (8) Schmid, K., Kölle, M., Matheis, T.: Learning to Participate through Trading of Reward Shares. In: Proceedings of the Adaptive and Learning Agents Workshop, Online (2022)
  * (9) Deng, Y., Tang, P., Zheng, S.: Complexity and Algorithms of K-implementation. In: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, Singapore (2016)
  * (10) Elias, J., Martignon, F., Avrachenkov, K., Neglia, G.: Socially-Aware Network Design Games. In: 2010 Proceedings IEEE INFOCOM, pp. 1–5. IEEE, San Diego, CA, USA (2010). https://doi.org/10.1109/INFCOM.2010.5462275
  * (11) Chen, P.-A., Kempe, D.: Altruism, selfishness, and spite in traffic routing. In: Proceedings of the 9th ACM Conference on Electronic Commerce, pp. 140–149. ACM, Chicago Il USA (2008). https://doi.org/%****␣paper.bbl␣Line␣225␣****10.1145/1386790.1386816
  * (12) Chen, P.-A., De Keijzer, B., Kempe, D., Schäfer, G.: The Robust Price of Anarchy of Altruistic Games. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) Internet and Network Economics vol. 7090, pp. 383–390. Springer Berlin Heidelberg, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25510-6_33
  * (13) Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M., Papaioannou, E.: The Impact of Altruism on the Efficiency of Atomic Congestion Games. In: Wirsing, M., Hofmann, M., Rauschmayer, A. (eds.) Trustworthly Global Computing vol. 6084, pp. 172–188. Springer Berlin Heidelberg, Berlin, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15640-3_12
  * (14) Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. Computer Science Review 3(2), 65–69 (2009). https://doi.org/10.1016/j.cosrev.2009.04.003
  * (15) Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The Price of Stability for Network Design with Fair Cost Allocation. In: 45th Annual IEEE Symposium on Foundations Of Computer Science, pp. 295–304. IEEE, Rome, Italy (2004). https://doi.org/10.1109/FOCS.2004.68
  * (16) Elkind, E., Fanelli, A., Flammini, M.: Price of Pareto Optimality in hedonic games. Artificial Intelligence 288, 103357 (2020). https://doi.org/10.1016/j.artint.2020.103357
  * (17) Axelrod, R.: An Evolutionary Approach to Norms. The American Political Science Review 80, 18 (1986) 1960858
  * (18) Mahmoud, S., Griffiths, N., Keppens, J., Luck, M.: An Analysis of Norm Emergence in Axelrod’s Model. 8th European Workshop on Multi-Agent Systems, 15 (2010)
  * (19) Montes, N., Sierra, C.: Value-Guided Synthesis of Parametric Normative Systems. Autonomous Agents and Multi-Agent Systems, 9 (2021)
  * (20) Sierra, C., Osman, N., Noriega, P., Sabater-Mir, J.: Value alignment: A formal approach. arXiv preprint arXiv:2110.09240, 15 (2021) arxiv:2110.09240
  * (21) Ohtsuki, H., Iwasa, Y.: The leading eight: Social norms that can maintain cooperation by indirect reciprocity. Journal of Theoretical Biology 239(4), 435–444 (2006). https://doi.org/10.1016/j.jtbi.2005.08.008
  * (22) Pereira, L.M., Lenaerts, T., Martinez-Vaquero, L.A.: Social Manifestation of Guilt Leads to Stable Cooperation in Multi-Agent Systems. In: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems, São Paulo, Brazil (2017)
  * (23) Lorini, E., Mühlenbernd, R.: The Long-Term Benefits of Following Fairness Norms under Dynamics of Learning and Evolution. Fundamenta Informaticae 158(1-3), 121–148 (2018). https://doi.org/10.3233/FI-2018-1644
  * (24) Jacq, A., Perolat, J., Geist, M., Pietquin, O.: Foolproof Cooperative Learning. arXiv (2020)
  * (25) Axelrod, R.: Effective Choice in the Prisoner’s Dilemma. Journal of Conflict Resolution 24(1), 3–25 (1980). https://doi.org/10.1177/002200278002400101
  * (26) Press, W.H., Dyson, F.J.: Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent. Proceedings of the National Academy of Sciences 109(26), 10409–10413 (2012). https://doi.org/10.1073/pnas.1206569109
  * (27) Hilbe, C., Nowak, M.A., Sigmund, K.: Evolution of extortion in Iterated Prisoner’s Dilemma games. Proceedings of the National Academy of Sciences 110(17), 6913–6918 (2013). https://doi.org/%****␣paper.bbl␣Line␣475␣****10.1073/pnas.1214834110
  * (28) Stewart, A.J., Plotkin, J.B.: From extortion to generosity, evolution in the Iterated Prisoner’s Dilemma. Proceedings of the National Academy of Sciences 110(38), 15348–15353 (2013). https://doi.org/10.1073/pnas.1306246110
  * (29) Hofbauer, J., Sigmund, K.: Evolutionary Game Dynamics 40(4), 479–519 (2003). https://doi.org/10.1090/S0273-0979-03-00988-1
  * (30) Nowak, M.A., Sigmund, K.: Evolutionary Dynamics of Biological Games. Science 303(5659), 793–799 (2004). https://doi.org/10.1126/science.1093411
  * (31) Rand, D.G., Nowak, M.A.: The evolution of antisocial punishment in optional public goods games. Nature Communications 2(1), 434 (2011). https://doi.org/10.1038/ncomms1442
  * (32) Leyton-Brown, K., Shoham, Y.: Essentials of Game Theory: A Concise, Multidisciplinary Introduction. Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 3. Morgan & Claypool, San Rafael, Calif. (2008)
  * (33) Peysakhovich, A., Lerer, A.: Prosocial Learning Agents Solve Generalized Stag Hunts Better than Selfish Ones. arXiv (2017)
  * (34) McKee, K.R., Gemp, I., McWilliams, B., Duéñez-Guzmán, E.A., Hughes, E., Leibo, J.Z.: Social Diversity and Social Preferences in Mixed-Motive Reinforcement Learning. In: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, pp. 869–877. International Foundation for Autonomous Agents and Multiagent Systems, Auckland, New Zealand (2020). https://doi.org/10.5555/3398761.3398863
  * (35) Haeri, H.: Reward-Sharing Relational Networks in Multi-Agent Reinforcement Learning as a Framework for Emergent Behavior. In: Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems, pp. 1808–1810. International Foundation for Autonomous Agents and Multiagent Systems, Online (2021). https://doi.org/10.5555/3463952.3464246
  * (36) Wang, J.X., Hughes, E., Fernando, C., Czarnecki, W.M., Duéñez-Guzmán, E.A., Leibo, J.Z.: Evolving Intrinsic Motivations for Altruistic Behavior. In: Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pp. 683–692. International Foundation for Autonomous Agents and Multiagent Systems, Montreal QC, Canada (2019)
  * (37) Christoffersen, P.J.K., Haupt, A.A., Hadfield-Menell, D.: Get It in Writing: Formal Contracts Mitigate Social Dilemmas in Multi-Agent RL. arXiv (2022)
  * (38) Sodomka, E., Hilliard, E.M., Littman, M.L., Greenwald, A.: Coco-Q: Learning in Stochastic Games with Side Payments. In: Proceedings of the 30th International Conference on Machine Learning. 3, vol. 28, pp. 1471–1479. JMLR.org, Atlanta, Georgia, USA (2013)
  * (39) Deng, Y., Conitzer, V.: Disarmament Games. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pp. 473–479. AAAI Press, San Francisco, California USA (2017). https://doi.org/10.1609/aaai.v31i1.10573
  * (40) Lupu, A., Precup, D.: Gifting in Multi-Agent Reinforcement Learning. In: New Zealand, p. 9 (2020)
  * (41) Wang, W.Z., Beliaev, M., Bıyık, E., Lazar, D.A., Pedarsani, R., Sadigh, D.: Emergent Prosociality in Multi-Agent Games Through Gifting. In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pp. 434–442. ijcai.org, Montreal, Canada (2021). https://doi.org/10.24963/ijcai.2021/61
  * (42) Yang, J., Li, A., Farajtabar, M., Sunehag, P., Hughes, E., Zha, H.: Learning to Incentivize Other Learning Agents. In: Proceedings of the 34th Conference on Neural Information Processing Systems, vol. 33, pp. 15208–15219. Curran Associates, Inc., Vancouver, Canada (2020)
  * (43) Gemp, I., McKee, K.R., Everett, R., Duéñez-Guzmán, E.A., Bachrach, Y., Balduzzi, D., Tacchetti, A.: D3C: Reducing the Price of Anarchy in Multi-Agent Learning. In: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pp. 498–506. International Foundation for Autonomous Agents and Multiagent Systems, Online (2022). https://doi.org/10.5555/3535850.3535907
  * (44) Macy, M.W., Flache, A.: Learning dynamics in social dilemmas. Proceedings of the National Academy of Sciences of the National Academy of Sciences 99, 7229–7236 (2002)
  * (45) Leibo, J.Z., Zambaldi, V., Lanctot, M.: Multi-agent Reinforcement Learning in Sequential Social Dilemmas. In: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems, pp. 464–473. ACM, São Paulo, Brazil (2017)
  * (46) Schelling, T.C.: Hockey Helmets, Concealed Weapons, and Daylight Saving: A Study of Binary Choices With Externalities. Journal of Conflict Resolution 17(3), 381–428 (1973). https://doi.org/10.1177/002200277301700302
  * (47) Shapley, L.S.: A value for _n_ -person games. In: Roth, A.E. (ed.) The Shapley Value, 1st edn., pp. 31–40. Cambridge University Press, ??? (1988). https://doi.org/10.1017/CBO9780511528446.003
  * (48) Bachrach, Y., Polukarov, M., Jennings, N.R.: The Good, The Bad and The Cautious: Safety Level Cooperative Games. In: Saberi, A. (ed.) Internet and Network Economics vol. 6484, pp. 432–443. Springer Berlin Heidelberg, Berlin, Heidelberg (2010). https://doi.org/%****␣paper.bbl␣Line␣825␣****10.1007/978-3-642-17572-5_36
  * (49) Harsanyi, J.C.: Games with Incomplete Information Played by “Bayesian” Players, I–III: Part I. The Basic Model. Management Science 50(12_supplement), 1804–1817 (2004). https://doi.org/10.1287/mnsc.1040.0270
  * (50) Dafoe, A., Hughes, E., Bachrach, Y., Collins, T., McKee, K.R., Leibo, J.Z., Larson, K., Graepel, T.: Open Problems in Cooperative AI (2020)