Multi-agent Reinforcement Learning in
Sequential Social Dilemmas
Joel Z. Leibo1

Vinicius Zambaldi1

Marc Lanctot

DeepMind, London, UK
jzl@google.com

DeepMind, London, UK
vzambaldi@google.com

DeepMind, London, UK
lanctot@google.com

Janusz Marecki

Thore Graepel

DeepMind, London, UK
tartel@google.com

DeepMind, London, UK
thore@google.com

ABSTRACT
Matrix games like Prisoner’s Dilemma have guided researchon social dilemmas for decades. However, they necessarily
treat the choice to cooperate or defect as an atomic action.
In real-world social dilemmas these choices are temporally
extended. Cooperativeness is a property that applies to policies, not elementary actions. We introduce sequential social
dilemmas that share the mixed incentive structure of matrix
game social dilemmas but also require agents to learn policies that implement their strategic intentions. We analyze
the dynamics of policies learned by multiple self-interested
independent learning agents, each using its own deep Qnetwork, on two Markov games we introduce here: 1. a fruit
Gathering game and 2. a Wolfpack hunting game. We characterize how learned behavior in each domain changes as afunction of environmental factors including resource abundance. Our experiments show how conflict can emerge fromcompetition over shared resources and shed light on how
the sequential nature of real world social dilemmas affects
cooperation.

CCS Concepts•Computing methodologies → Multi-agent reinforcement learning; Agent / discrete models; Stochastic games;

Keywords
Social dilemmas, cooperation, Markov games, agent-basedsocial simulation, non-cooperative games

1.

INTRODUCTION

Social dilemmas expose tensions between collective andindividual rationality [1]. Cooperation makes possible better outcomes for all than any could obtain on their own.
However, the lure of free riding and other such parasitic
strategies implies a tragedy of the commons that threatens
the stability of any cooperative venture [2].
1

These authors contributed equally.

Appears in: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), S. Das, E. Durfee, K. Larson, M. Winikoff(eds.), May 8–12, 2017, São Paulo, Brazil.
Copyright © 2017, International Foundation for Autonomous Agents andMultiagent Systems (www.ifaamas.org). All rights reserved.

The theory of repeated general-sum matrix games provides a framework for understanding social dilemmas. Fig.
1 shows payoff matrices for three canonical examples: Prisoner’s Dilemma, Chicken, and Stag Hunt. The two actions
are interpreted as cooperate and defect respectively. The
four possible outcomes of each stage game are R (reward
of mutual cooperation), P (punishment arising from mutual defection), S (sucker outcome obtained by the player
who cooperates with a defecting partner), and T (temptation outcome achieved by defecting against a cooperator).
A matrix game is a social dilemma when its four payoffs
satisfy the following social dilemma inequalities (this formulation from [3]):1. R > P
defection.

Mutual cooperation is preferred to mutual(1)

2. R > S
Mutual cooperation is preferred to being
exploited by a defector.
(2)
3. 2R > T + S This ensures that mutual cooperation ispreferred to an equal probability of unilateral cooperation and defection.
(3)
4. either greed : T > R
Exploiting a cooperator ispreferred over mutual cooperationorfear : P > S
Mutual defection is preferredover being exploited.
(4)
Matrix Game Social Dilemmas (MGSD) have been fruitfully employed as models for a wide variety of phenomenain theoretical social science and biology. For example, there
is a large and interesting literature concerned with mechanisms through which the socially preferred outcome of mutual cooperation can be stabilized, e.g., direct reciprocity [4,5, 6, 7], indirect reciprocity [8], norm enforcement [9, 10],
simple reinforcement learning variants [3], multiagent reinforcement learning [11, 12, 13, 14, 15], spatial structure [16],emotions [17], and social network effects [18, 19].
However, the MGSD formalism ignores several aspects ofreal world social dilemmas which may be of critical importance.
1. Real world social dilemmas are temporally extended.
2. Cooperation and defection are labels that apply to policies implementing strategic decisions.
3. Cooperativeness may be a graded quantity.

C
D

C
R, R
T, S

D
S, T
P, P

Chicken

C
D

C
3, 3
4, 1

D
1, 4
0, 0

Stag Hunt

C
D

C
4, 4
3, 0

D
0, 3
1, 1

Prisoners

C
D

C
3, 3
4, 0

D
0, 4
1, 1

Figure 1: Canonical matrix game social dilemmas. Left: Outcome variables R, P , S, and T are mapped tocells of the game matrix. Right: The three canonical matrix game social dilemmas. By convention, a cell of
X, Y represents a utility of X to the row player and Y to the column player. In Chicken, agents may defect outof greed. In Stag Hunt, agents may defect out of fear of a non-cooperative partner. In Prisoner’s Dilemma,
agents are motivated to defect out of both greed and fear simultaneously.
4. Decisions to cooperate or defect occur only quasi-simultaneously since some information about what player
2 is starting to do can inform player 1’s decision andvice versa.
5. Decisions must be made despite only having partial
information about the state of the world and the activities of the other players.
We propose a Sequential Social Dilemma (SSD) model tobetter capture the above points while, critically, maintaining
the mixed motivation structure of MGSDs. That is, analogous inequalities to (1) – (4) determine when a temporallyextended Markov game is an SSD.
To demonstrate the importance of capturing sequential
structure in social dilemma modeling, we present empirical game-theoretic analyses [20, 21] of SSDs to identify theempirical payoff matrices summarizing the outcomes thatwould arise if cooperate and defect policies were selected as
one-shot decisions. The empirical payoff matrices are themselves valid matrix games. Our main result is that bothof the SSDs we considered, Gathering and Wolfpack, haveempirical payoff matrices that are Prisoner’s Dilemma (PD).
This means that if one were to adhere strictly to the MGSDmodeling paradigm, PD models should be proposed for bothsituations. Thus any conclusions reached from simulatingthem would necessarily be quite similar in both cases (andto other studies of iterated PD). However, when viewed as
SSDs, the formal equivalence of Gathering and Wolfpack
disappears. They are clearly different games. In fact, there
are simple experimental manipulations that, when applied
to Gathering and Wolfpack, yield opposite predictions concerning the emergence and stability of cooperation.
More specifically, we describe a factor that promotes the
emergence of cooperation in Gathering while discouraging
its emergence in Wolfpack, and vice versa. The straightforward implication is that, for modeling real-world social
dilemmas with SSDs, the choice of whether to use a Gatheringlike or Wolfpack-like model is critical. And the differences
between the two cannot be captured by MGSD modeling.
Along the way to these results, the present paper also
makes a small methodological contribution. Owing to thegreater complexity arising from their sequential structure, it
is more computationally demanding to find equilibria of SSD
models than it is for MGSD models. Thus the standard evolution and learning approaches to simulating MGSDs cannot
be applied to SSDs. Instead, more sophisticated multiagent
reinforcement learning methods must be used (e.g [22, 23,24]). In this paper we describe how deep Q-networks (e.g[25]) may be applied to this problem of finding equilibria of
SSDs.

Figure 2: Venn diagram showing the relationshipbetween Markov games, repeated matrix games,
MGSDs, and SSDs. A repeated matrix game is an
MGSD when it satisfies the social dilemma inequalities (eqs. 1 – 4). A Markov game with |S| > 1 isan SSD when it can be mapped by empirical gametheoretic analysis (EGTA) to an MGSD. Many SSDs
may map to the same MGSD.

2.

DEFINITIONS AND NOTATION

We model sequential social dilemmas as general-sum Markov(simultaneous move) games with each agent having only apartial observation onto their local environment. Agents
must learn an appropriate policy while coexisting with one
another. A policy is considered to implement cooperation
or defection by properties of the realizations it generates. A
Markov game is an SSD if and only if it contains outcomesarising from cooperation and defection policies that satisfy
the same inequalities used to define MGSDs (eqs. 1 – 4).
This definition is stated more formally in sections 2.1 and2.2 below.

2.1

Markov GamesA two-player partially observable Markov game M is defined by a set of states S and an observation function O :S ×{1, 2} → Rd specifying each player’s d-dimensional view,along with two sets of actions allowable from any state A1
and A2 , one for each player, a transition function T : S ×
A1 × A2 → ∆(S), where ∆(S) denotes the set of discrete
probability distributions over S, and a reward function foreach player: ri : S × A1 × A2 → R for player i. Let Oi ={oi | s ∈ S, oi = O(s, i)} be the observation space of player i.
To choose actions, each player uses policy πi : Oi → ∆(Ai ).
For temporal discount factor γ ∈ [0, 1] we can define thelong-term payoff Vi~π (s0 ) to player i when the joint policy

~π = (π1 , π2 ) is followed starting from state s0 ∈ S.

Vi~π (s0 ) = E~at ∼~π(O(st )),st+1 ∼T (st ,~at )

"∞
X

#
t

γ ri (st , ~at ) . (5)t=0Matrix games are the special case of two-player perfectly
observable (Oi (s) = s) Markov games obtained when |S| =1. MGSDs also specify A1 = A2 = {C, D}, where C and D
are called (atomic) cooperate and defect respectively.
The outcomes R(s), P (s), S(s), T (s) that determine whena matrix game is a social dilemma are defined as follows.
C

C

C

C

R(s) := V1π ,π (s) = V2π ,π (s),

(6)

D
D
D
D
P (s) := V1π ,π (s) = V2π ,π (s),

(7)

C
D
D
C
S(s) := V1π ,π (s) = V2π ,π (s),

(8)

D
C
C
D
T (s) := V1π ,π (s) = V2π ,π (s),(9)

where π C and π D are cooperative and defecting policies as
described next. Note that a matrix game is a social dilemma
when R, P, S, T satisfy the inequalities (1) – (4).

2.2

Definition of Sequential Social DilemmaThis definition is based on a formalization of empiricalgame-theoretic analysis [20, 21]. We define the outcomes(R, P, S, T ) := (R(s0 ), P (s0 ), S(s0 ), T (s0 )) induced by initial state s0 , and two policies π C , π D , through their longterm expected payoff (5) and the definitions (6) – (9). We
refer to the game matrix with R, P , S, T organized as inFig. 1-left. as an empirical payoff matrix following the terminology of [21].
Definition:
A sequential social dilemma is a tuple(M, ΠC , ΠD ) where ΠC and ΠD are disjoint sets of policies that are said to implement cooperation and defection
respectively. M is a Markov game with state space S. Let
the empirical payoff matrix (R(s), P (s), S(s), T (s)) be induced by policies (π C ∈ ΠC , π D ∈ ΠD ) via eqs. (5) – (9).
A Markov game is an SSD when there exist states s ∈ S
for which the induced empirical payoff matrix satisfies thesocial dilemma inequalities (1) – (4).
S
Remark: There is no guarantee that ΠC ΠD = Π, theset of all legal policies. This reflects the fact that, in practicefor sequential behavior, cooperativeness is usually a gradedproperty. Thus we are forced to define ΠC and ΠD by thresholding a continuous social behavior metric. For example, toconstruct an SSD for which a policy’s level of aggressivenessα : Π → R is the relevant social behavior metric, we pickthreshold values αc and αd so that α(π) < αc ⇐⇒ π ∈ ΠC
and α(π) > αd ⇐⇒ π ∈ ΠD .

3.

LEARNING ALGORITHMS

Most previous work on finding policies for Markov games
takes the prescriptive view of multiagent learning [26]: thatis, it attempts to answer “what should each agent do?” Several algorithms and analyses have been developed for thetwo-player zero-sum case [22, 27, 28, 29, 30]. The generalsum case is significantly more challenging [31], and algorithms either have strong assumptions or need to either track
several different potential equilibria per agent [32, 33], modelother players to simplify the problem [34], or must find a

Figure 3: Left: Gathering. In this frame the blue
player is directing its beam at the apple respawn
location. The red player is approaching the apples
from the south. Right: Wolfpack. The size of theagent’s view relative to the size of the map is illustrated. If an agent is inside the blue diamondshaped region around the prey when a capture
occurs—when one agent touches the prey—both it
and its partner receive a reward of rteam .

cyclic strategy composed of several policies obtained throughmultiple state space sweeps [35]. Researchers have also studied the emergence of multi-agent coordination in the decentralized, partially observable MDP framework [36, 37, 38].
However, that approach relies on knowledge of the underlying Markov model, an unrealistic assumption for modelingreal-world social dilemmas.
In contrast, we take a descriptive view, and aim to answer“what social effects emerge when each agent uses a particular learning rule?” The purpose here then is to study andcharacterize the resulting learning dynamics, as in e.g., [13,15], rather than on designing new learning algorithms. It is
well-known that the resulting “local decision process” could
be non-Markovian from each agent’s perspective [39]. Thisis a feature, not a bug in descriptive work since it is a property of the real environment that the model captures.
We use deep reinforcement learning as the basis for eachagent in part because of its recent success with solving complex problems [25, 40]. Also, temporal difference predictions
have been observed in the brain [41] and this class of reinforcement learning algorithm is seen as a candidate theoryof animal habit-learning [42].

3.1

Deep Multiagent Reinforcement Learning

Modern deep reinforcement learning methods take theperspective of an agent that must learn to maximize its cumulative long-term reward through trial-and-error interactions with its environment [43, 44].
In the multi-agent setting, the i-th agent stores a function
Qi : Oi × Ai → R represented by a deep Q-network (DQN).
See [25] for details in the single agent case. In our casethe true state s is observed differently by each player, as
oi = O(s, i). However for consistency of notation, we use ashorthand: Qi (s, a) = Qi (O(s, i), a).
During learning, to encourage exploration we parameterize the i-th agent’s policy byπi (s) =argmaxa∈Ai Qi (s, a)U(Ai )

with probability 1 − with probability 

where U(Ai ) denotes a sample from the uniform distribution

over Ai . Each agent updates its policy given a stored batch1of experienced transitions {(s, a, ri , s0 )t : t = 1, . . . T } such
that


0
0
Qi (s , a ) − Qi (s, a)Qi (s, a) ← Qi (s, a) + α ri + γ max
0a ∈AiThis is a “growing batch” approach to reinforcement learning in the sense of [45]. However, it does not grow in an unbounded fashion. Rather, old data is discarded so the batch
can be constantly refreshed with new data reflecting more
recent transitions. We compared batch sizes of 1e5 (ourdefault) and 1e6 in our experiments (see Sect. 5.3). The
network representing the function Q is trained through gradient descent on the mean squared Bellman residual with the
expectation taken over transitions uniformly sampled fromthe batch (see [25]). Since the batch is constantly refreshed,
the Q-network may adapt to the changing data distribution
arising from the effects of learning on π1 and π2 .
In order to make learning in SSDs tractable, we makethe extra assumption that each individual agent’s learning
depends only on the other agent’s learning via the (slowly)changing distribution of experience it generates. That is, thetwo learning agents are “independent” of one another andeach regard the other as part of the environment. From theperspective of player one, the learning of player two shows
up as a non-stationary environment. The independence assumption can be seen as a particular kind of bounded rationality: agents do no recursive reasoning about one another’s
learning. In principle, this restriction could be dropped
through the use of planning-based reinforcement learning
methods like those of [24].

4.

SIMULATION METHODSBoth games studied here were implemented in a 2D gridworld game engine. The state st and the joint action of all
players ~a determines the state at the next time-step st+1 .
Observations O(s, i) ∈ R3×16×21 (RGB) of the true state st
depended on the player’s current position and orientation.
The observation window extended 15 grid squares ahead
and 10 grid squares from side to side (see Fig. 3B). Actions a ∈ R8 were agent-centered: step forward, step backward, step left, step right, rotate left, rotate right, use beamand stand still. Each player appears blue in its own local
view, light-blue in its teammates view and red in its opponent’s view. Each episode lasted for 1, 000 steps. Default
neural networks had two hidden layers with 32 units, interleaved with rectified linear layers which projected to the
output layer which had 8 units, one for each action. During
training, players implemented epsilon-greedy policies, withepsilon decaying linearly over time (from 1.0 to 0.1). The
default per-time-step discount rate was 0.99.

5.

RESULTSIn this section, we describe three experiments: one foreach game (Gathering and Wolfpack), and a third experiment investigating parameters that influence the emergenceof cooperation versus defection.

5.1

Experiment 1: Gathering

The goal of the Gathering game is to collect apples, represented by green pixels (see Fig. 3A). When a player collects
1

The batch is sometimes called a “replay buffer” e.g. [25].

Figure 4: Social outcomes are influenced by environment parameters. Top: Gathering. Shown isthe beam-use rate (aggressiveness) as a function ofre-spawn time of apples Napple (abundance) and respawn time of agents Ntagged (conflict-cost). These
results show that agents learn aggresssive policies inenvironments that combine a scarcity of resources
with the possibility of costly action. Less aggressive
policies emerge from learning in relatively abundantenvironments with less possibility for costly action.
Bottom: Wolfpack. Shown is two minus the average number of wolves per capture as a function of
the capture radius and group capture benefit (rteam ).
Again as expected, greater group benefit and larger
capture radius lead to an increase in wolves per capture, indicating a higher degree of cooperation.

an apple it receives a reward of 1 and the apple is temporarily removed from the map. The apple respawns after Napple
frames. Players can direct a beam in a straight line along
their current orientation. A player hit by the beam twice
is “tagged” and removed from the game for Ntagged frames.
No rewards are delivered to either player for tagging. The
only potential motivation for tagging is competition over theapples. Refer to the Gathering gameplay video2 for demonstration.
Intuitively, a defecting policy in this game is one thatis aggressive—i.e., involving frequent attempts to tag rival
players to remove them from the game. Such a policy is motivated by the opportunity to take all the apples for oneselfthat arises after eliminating the other player. By contrast,
a cooperative policy is one that does not seek to tag theother player. This suggests the use of a social behavior met2

https://goo.gl/2xczLc

ric (section 2.2) that measures a policy’s tendency to use
the beam action as the basis for its classification as defection or cooperation. To this end, we counted the numberof beam actions during a time horizon and normalized it by
the amount of time in which both agents were playing (notremoved from the game).
By manipulating the rate at which apples respawn after
being collected, Napple , we could control the abundance ofapples in the environment. Similarly, by manipulating thenumber of timesteps for which a tagged agent is removed
from the game, Ntagged , we could control the cost of potential conflict. We wanted to test whether conflict would
emerge from learning in environments where apples were
scarce. We considered the effect of abundance (Napple ) andconflict-cost (Ntagged ) on the level of aggressiveness (beamuse rate) that emerges from learning. Fig. 4A shows thebeam-use rate that evolved after training for 40 million steps
as a function of abundance (Napple ) and conflict-cost (Ntagged ).
Supplementary video 3 shows how such emergent conflict
evolves over the course of learning. In this case, differencesin beam-use rate (proxy for the tendency to defect) learnedin the different environments emerge quite early in training
and mostly persist throughout. When learning does change
beam-use rate, it is almost always to increase it.
We noted that the policies learned in environments withlow abundance or high conflict-cost were highly aggressive
while the policies learned with high abundance or low conflictcost were less aggressive. That is, the Gathering game predicts that conflict may emerge from competition for scarce
resources, but is less likely to emerge when resources areplentiful.
To further characterize the mixed motivation structureof the Gathering game, we carried out the empirical gametheoretic analysis suggested by the definition of section 2.2.
We chose the set of policies ΠC that were trained in the highabundance / low conflict-cost environments (low aggression
policies) and ΠD as policies trained in the low abundanceand high conflict-cost environments (high aggression policies), and used these to compute empirical payoff matrices
as follows. Two pairs of policies (π1C , π1D ) and (π2C , π2D ) aresampled from ΠC and ΠD and matched against each otherin the Gathering game for one episode. The resulting rewards are assigned to individual cells of a matrix game, inwhich πiC corresponds the cooperative action for player i,and πjD , the defective action for player j. This process isrepeated until convergence of the cell values, and generates
estimates of R, P, S, and T for the game corresponding toeach abundance / conflict-cost (Napple , Ntagged ) level tested.
See Figure 5 for an illustration of this workflow. Fig. 6A
summarizes the types of empirical games that were foundgiven our parameter spectrum. Most cases where the social
dilemma inequalities (1) – (4) held, i.e., the strategic scenario was a social dilemma, turned out to be a prisoner’s
dilemma. The greed motivation reflects the temptation totake out a rival and collect all the apples oneself. The fear
motivation reflected the danger of being taken out oneself
by a defecting rival. P is preferred to S in the Gathering
game because mutual defection typically leads to both players alternating tagging one another, so each gets some timealone to collect apples. Whereas the agent receiving the outcome S does not try to tag its rival and thus never gets thischance.

5.2

5.3

https://goo.gl/w2VqlQExperiment 3: Agent parameters influencing the emergence of defection

So far we have described how properties of the environment influence emergent social outcomes. Next we consider
the impact of manipulating properties of the agents. Psychological research attempting to elucidate the motivational
factors underlying human cooperation is relevant here. In
particular, Social Psychology has advanced various hypotheses concerning psychological variables that may influence cooperation and give rise to the observed individual differencesin human cooperative behavior in laboratory-based social
dilemmas [2]. These factors include consideration-of-futureconsequences [46], trust [47], affect (interestingly, it is negative emotions that turn out to promote cooperation [48]),and a personality variable called social value orientation
characterized by other-regarding-preferences. The latter has
been studied in a similar Markov game social dilemma setup
to our SSD setting by [49].
Obviously the relatively simple DQN learning agents weconsider here do not have internal variables that directly correspond to the factors identified by Social Psychology. Nor
4

3

Experiment 2: Wolfpack

The Wolfpack game requires two players (wolves) to chasea third player (the prey). When either wolf touches the prey,
all wolves within the capture radius (see Fig. 3B) receive areward. The reward received by the capturing wolves is proportional to the number of wolves in the capture radius. The
idea is that the prey is dangerous, a lone wolf can overcomeit, but is at risk of losing the carcass to scavengers. However, when the two wolves capture the prey together, they
can better protect the carcass from scavengers and hence receive a higher reward. A lone-wolf capture provides a reward
of rlone and a capture involving both wolves is worth rteam .
Refer to the Wolfpack gameplay video4 for demonstration.
The wolves learn to catch the prey over the course of training. Fig. 4B shows the effect on the average number ofwolves per capture obtained from training in environmentswith varying levels of group capture bonus rteam /rlone andcapture radius. Supplementary video 5 shows how this dependency evolves over learning time. Like in the Gathering
game, these results show that environment parameters influence how cooperative the learned policies will be. It isinteresting that two different cooperative policies emerged
from these experiments. On the one hand, the wolves could
cooperate by first finding one another and then moving together to hunt the prey, while on the other hand, a wolf
could first find the prey and then wait for the other wolf toarrive before capturing it.
Analogous to our analysis of the Gathering game, we chooseΠC and ΠD for Wolfpack to be the sets of policies learnedin the high radius / group bonus and low radius /groupbonus environments respectively. The procedure for estimating R, P, S, and T was the same as in section 5.1. Fig.
6B summarizes these results. Interestingly, it turns out that
all three classic MGSDs, chicken, stag hunt, and prisoner’s
dilemma can be found in the empirical payoff matrices of
Wolfpack.

5

https://goo.gl/AgXtTn
https://goo.gl/vcB8mU

Figure 5: Workflow to obtain empirical payoff matrices from Markov games. Agents are trained under
different environmental conditions, e.g., with high or low abundance (Gathering case) or team capture bonus(Wolfpack case) resulting in agents classified as cooperators (π C ∈ ΠC ) or defectors (π D ∈ ΠD ). Empirical
game payoffs are estimated by sampling (π1 , π2 ) from ΠC × ΠC , ΠC × ΠD , ΠD × ΠC , and ΠD × ΠD . By repeatedly
playing out the resulting games between the sampled π1 and π2 , and averaging the results, it is possible toestimate the payoffs for each cell of the matrix.
should they be expected to capture the full range of humanindividual differences in laboratory social dilemmas. Nevertheless, it is interesting to consider just how far one can go
down this road of modeling Social Psychology hypotheses
using such simple learning agents6 . Recall also that DQN
is in the class of reinforcement learning algorithms that is
generally considered to be the leading candidate theory ofanimal habit-learning [50, 42]. Thus, the interpretation of
our model is that it only addresses whatever part of cooperative behavior arises “by habit” as opposed to conscious
deliberation.
Experimental manipulations of DQN parameters yield consistent and interpretable effects on emergent social behavior.
Each plot in Fig. 7 shows the relevant social behavior metric,
conflict for Gathering and lone-wolf behavior for Wolfpack,
as a function of an environment parameter: Napple , Ntagged(Gathering) and rteam /rlone (Wolfpack). The figure showsthat in both games, agents with greater discount parameter (less time discounting) more readily defect than agentsthat discount the future more steeply. For Gathering thislikely occurs because the defection policy of tagging theother player to temporarily remove them from the game only
provides a delayed reward in the form of the increased opportunity to collect apples without interference. However,when abundance is very high, even the agents with higher
discount factors do not learn to defect. In such paradisiacal settings, the apples respawn so quickly that an individual agent cannot collect them quickly enough. As a consequence, there is no motivation to defect regardless of thetemporal discount rate. Manipulating the size of the storedand-constantly-refreshed batch of experience used to traineach DQN agent has the opposite effect on the emergence of
defection. Larger batch size translates into more experience
with the other agent’s policy. For Gathering, this meansthat avoiding being tagged becomes easier. Evasive action
benefits more from extra experience than the ability to target the other agent. For Wolfpack, larger batch size allows
6
The contrasting approach that seeks to build more structure into the reinforcement learning agents to enable moreinterpretable experimental manipulations is also interesting
and complementary e.g., [24].

greater opportunity to learn to coordinate to jointly catchthe prey.
Possibly the most interesting effect on behavior comesfrom the number of hidden units in the neural network behind the agents, which may be interpreted as their cognitive capacity. Curves for tendency to defect are shown in
the right column of Fig. 7, comparing two different network
sizes. For Gathering, an increase in network size leads toan increase in the agent’s tendency to defect, whereas for
Wolfpack the opposite is true: Greater network size leads toless defection.
This can be explained as follows. In Gathering, defection behavior is more complex and requires a larger network
size to learn than cooperative behavior. This is the casebecause defection requires the difficult task of targeting the
opposing agent with the beam whereas peacefully collecting
apples is almost independent of the opposing agent’s behavior. In Wolfpack, cooperation behavior is more complex andrequires a larger network size because the agents need to coordinate their hunting behaviors to collect the team reward
whereas the lone-wolf behavior does not require coordination with the other agent and hence requires less network
capacity.
Note that the qualitative difference in effects for network
size supports our argument that the richer framework of
SSDs is needed to capture important aspects of real social
dilemmas. This rather striking difference between Gatheringand Wolfpack is invisible to the purely matrix game based
MGSD-modeling. It only emerges when the different complexities of cooperative or defecting behaviors, and hence thedifficulty of the corresponding learning problems is modeled
in a sequential setup such as an SSD.

6.

DISCUSSION

In the Wolfpack game, learning a defecting lone-wolf policy is easier than learning a cooperative pack-hunting policy. This is because the former does not require actions
to be conditioned on the presence of a partner within thecapture radius. In the Gathering game the situation is reversed. Cooperative policies are easier to learn since theyneed only be concerned with apples and may not depend

Figure 6: Summary of matrix games discovered within Gathering (Left) and Wolfpack (Right) throughextracting empirical payoff matrices. The games are classified by social dilemma type indicated by color andquandrant. With the x-axis representing fear = P − S and the y-axis representing greed = T − R, the lower
right quadrant contains Stag Hunt type games (green), the top left quadrant Chicken type games (blue),and the top right quadrant Prisoner’s Dilemma type games (red). Non-SSD type games, which either violatesocial dilemma condition (1) or do not exhibit fear or greed are shown as well.
on the rival player’s actions. However, optimally efficient
cooperative policies may still require such coordination toprevent situations where both players simultaneously moveon the same apple. Cooperation and defection demand differing levels of coordination for the two games. Wolfpack’s
cooperative policy requires greater coordination than its defecting policy. Gathering’s defection policy requires greater
coordination (to successfully aim at the rival player).
Both the Gathering and Wolfpack games contain embedded MGSDs with prisoner’s dilemma-type payoffs. The MGSD
model thus regards them as structurally identical. Yet,
viewed as SSDs, they make rather different predictions. Thissuggests a new dimension on which to investigate classic
questions concerning the evolution of cooperation. For any
to-be-modeled phenomenon, the question now arises: which
SSD is a better description of the game being played? If
Gathering is a better model, then we would expect cooperation to be the easier-to-learn “default” policy, probably
requiring less coordination. For situations where Wolfpack
is the better model, defection is the easier-to-learn “default”
behavior and cooperation is the harder-to-learn policy requiring greater coordination. These modeling choices are
somewhat orthogonal to the issue of assigning values to thevarious possible outcomes (the only degree of freedom in
MGSD-modeling), yet they make a large difference to theresults.
SSD models address similar research questions as MGSD
models, e.g. the evolution of cooperation. However, SSD
models are more realistic since they capture the sequential
structure of real-world social dilemmas. Of course, in modeling, greater verisimilitude is not automatically virtuous.
When choosing between two models of a given phenomenon,

Occam’s razor demands we prefer the simpler one. If SSDs
were just more realistic models that led to the same conclusions as MGSDs then they would not be especially useful.
This however, is not the case. We argue the implication of
the results presented here is that standard evolutionary andlearning-based approaches to modeling the trial and error
process through which societies converge on equilibria of social dilemmas are unable to address the following importantlearning related phenomena.
1. Learning which strategic decision to make, abstractly,
whether to cooperate or defect, often occurs simultaneously with learning how to efficiently implement saiddecision.
2. It may be difficult to learn how to implement an effective cooperation policy with a partner bent on defection—or vice versa.
3. Implementing effective cooperation or defection may
involve solving coordination subproblems, but there is
no guarantee this would occur, or that cooperation anddefection would rely on coordination to the same extent. In some strategic situations, cooperation may
require coordination, e.g., standing aside to allow apartner’s passage through a narrow corridor while inothers defection may require coordination e.g. blocking a rival from passing.
4. Some strategic situations may allow for multiple different implementations of cooperation, and each may
require coordination to a greater or lesser extent. The
same goes for multiple implementations of defection.

0.12

Aggressiveness

0.12

0.11
0.10

0.10
0.08
0.06
0.04

+

Lone-wolf capture rate

0.70

0.66

0.62
0.60
0.58
0.56
0.54

0.08
0.07

Discount: 0.99
Discount: 0.995
Scarcity
Discount: 0.99
Discount: 0.995

0.68

0.64

0.09

+

0.06
0.05
0.04

0.08
0.06

Batch size: 1e+04
Batch size: 1e+05
Scarcity

0.75

Batch size: 1e+04
Batch size: 1e+05

0.70
0.65
0.60
0.55

Group benefit

_

0.10

0.50

_

0.04

0.70

0.55
0.50
0.45
0.40

Network size: 16
Network size: 64
Scarcity
Network size: 16
Network size: 64

0.65
0.60

Group benefit+_

Group benefit

Figure 7: Factors influencing the emergence of defecting policies. Top row: Gathering. Shown are plotsof average beam-use rate (aggressiveness) as a function of Napple (scarcity) Bottom row: Wolfpack. Shownare plots of (two minus) average-wolves-per-capture (Lone-wolf capture rate) as a function of rteam (Group
Benefit). For both Gathering and Wolfpack we vary the following factors: temporal discount (left), batch size(centre), and network size (right). Note that the effects of discount factor and batch size on the tendency todefect point in the same direction for Gathering and Wolfpack, network size has the opposite effect (see text
for discussion.)
5. The complexity of learning how to implement effective cooperation and defection policies may not be
equal. One or the other might be significantly easierto learn—solely due to implementation complexity—
in a manner that cannot be accounted for by adjustingoutcome values in an MGSD model.
Our general method of tracking social behavior metrics
in addition to reward while manipulating parameters of thelearning environment is widely applicable. One could use
these techniques to simulate the effects of external interventions on social equilibria in cases where the sequential
structure of cooperation and defection are important. Notice that several of the examples in Schelling’s seminal book
Micromotives and Macrobehavior [51] can be seen as temporally extended social dilemmas for which policies have beenlearned over the course of repeated interaction, including
the famous opening example of lecture hall seating behavior. It is also possible to define SSDs that model the extraction of renewable vs non-renewable resources and track thesustainability of the emergent social behaviors while taking
into account the varying difficulties of learning sustainable(cooperating) vs. non-sustainable (defecting) policies. Effects stemming from the need to learn implementations forstrategic decisions may be especially important for informed
policy-making concerning such real-world social dilemmas.

Acknowledgments
The authors would like to thank Chrisantha Fernando, Toby
Ord, and Peter Sunehag for fruitful discussions in the leadup to this work, and Charles Beattie, Denis Teplyashin, andStig Petersen for software engineering support.

REFERENCES[1] Anatol Rapoport. Prisoner’s dilemma–recollections
and observations. In Game Theory as a Theory of a
Conflict Resolution, pages 17–34. Springer, 1974.
[2] Paul AM Van Lange, Jeff Joireman, Craig D Parks,
and Eric Van Dijk. The psychology of social dilemmas:
A review. Organizational Behavior and Human
Decision Processes, 120(2):125–141, 2013.
[3] Michael W Macy and Andreas Flache. Learning
dynamics in social dilemmas. Proceedings of the
National Academy of Sciences, 99(suppl 3):7229–7236,
2002.
[4] Robert L. Trivers. The evolution of reciprocal
altruism. Quarterly Review of Biology, pages 35–57,
1971.
[5] Robert Axelrod. The Evolution of Cooperation. Basic
Books, 1984.
[6] Martin A Nowak and Karl Sigmund. Tit for tat inheterogeneous populations. Nature,355(6357):250–253, 1992.
[7] Martin Nowak, Karl Sigmund, et al. A strategy of
win-stay, lose-shift that outperforms tit-for-tat in theprisoner’s dilemma game. Nature, 364(6432):56–58,
1993.
[8] Martin A Nowak and Karl Sigmund. Evolution ofindirect reciprocity by image scoring. Nature,393(6685):573–577, 1998.
[9] Robert Axelrod. An evolutionary approach to norms.
American political science review, 80(04):1095–1111,
1986.

[10] Samhar Mahmoud, Simon Miles, and Michael Luck.
Cooperation emergence under resource-constrained
peer punishment. In Proceedings of the 2016
International Conference on Autonomous Agents &Multiagent Systems, pages 900–908. International
Foundation for Autonomous Agents and Multiagent
Systems, 2016.
[11] T.W. Sandholm and R.H. Crites. Multiagent
reinforcement learning in the iterated prisoner’s
dilemma. Biosystems, 37(1–2):147–166, 1996.
[12] Enrique Munoz de Cote, Alessandro Lazaric, andMarcello Restelli. Learning to cooperate inmulti-agent social dilemmas. In Proceedings of theFifth International Joint Conference on Autonomous
Agents and Multiagent Systems (AAMAS), 2006.
[13] M. Wunder, M. Littman, and M. Babes. Classes ofmultiagent Q-learning dynamics with greedy
exploration. In Proceedings of the 27th International
Conference on Machine Learning, 2010.
[14] Erik Zawadzki, Asher Lipson, and Kevin
Leyton-Brown. Empirically evaluating multiagent
learning algorithms. CoRR, abs/1401.8074, 2014.
[15] Daan Bloembergen, Karl Tuyls, Daniel Hennes, andMichael Kaisers. Evolutionary dynamics ofmulti-agent learning: A survey. Journal of Artificial
Intelligence Research, 53:659–697, 2015.
[16] Martin A Nowak and Robert M May. Evolutionary
games and spatial chaos. Nature, 359(6398):826–829,
1992.
[17] Chao Yu, Minjie Zhang, Fenghui Ren, and Guozhen
Tan. Emotional multiagent reinforcement learning in
spatial social dilemmas. IEEE Transactions on Neural
Networks and Learning Systems, 26(12):3083–3096,
2015.
[18] Hisashi Ohtsuki, Christoph Hauert, Erez Lieberman,
and Martin A Nowak. A simple rule for the evolutionof cooperation on graphs and social networks. Nature,441(7092):502–505, 2006.
[19] Francisco C Santos and Jorge M Pacheco. A new routeto the evolution of cooperation. Journal of
Evolutionary Biology, 19(3):726–733, 2006.
[20] William E Walsh, Rajarshi Das, Gerald Tesauro, andJeffrey O Kephart. Analyzing complex strategicinteractions in multi-agent systems. In AAAI-02
Workshop on Game-Theoretic and Decision-Theoretic
Agents, pages 109–118, 2002.
[21] Michael Wellman. Methods for empiricalgame-theoretic analysis (extended abstract). In
Proceedings of the National Conference on Artificial
Intelligence (AAAI), pages 1552–1555, 2006.
[22] M. L. Littman. Markov games as a framework for
multi-agent reinforcement learning. In Proceedings ofthe 11th International Conference on Machine
Learning (ICML), pages 157–163, 1994.
[23] Ann Nowé, Peter Vrancx, and Yann-Michaël De
Hauwere. Game theory and multiagent reinforcement
learning. In Marco Wiering and Martijn van Otterlo,
editors, Reinforcement Learning: State-of-the-Art,
chapter 14. Springer, 2012.
[24] Max Kleiman-Weiner, M K Ho, J L Austerweil,
Michael L Littman, and Josh B Tenenbaum.
Coordinate to cooperate or compete: abstract goals

and joint intentions in social interaction. In
Proceedings of the 38th Annual Conference of the
Cognitive Science Society, 2016.
[25] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu,
J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller,
A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie,
A. Sadik, I. Antonoglou, H. King, D. Kumaran,
D. Wierstra, S. Legg, and D. Hassabis. Human-level
control through deep reinforcement learning. Nature,518(7540):529–533, 2015.
[26] Y. Shoham, R. Powers, and T. Grenager. If
multi-agent learning is the answer, what is thequestion? Artificial Intelligence, 171(7):365–377, 2007.
[27] M. G. Lagoudakis and R. Parr. Value function
approximation in zero-sum Markov games. In
Proceedings of the 18th Conference on Uncertainty in
Artificial Intelligence (UAI), pages 283–292, 2002.
[28] J. Pérolat, B. Scherrer, B. Piot, and O. Pietquin.
Approximate dynamic programming for two-player
zero-sum Markov games. In Proceedings of theInternational Conference on Machine Learning(ICML), 2015.
[29] J. Pérolat, B. Piot, M. Geist, B. Scherrer, and
O. Pietquin. Softened approximate policy iteration for
Markov games. In Proceedings of the International
Conference on Machine Learning (ICML), 2016.
[30] Branislav Bošanský, Viliam Lisý, Marc Lanctot, Jiřı́Čermák, and Mark H.M. Winands. Algorithms forcomputing strategies in two-player simultaneous move
games. Artificial Intelligence, 237:1–40, 2016.
[31] M. Zinkevich, A. Greenwald, and M. Littman. Cyclic
equilibria in Markov games. In Neural Information
Processing Systems, 2006.
[32] J. Hu and M. P. Wellman. Multiagent reinforcement
learning: Theoretical framework and an algorithm. In
Proceedings of the 15th International Conference on
Machine Learning (ICML), pages 242–250, 1998.
[33] A. Greenwald and K. Hall. Correlated-Q learning. In
Proceedings of the 20th International Conference on
Machine Learning (ICML), pages 242–249, 2003.
[34] Michael Littman. Friend-or-foe Q-learning in
general-sum games. In Proceedings of the EighteenthInternational Conference on Machine Learning, pages
322–328, 2001.
[35] J. Pérolat, B. Piot, B. Scherrer, and O. Pietquin. On
the use of non-stationary strategies for solving
two-player zero-sum Markov games. In Proceedings ofthe 19th International Conference on Artificial
Intelligence and Statistics, 2016.
[36] Piotr J Gmytrasiewicz and Prashant Doshi. A
framework for sequential planning in multi-agent
settings. Journal of Artificial Intelligence Research,
24:49–79, 2005.
[37] Pradeep Varakantham, Jun-young Kwak, Matthew E
Taylor, Janusz Marecki, Paul Scerri, and Milind
Tambe. Exploiting coordination locales in distributed
POMDPs via social model shaping. In Proceedings ofthe 19th International Conference on AutomatedPlanning and Scheduling, ICAPS, 2009.
[38] Raphen Becker, Shlomo Zilberstein, Victor Lesser, andClaudia V Goldman. Solving transition independent
decentralized Markov decision processes. Journal ofArtificial Intelligence Research, 22:423–455, 2004.
[39] Guillaume J. Laurent, Laëtitia Matignon, and N. Le
Fort-Piat. The world of independent learners is not
Markovian. Int. J. Know.-Based Intell. Eng. Syst.,
15(1):55–64, 2011.
[40] David Silver, Aja Huang, Chris J. Maddison, Arthur
Guez, Laurent Sifre, George van den Driessche, Julian
Schrittwieser, Ioannis Antonoglou, Veda
Panneershelvam, Marc Lanctot, Sander Dieleman,
Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya
Sutskever, Timothy Lillicrap, Madeleine Leach, Koray
Kavukcuoglu, Thore Graepel, and Demis Hassabis.
Mastering the game of Go with deep neural networks
and tree search. Nature, 529:484–489, 2016.
[41] W. Schultz, P. Dayan, and P.R. Montague. A neuralsubstrate of prediction and reward. Science,
275(5306):1593–1599, 1997.
[42] Y. Niv. Reinforcement learning in the brain. The
Journal of Mathematical Psychology, 53(3):139–154,
2009.
[43] Richard S. Sutton and Andrew G. Barto. Introduction
to Reinforcement Learning. MIT Press, 1998.
[44] Michael L Littman. Reinforcement learning improves
behaviour from evaluative feedback. Nature,521(7553):445–451, 2015.
[45] Sascha Lange, Thomas Gabel, and Martin Riedmiller.
Batch reinforcement learning. In Reinforcement
learning, pages 45–73. Springer, 2012.
[46] Katherine V Kortenkamp and Colleen F Moore. Time,uncertainty, and individual differences in decisions tocooperate in resource dilemmas. Personality andSocial Psychology Bulletin, 32(5):603–615, 2006.
[47] Craig D Parks and Lorne G Hulbert. High and low
trusters’ responses to fear in a payoff matrix. Journalof Conflict Resolution, 39(4):718–730, 1995.
[48] Hui Bing Tan and Joseph P Forgas. When happinessmakes us selfish, but sadness makes us fair: Affective
influences on interpersonal strategies in the dictator
game. Journal of Experimental Social Psychology,
46(3):571–576, 2010.
[49] Joseph L. Austerweil, Stephen Brawner, Amy
Greenwald, Elizabeth Hilliard, Mark Ho, Michael L.
Littman, James MacGlashan, and Carl Trimbach. How
other-regarding preferences can promote cooperationin non-zero-sum grid games. In Proceedings of the
AAAI Symposium on Challenges and Opportunities inMultiagent Learning for the Real World, 2016.
[50] Nathaniel D Daw, Yael Niv, and Peter Dayan.
Uncertainty-based competition between prefrontal anddorsolateral striatal systems for behavioral control.
Nature neuroscience, 8(12):1704–1711, 2005.
[51] Thomas C. Schelling. Micromotives andmacrobehavior. WW Norton & Company, 1978 Rev.
2006.