Emergence of Cooperation in Complex Agent Networks
Based on Expectation of Cooperation(Extended Abstract)∗Ryosuke Shibusawa, Tomoaki Otsuka, and Toshiharu Sugawara
Deptartment of Computer Science and Communications Engineering
Waseda University, Tokyo 169-8555, Japan{r.shibusawa, t.otsuka}@isl.cs.waseda.ac.jp, sugawara@waseda.jp
ABSTRACT

equilibria are not appropriate from social viewpoint [2, 3, 1].
However, these studies did not succeed in the emergence ofcooperation in social dilemma in some agent networks or it
is not obvious to implement in the actual systems.
The contribution of this paper is the proposal of the simple behavioral strategy called expectation of cooperation withwhich (the norm of) cooperation in the prisoner’s dilemma(PD) games emerges under a certain condition. We then experimentally show that the expectation of cooperation strategy fosters cooperation in the whole networks, although it
is simple and easy to implement.

This paper proposes a behavioral strategy called expectation of cooperation strategy with which cooperation in theprisoner’s dilemma game emerges in agent networks by incorporating Q-learning. The proposed strategy is simple andeasy to implement but nevertheless can evolve and maintaincooperation in all agent networks under certain conditions.
We conducted a number of experiments to clarify these conditions, and the results indicate that cooperation emerged.

Categories and Subject Descriptors
I.2.11 [Artificial Intelligence]: Distributed Artificial Intelligence—Multiagent systems

General Terms

2.

PROPOSED METHOD

2.1

PD Games with Ensemble Strategy

For a given agent network G = (A, E), we assume thatall pairs of agents in E play the PD game once in a single round in random order. Agent i decides its strategy by
the ensemble strategy decision with Q-value or simply theensemble decision with ε-greedy method for all neighbors.
More specifically, i has the Q-value, Qi (s, j), for the strategy s ∈ Str and neighbor agent j ∈ Ni at the t-th round,and it is updated byExperimentation

Keywords
Norm, Complex networks, prisoner’s dilemma

1. INTRODUCTION
Humans are basically self-interested and individually rational but often pursue social benefits on the basis of, for example, altruism and indirect reciprocity. This kind of behavior is selected to avoid/resolve social dilemmas such as conflicts between (groups of) humans and the existence of freeriders. Agents’ decisions made only from the self-interested
and local viewpoints often result in non-cooperative behavior resulting in conflicts that may result in loss for bothsides. To avoid such conflicts, agents should take into account not only local benefits but also social benefits; suchsocially cooperative behavior may be the non-best choicefrom a short-term and local viewpoint but will bring better
results eventually in the long term.
A number of studies have been conducted, and sociallycooperative behavior as a norm has emerged in which Nash
∗This work is supported by KAKENHI (25280087).

Qit (s, j) = (1 − αi ) · Qit−1 (s, j) + αi · rji (t − 1),
where rji (t − 1) is the payoﬀ received after the latest PD
game with j at round t − 1, and αi is the parameter for thelearning rate of agent i.
At the beginning of the t-th round, agent i identifies its
strategy, si (t), so that the following condition is satisfied.
si (t) = arg max pi (s),(1)s∈Strwhere pi (s) is the preference function for ensemble decision.
In our experiments, we define it as a plurality, i.e.,∑p(s) =δ(s, sij (t − 1))(2)j∈Nisij (t − 1) = arg max Qit−1 (s, j),(3)

Appears in: Proceedings of the 15th International Conferences∈Str

on Autonomous Agents and Multiagent Systems (AAMAS 2016),
J. Thangarajah, K. Tuyls, C. Jonker, S. Marsella (eds.),
May 9–13, 2016, Singapore.
c 2016, International Foundation for Autonomous Agents andCopyright ⃝Multiagent Systems (www.ifaamas.org). All rights reserved.

where δ(s, s′ ) = 1 if s = s′ ; otherwise it is zero. Then,i selects strategy si (t) with probability 1 − ε and selects it
randomly from Str with probability ε. We call strategy si (t)as the preferred strategy of i at the t-th round.

1333

Complete graph

Number of cooperation

300
250

L=3, 4, 5200

L=0

L=1

L=2

L=3

L=4

L=5

the ε-greedy strategy is set to 0.05. The number of agents|A| is three hundred. The data described below is the meanvalues of 20 independent trials.
Figure 1 plots the ratios of agents that select cooperation, C, per round. Note that the initial values of Qi0 (s, j)for ∀i ∈ A and ∀j ∈ Ni is set to 0. We can see thatwhen L ≤ 2, cooperation could not emerge in the societyof agents with the expectation of cooperation strategy but
did emerge (thus the preferred strategy, si (t), converged toC for ∀i ∈ A) when L ≥ 3. Note that we also conducted
the same experiment for the agents with only expectation ofcooperation strategy without the ensemble strategy decision
with Q-values, so agent i selects D with probability 1 − εand C or D randomly with probability ε when li = 0. In
this case, no cooperation emerged even when L = 5.
The ratios of cooperation seemed to depend on the ratiosof cooperation in the first round (initial strategies) due tothe characteristics of expectation of cooperation behavioral
strategy since the joint action (C, C) by a pair of agents
forced them to cooperate individually for the next L rounds.
In the experiment described above, Q(C) = Q(D) = 0, so
fifty percent of the agents preferred cooperation (si (0) =C), and the other agents preferred defection (si (0) = D)on average. Thus, we set the Q-values, Q(C) = Q(D) =0, like in the previous experiment, but we assumed thatagents selected C as the initial preferred strategy, si (0), withprobability R (0 ≤ R ≤ 0.5, so the other agents selected Dwith probability 1 − R).
Figure 2 plotted the ratios of cooperation at the 5000thround when R was varied. The ratios of cooperation sharply
increase to 100% with increasing initial cooperation rate, R.
For example, the curve for L = 3 indicated that all agents
selected C after all when R = 0.45, but approximately half of
the agents and none of the agents selected C when R = 0.40
and R = 0.35, respectively.
When the initial cooperation ratio was small, the experiment started from the situation in which many agents preferred D. Furthermore, since agents were tightly connectedto each other in the complete graph, relatively larger cooperation persistence, L, was necessary to overturn the situation
where D was the majority strategy, but the overturn wasimmediate if R reached a suﬃciently large number.

150
10050001000

2000
3000
Round

40005000

Figure 1: Ratios of cooperation per round.
Complete graph
L=1Ratio of cooperation (%)

100
90
80
70
60
50
40
30
20
100

L=2

L=3

L=2.5
L=3
L=3.5
L=400.1

0.2

0.3

Initial cooperation ratio (R)

0.4

0.5

Figure 2: Ratios of cooperation.

2.2 Expectation of Cooperation Strategy
Agents with the proposed behavioral strategy, called theexpectation of cooperation strategy, are assumed to knowthat social cooperative behavior is better than defection, so
they expect (hope for) it when interacting with their neighbors, but they also know that it is fruitless if other local
agents do not cooperate. Furthermore, agents can observe
others’ strategies only when they interact. We introduce
the positive integer, L, which represents cooperation persistence. Agent i also has the parameter li (≥ 0) to express theremaining term for persisting cooperation, i.e., when li = 0,i selects the preferred strategy, but while li > 0, i causes cooperation persistence in the hope of cooperation in the local
environment. The initial value of li is set to zero.
If agents i and j mutually select cooperation, (C, C), occasionally, they will individually set li and lj to L and enter
the term for persisting cooperation in the hope of (local)
emergence of cooperation. Thus, i and j persist cooperation
in at least the next L PD games (not rounds) with theirneighbors, and li is decremented by one after each game.
However, if i encounters joint (C, C) again, li is set to L andthe term of persisting cooperation is prolonged.
It is obvious that if the cooperation persistence, L, is large,agents continue to select C, and if L = 0, it is the PD gameswith normal Q-learning, so all agents tend to select D, whichis the Nash equilibrium. We are interested in the smallest
value of L that leads to (almost) total cooperation.

4.

We proposed the strategy called expectation of cooperation in which agents continue to cooperate for L > 0 times
after mutual cooperation. We also conducted other types ofnetworks, such BA and CNN, and if agents select C or D
randomly, L = 3 seems the minimal number for this strategy
from our experiments.

REFERENCES[1] N. Masuda. Evolution of cooperation driven by zealots.
Nature Scientific Reports, 2(646), 2012.
[2] K. Moriyama, S. Kurihara, and M. Numao. Evolving
subjective utilities: Prisoner’s dilemma game examples.
In Proc. of AAMAS 2011 - Vol. 1, pages 233–240, 2011.
[3] D.-M. Shi, H.-X. Yang, M.-B. Hu, W.-B. Du, B.-H.
Wang, and X.-B. Cao. Preferential Selection Promotes
Cooperation in a Spatial Public Goods Game. Physica
A: Statistical Mechanics and its Applications,388(21):4646 – 4650, 2009.

3. EXPERIMENTAL RESULT
We evaluated our strategy using the agent network of compete graph. The payoﬀ matrix for PD game is defined asCDC3, 35, 0

CONCLUSION

D0, 51, 1

The learning rate α (= αi for ∀i ∈ A) is set to 0.1, and ε for1334