A simple learning strategy which
realizes robust cooperation better thanPavlov in Iterated Prisoners’ Dilemma
Joe Yuichiro Wakano
Norio Yamamura(Center for Ecological Research, Kyoto Univ.)1

Prisoner’s Dilemma (PD)

CDC

30

D

5

1

C:cooperation
D:defection

Defection is always the best strategy in a single round PD game.

2

Pavlov

When the game is repeated (Iterated Prisoner’s Dilemma or IPD),
adaptive strategy is not clear.
Pavlov is proposed as a leading strategy in IPD(Nowak & Sigmund 1993)
Pavlov :=Probability ofplaying C after( 1,0,0,1 )CC CD DC DD

3

Performance of Classic Strategies
TFT (1,0,1,0) ends up very poor when noise is introduced.
Pavlov is invaded by All-D but
Pavlov like strategy (1-e,0,0,1-e) is not.
(Nowak & Sigmund 1993)

Is Pavlov like strategy an ESS in a strategy set of (p1,p2,p3,p4) ?

4Performance of Classic Strategies
Payoff for (p1,p2,p3,p4) against (q1,q2,q3,q4) can be derived
analytically (eigen vector in Markov process).
214 strategies are matched each other and payoff is calculated.
By investigating the payoff matrix, we obtain ...

Pavlov like strategy (1-e,0,0,1-e) is invaded by (1,0,0,1).
Only two ESSs found: All-D and GRIM (1,0,0,0)
No strategy of type (p1,p2,p3,p4) can establish stable mutualcooperation.
5

Introduction of Learning Players
Reinforcement learning:“Repeat when rewarded, change when punished” or“Win-Stay, Lose-Shift”
Simple and intuitively understandable rule.
Pavlov can be considered as the most simple player adopting
reinforcement learning.
However, Pavlov considers the previous move only.
We will intoduce a learning player who considers pastexperiences (generalized Pavlov ?).
6

Aspiration Level
In order to adopt reinforcement learning, standard or
aspiration level of evaluation must be defined.
Payoff

Evaluation

T=5
good
R=3
P=1
S=0

aspiration level s
badTo establish stable mutual cooperation, 1<s<3 is necessary.
7Model of Learning Players
Aspiration level s is genetically fixed.
Internal state h is changed during reptition of PD.
C is played when current internal state h>0, otherwise D.

∆h = a ⋅ sgn( f − s ) ⋅ sgn( h )1( x ≥ 0)sgn( x) ≡ 
− 1( x < 0)
Examples:If C is played and the resulting score f is larger than s, cooperation isaffirmatively learned. That is, the player increases h to become morecooperative.
If C is played and the resulting score f is smaller than s, cooperation isnegatively learned. That is, the player decreases h to become lesscooperative.
If D is played and the resulting score f is larger than s, defection isaffirmatively learned, leading decrease in h.
8Model of Learning Players
Each IPD consists of 10,000 PD games.
Error or noise is introduced at probability e.
When error happens, the opposite action expected from h value
is played.
Internal state h is reset to a / 2 every time the opponent
changes, thus the learner always plays D at the first round.
The learner can learn to exploit All-C.
Internal state h can be considered as ‘faith in cooperation’.
Such faith is altered by past experience.
Payoffs of both players in IPD is determined only by aspirationlevels.
9Digital Learner∆h = 2 ⋅ sgn( f − s ) ⋅ sgn( h )1( x ≥ 0)sgn( x) ≡ 
− 1( x < 0)

Only 5 independent variants;
D L ( s≤ 0 ), D L ( 0 < s≤ 1 ), D L ( 1 < s≤ 3 ), D L ( 3 < s≤ 5 ), D L ( s>5)

53
1010

Example of Digital Learner’s behavior

Table Comparison of digital learner (1<s≤3, a =2) and Pavlov
strategy
opponent
actual realization of game (h)DL(1<s≤3)

Pavlov

All-D
All-C
Pavlov
TFTDL(1<s≤3)
All-D
All-C
Pavlov
TFTDL(1<s≤3)

averagepayoffDD(‑1), CD(1), DD(‑1), CD(1), DD(‑1),... 0.5
DC(‑1), DC(‑3), DC(‑5), DC(‑7), DC(‑9),... 5DD(‑1), CC(1), CC(3), CC(5), CC(7),... 3
DC(‑1), DD(‑3), DD(‑1), CD(1), DC(‑1),... 1.75
DD(‑1), CC(1), CC(3), CC(5), CC(7),... 3
0.5
DD, CD, DD, CD, DD, ...
5
DC, DC, DC, DC, DC, ...
3
DD, CC, CC, CC, CC, ...
2
DC, DD, CD, DC, DD, ...
3
DD, CC, CC, CC, CC, ...

11

ESS among 5 variants of Digital Learner
Table Results of matches among digital learners.
playeropponent(mutant) s≤00<s ≤11<s≤3(a) 1% error s≤01.030049 1.030053 2.965461
0<s≤11.030048 1.030052 2.985288
1<s≤30.535146 0.535152 2.984959
3<s≤50.539876 0.53988
2.943325s>50.535053 0.545318 3.954128(b)10% error s≤01.290936 1.290994 2.851567
0<s≤11.290922 1.290977 2.851499
1<s≤30.848479 0.848549 2.865511
3<s≤50.888843 0.88891
2.482726s>50.850024 0.98887
3.526731(wild type)3<s≤5
2.965461
2.965454
0.584596
1.738342
1.258617
2.709865
2.709804
1.243602
1.910963
1.601163s>52.985005
2.974166
1.519351
2.502725
2.010029
2.849876
2.788106
1.848385
2.405803
2.090827

cooperative variant

12

ESS among 5 variants of Digital Learner
Table Results of matches among digital learners.
playeropponent(mutant) s≤00<s ≤11<s≤3(a) 1% error s≤01.030049 1.030053 2.965461
0<s≤11.030048 1.030052 2.985288
1<s≤3
0.535146 0.535152 2.984959
3<s≤50.539876 0.53988
2.943325s>50.535053 0.545318 3.954128(b)10% error s≤01.290936 1.290994 2.851567
0<s≤11.290922 1.290977 2.851499
1<s≤30.848479 0.848549 2.865511
3<s≤50.888843 0.88891
2.482726s>50.850024 0.98887
3.526731

ESS(wild type)3<s≤5
2.965461
2.965454
0.584596
1.738342
1.258617
2.709865
2.709804
1.243602
1.910963
1.601163s>52.985005
2.974166
1.519351
2.502725
2.010029
2.849876
2.788106
1.848385
2.405803
2.090827

cooperative variant

Cooperative variant DL(1<s<3) is not an ESS.
DL(s<0) is almost same as All-D, thus defection spreads
13Analog Learner
The impact on learning process may depend on the payoff value(instead of a constant as in DL model).
Analog evaluation model is developed.

∆h = 2 ⋅ ( f − s ) ⋅ sgn( h)Small difference in aspiration level s produces different learningprocess.
We used 56 different s values (s=-0.1, 0, 0.1, 0.2, …,5.4)
in computer simulations.

14

Can Analog Learners invade classic strategies ?

Analog Learner for s=1.6,…,3.0 invades All-C, All-D, TFT
and Pavlov.
15

Can Analog Learners invade classic strategies ?

Analog Learner for s=1.6,…,3.0 invades All-C, All-D, TFT
and Pavlov.
16

Can classic strategies invade Analog Learners ?

Analog Learner for s=2.6,…,3.0 is stable against invasion ofAll-C, All-D, TFT and Pavlov.
17

Can classic strategies invade Analog Learners ?

Analog Learner for s=2.7,…,2.8 is stable against invasion ofAll-C, All-D, TFT and Pavlov.
18

Summary of classic strategies vs. Analog Learner
Though Analog Learner cannot invade All-D population,
cooperative variants of Analog Learner do very wellagainst classic strategies.

1% error:
Analog Learner for s=2.6,…,3.0 invades and is stable against
All-C, TFT, Pavlov (and All-D).
10% error:
Analog Learner for s=2.7,…,2.8 invades and is stable against
All-C, TFT, Pavlov (and All-D).
19

Evolutionary dynamics of aspiration levelF(s,s*):= payoff value of AL(s=s) when matched against AL(s=s*)
F(s,s*) is obtained by compter simulation. By calculating many
sets of (s,s*), we obtain the payoff matrix (56 x 56 matrix).

20

Evolutionary dynamics of aspiration level

21Evolutionary dynamics of aspiration level
From this payoff matrix, Pairwise Invasibility Plot (PIP) is drawn.
By surveying PIP, it becomes clear whether evolutionarily stablestrategy (ESS) exists or not.

22

ESS among Analog LearnersPairwise Invasibility Plot

23

ESS among Analog Learners

Pairwise Invasibility Plot24

Analog Learner can establish robust cooperation
Under both 1% and 10% error rate, Analog Learner withaspiration level around 2.7 can invade All-C, TFT or Pavlov
populations and establish very robust mutual cooperation.
Such population is more cooperative than Pavlov population.
F(2.7,2.7):
Average score ofAL(s=2.7) population

1% 2.9891
10% 2.8491

Average scores of populations for infinitely
iterated Prisoners’ DilemmaerroAll-CPavlovTFTAll-Dr(1,0,1,0) (0,0,0,0)
rate (1,1,1,1) (1,0,0,1)
0%
3.000
3.000
3.000
1.000
1%
2.990
2.951
2.010
1.030
5%
2.948
2.777
2.048
1.148
10%
2.890
2.602
2.090
1.290
20%
2.760
2.376
2.160
1.560

Due to strong faith in cooperation, it allows its partner’s
defection played by error without punishment.

25

Difference between Digital and Analog Learner
When matched against All-D (or DL(s<1) or AL(s<1));
DL(1<s<3)
AL(s=2)-1
DDDD-11CDCD
1-1DDDD-31CDDD-11DD
CD
13 (Digital Learner)
All-D strategy’s payoff =2.3 (Analog Learner)<Average payoff of AL(s=2) population (=3)
Quantified evaluation ability is essential to avoid being exploitedby always defecting strategies.
26

Future problems
Memory decay;
more recent result might affect internal state more strongly
Analog Learner with non-linear evaluation

27