I have a solution!

Finding successful strategies
for social dilemma using K
computer
Yohsuke Murase, Seung Ki Baek
RIKEN Center for Computational Science, JapanPukyong National University, Korea

iterated Prisoner’s Dilemma
player B
cooperation

defection

cooperation

(3,3)

(0,5)

defection

(5,0)

(1,1)

player A

implementation error occurs with probability

long-term payoffe<latexit sha1_base64="fSe004YKF6vMcUZEj33avSo9wuc=">AAACZHichVHLSsNAFD2Nr1ofrYogCFIsFVflRgTFVdGNS9taW1CRJE5raJqEJC3U4g/oVnHhSkFE/Aw3/oALf0AQlxXcuPA2DYgW9Q4zc+bMPXfOzKi2obse0VNI6unt6x8ID0aGhkdGo7Gx8S3XqjmayGuWYTlFVXGFoZsi7+meIYq2I5SqaoiCWllr7xfqwnF1y9z0GrbYrSplUy/pmuIxlRF7sQSlyI94N5ADkEAQG1bsBjvYhwUNNVQhYMJjbECBy20bMgg2c7toMucw0v19gSNEWFvjLMEZCrMVHsu82g5Yk9ftmq6v1vgUg7vDyjiS9Ei31KIHuqMX+vi1VtOv0fbS4FntaIW9Fz2eyr3/q6ry7OHgS/WnZw8lLPtedfZu+0z7FlpHXz88b+VWssnmHF3RK/u/pCe65xuY9TftOiOyF4jwB8g/n7sbbC2kZErJmcVEejX4ijCmMYt5fu8lpLGODeT5XIETnOIs9CwNSxPSZCdVCgWaCXwLaeYT0EyJ5Q==</latexit><latexit

TX11(t)fi ⌘ lim lim
Fie!0 T !1 T
t=0<latexit sha1_base64="CfD1qyKg0ws1VkAs+U8zHbmbHOk=">AAACtXichVFNaxRBEH0Zv+IazUYvgpfBJSEeXGpCIEEQQgTxuEl2k0BmM8xMepIm8+VMz8JmmD/gH/DgSUFC8O4f8OIfyCGQq4HgMYIXD9bMDogGtZrurnpVr/p1txP7MlVEJ2PalavXrt8Yv9m4NXH7zmRz6u56GmWJK3pu5EfJpmOnwpeh6CmpfLEZJ8IOHF9sOPvPyvzGQCSpjMKuGsaiH9i7ofSkayuGrGbHs6RuipeZHOimLwMrF6aKdCrqqFtGpgw9NWTIS2w3N4q8W5hpxln1lIrtvPvYKJ5bcjufVY8Kq9miNlWmX3aM2mmhtk7UPISJHURwkSGAQAjFvg8bKY8tGCDEjPWRM5awJ6u8QIEGczOuElxhM7rP6y5HWzUaclz2TCu2y6f4PBNm6pimYzqiC/pMH+icfvy1V171KLUMeXdGXBFbk6/ur33/LyvgXWHvF+ufmhU8LFZaJWuPK6S8hTviDw5eX6w9WZ3OZ+gdfWX9b+mEPvENwsE39/2KWH2DBn+A8edzX3bW59oGtY2V+dbScv0V43iAh5jl917AEl6ggx6f+xGn+IIzbUHrazuaNyrVxmrOPfxmWvQTVAapmg==</latexit>

Strategies for IPD game
Tit-For-Tat (TFT)

Win-Stay-Lose-Shift (WSLS)

It is guaranteed that your payoff
is no less than the co-players'.

Cooperation is tolerant against
an error.

Cooperation is fragile against anerror.

Repeatedly exploited againstAllD.

c c d c d cc d c dc c c d c dd d d dOther strategies (TF2T, ZD strategies, generous TFT…)
have positives and negatives.

partners or rivals?
Eﬃciency

eﬃcient (partner)⌦defensible (rivals)

Defensibility⌦⌦cooperation⌦generous TFT
AllCTrigger

WSLS
TF2T
generous ZD

more cooperations

AllDTFT
extortionate ZD

successful???

more defections

It would be great if a single strategy satisfies these advantages
simultaneously.
=> Nash equilibrium with a guarantee that you'll never lose.

A solution for Prisoner’s Dilemma

Yi et al., J. Theor. Biol. (2017)

comprehensive search in Memory-2 strategies

4 out of 65,536 strategies satisfies the conditions

TFT-ATFT
It is indeed possible to realize cooperation
without exposing themselves to the risk of being exploited.

Murase & Baek, J.Theor.Biol. (2018)

What about n-person
public-goods game?
n=3

the number of defecting co-players

TFT-ATFT does not work for n=3.
Does a solution exist for n=3?

Enumeration using K-computer22<latexit sha1_base64="HvQwK2P41zQrPI1GWAC98AoULqE=">AAACjXichVG7SgNBFD2urxgfidoINmJQrMIkKoqIiBZa+oqK8cHuOuqQfbE7CeiSH7AWLERBwUL8AD/Axh+wyCeIZQQbC+9uFkSDendm58yZe+7M4WqOITzJWKVBaWxqbmmNtcXbOzq7EsnunnXPLro6z+m2YbubmupxQ1g8J4U0+KbjctXUDL6hFeaD840Sdz1hW2vy2OE7pnpoiQOhq5KoreyuT8Myy+W9ZIqlWRgD9SATgRSiWLKTD9jGPmzoKMIEhwVJ2IAKj748MmBwiNuBT5xLSITnHGXESVukLE4ZKrEF+h/SLh+xFu2Dml6o1ukWg6ZLygEMsWd2x6rsid2zF/bxay0/rBG85ZhWrablzl7itG/1/V+VSavE0ZfqD4VG2X97kjjAZOhFkDcnZAKXeq1+6eS8ujq1MuQPsxv2Sv6uWYU9kkOr9KbfLvOVC8SpQZmf7agH69l0ZjSdXR5Lzc5FrYqhH4MYoX5MYBaLWEKO7rVwhktcKQllXJlWZmqpSkOk6cW3UBY+AXtVk8A=</latexit>

nm

n=3, m=1 : 256
n=3, m=2 : 1,099,511,627,776 (2^40)

Enumeration of strategies
1,099,511,627,776# of m=2 strategies

805,306,368

Defensibility against AllD
Defensibility

Defensibility

Eﬃciency

Efficiency

3,483,008⌦⌦⌦

cooperation⌦0Impossibility for m=2
memory-2 strategies
AONAllC

TFT

AllD

TF2T

no successful strategy exists in memory-2 strategy space.
0 / 1,099,511,627,776
No solution for n=3 game? or The solution exists when m>2?

Memory-3 strategies

2<latexit sha1_base64="KhAflYuw8dXnZ1exLY4273vfmLE=">AAACinichVG7SgNBFD1Z3/EVtRFsxBCxCrOrYNRG1MIyJiYRfLG7TnRwX+xuArr4A3ZWglYKFuIH+AE2/oCFnyCWCjYW3t0siAbjHWbmzJl77szhao4hPJ+x54TU1t7R2dXdk+zt6x8YTA0Nlz275uq8pNuG7W5oqscNYfGSL3yDbzguV03N4BXtcDm8r9S56wnbWvePHL5tqvuWqApd9YmqKDuBksud7KbSLMuiGG8GcgzSiCNvp+6xhT3Y0FGDCQ4LPmEDKjwam5DB4BC3jYA4l5CI7jlOkCRtjbI4ZajEHtK6T6fNmLXoHNb0IrVOrxg0XVKOI8Oe2C17Y4/sjr2wzz9rBVGN8C9HtGsNLXd2B09Hix//qkzafRx8q1ooNMpu7clHFbnIiyBvTsSELvVG/frx+VtxvpAJJtk1eyV/V+yZPZBDq/6u36zxwiWS1CD5dzuaQVnJytNZZW0mvbgUt6obY5jAFPVjFotYRR6l6HdnuMCl1Ccp0py00EiVErFmBD9CWvkCRt2R4Q==</latexit>

288497323236409786642155382248146= 820840100456150797347717440463
976893159497012533375533056

comparable to the number of protons in the universe

Although direct enumeration is impossible,
we found there are at least 256 solutions!

Enumeration of strategies
1,099,511,627,776# of m=2 strategies

805,306,368

Defensibility against AllD
Defensibility

3,483,008⌦

Defensibility

Eﬃciency“Partial” Efficiency (pcooperation> 0)⌦⌦

cooperation

Distinguishability

Distinguishability

⌦>

⌦544

AllCAllC“Partially” Successful Strategies (PS2)256elevating m=2 PS2 to m=3 successful strategies
24_cddccc
48_ddcccc

37_dccdcd
10_ccdcdc

16_cdcccc

C0_cccccc
34_dcccdc

40_dcdccc
B

25_cddccd
B

58_dddcdc

CB12_ccddcc

4_cccdcc

46_dcdddc

22_cdcddc

1_cccccd

3_ccccdd

B&CB

60_ddddcc

43_dcdcdd

C

20_cdcdcc

44_dcddcc

11_ccdcdd
14_cccddc

38_dccddc

62_dddddc

41_dcdccd

35_dcccdd

61_ddddcd
29_cdddcd

23_cdcddd

17_cdcccd

63_dddddd

59_dddcdd

5_cccdcd

55_ddcddd

51_ddccdd

47_dcdddd

31_cddddd
50_ddccdc

53_ddcdcd

56_dddccc

26_cddcdc

15_ccdddd

<latexit sha1_base64="95WLehzbGYYlQYuq9vfp16ljsEs=">AAACnXichVHLSsNAFD2N7/po1U3BhcWiuCrT+CquRBFciLRqrWC1JHFag2kSk7SgoX6AP+DClaILEd36AW78ARf9BHFZwY0Lb9OAqKh3mJkzZ+65M4crm5pqO4zVAkJLa1t7R2dXsLunty8U7h/YsI2ypfCMYmiGtSlLNtdUnWcc1dH4pmlxqSRrPCvvLzTusxVu2aqhrzuHJt8uSUVdLaiK5BCVD0dyRX4QzRUsSXHFqemqK+64YjJZrebDMRZnXkR/goQPYvAjZYTvkcMuDCgoowQOHQ5hDRJsGltIgMEkbhsucRYh1bvnqCJI2jJlccqQiN2ntUinLZ/V6dyoaXtqhV7RaFqkjGKUPbFrVmeP7IY9s/dfa7lejcZfDmmXm1pu5kMnkbW3f1Ul2h3sfar+UMiU/bcnBwUkPS8qeTM9puFSadavHJ3W12ZXR90xdsFeyN85q7EHcqhXXpWrNF89Q5AalPjejp9gQ4wnJuJiejI2N++3qhNDGME49WMGc1hCChl69xiXuMWdMCwsCsvCSjNVCPiaQXwJIfsB8gyY+g==</latexit>

2562288

WSLS
AllC

TFT

AllD

TF2T
Eﬃciency⌦Defensibility⌦

cooperation⌦

efficient strategies

defensible strategies⌦

Successful strategies indeed exists when m=3.
Full cooperation is achieved
while keeping the defensibility and the distinguishability.

An example of successful strategies.

memory length and # of players
n=2 : TFT-ATFT (m=2)
n=3 : m=3 Successful Strategies...
for general n (>=3), we showm<latexit sha1_base64="En7TK770IIYn3eKi5faMAC8QzmU=">AAACa3ichVFNLwNRFD0dX1UfLd0IFo2mYtXcEQmxEjaWbSlNEJkZT006X2amTWj8AUsbi9qQiIifYeMPWPgJIlYkNhbuTCcRBHfy5p133j33nXef6hi65xM9xKSOzq7unnhvoq9/YDCZGhpe8+y6q4myZhu2W1EVTxi6Jcq+7hui4rhCMVVDrKu1pWB/vSFcT7etVf/AEVumUrX0XV1TfKYqZmazKvYz1nYqS3kKI/MTyBHIIoqCnbrCJnZgQ0MdJgQs+IwNKPD424AMgsPcFprMuYz0cF/gCAnW1jlLcIbCbI3/VV5tRKzF66CmF6o1PsXg4bIygxzd0zW90B3d0CO9/1qrGdYIvBzwrLa1wtlOHo+svP2rMnn2sfep+tOzj13MhV519u6ETHALra1vHJ6+rMyXcs1JuqAn9n9OD3TLN7Aar9plUZRaSPADyN/b/ROsTedlysvFmezCYvQUcYxhAlPc71ksYBkFlMM+n6CFs9izlJZGpfF2qhSLNGl8CSn3AX3EjHo=</latexit>

nmemory length

Murase & Baek, J.Theor.Biol. (2018)

(3,3)
(2,2)

# of players

must be satisfied.
There is a critical memory length above whicha fundamentally new class of strategies may exist.

Conclusions•A new class of Nash equilibrium strategies was found with the aidof the K computer.

•Well-computed strategies can solve social dilemma without
appealing to our moral.

Exploring a broader strategy space does make a difference.
public-goods game for n>3• perception error• multiple choice of actions• indirect reciprocity• network reciprocity•

References•••

Y. Murase & S.K. Baek, “Seven rules to avoid the tragedy of the commons”, J. Theor. Biol. 449 p94 (2018)
Y. Murase & S.K. Baek, “Automata representation of successful strategies for social dilemmas”, arXiv:1910.02634,
under review
Y. Murase & S.K. Baek, “Memory-three strategies that are partners as well as rivals”, in preparation