日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-C-10

ほぼ公的観測下の繰り返し囚人のジレンマにおける協力のダイナミクス
05000493

電気通信大学*五十嵐瞭平

IGARASHI Ryohei

電気通信大学岩崎敦

IWASAKI Atsushi

はじめに

1.

表 1: 囚人のジレンマ (g > 0，l > 0，および |g − l| < 1)

繰り返しゲームは，長期的関係にあるプレイヤ間の（暗黙の）協調を説明するためのモデル [4] であり，主に経済学分野で企業間の談合といった協調行動を分析するために発展してきた. 2 人がまったく見間違えない「完全」観測下では，常に裏切り（AllD）や一度でもa2 = C

a2 = D

a1 = C1, 1−l, 1 + g

a1 = D

1 + g, −l0, 0

表 2: (a1 , a2 ) のときのシグナル分布

裏切られたら許さない（GRIM, 図 1a）といった非協力的な戦略しか生き残らないことが知られている [5]．しかし意外なことに有名なしっぺ返し（Tit-For-Tat，TFT,
図 1b）が生き残ることはない．一方で，2 人がお互い

w2 = gw2 = bw1 = g

Pa1 ,a2 (1 − e)2 + (1 − Pa1 , a2 )e2e(1 − e)

w1 = be(1 − e)

Pa1 ,a2 e2 + (1 − Pa1 , a2 )(1 − e)2の見間違えをほぼ共有する「ほぼ公的」観測下でならTFT が均衡になりうる [1]．そこで，本論文では「ほぼ公的」観測下の繰り返し囚人のジレンマを突然変異付きレプリケータダイナミクスを用いて分析した．

2. モデル
本章では文献 [3] に基づいて，2 人私的観測付き無限回繰り返しゲームをモデル化する. ここでプレイヤ繰り返しゲームの戦略は，昨日までの行動と観測のi ∈ {1, 2} はゲームを無限期間 t = 0, 1, 2, … に渡って繰履歴から今日の行動への写像で定義する．ゲームを無り返す．各期においてプレイヤ i は有限集合 A から行動限回繰り返すとき，戦略空間は無限になるので，すべてai を選択し，その行動の組を a = (a1 , a2 ) ∈ A2 とする．の均衡戦略を具体的に特定することは現実的ではない． 次に，プレイヤ i は a に関する私的なシグナル ωi ∈ Ω
そこで，プレイヤが取りうる戦略を状態数 2 以下の有を観測する．w をシグナルの組 (ω1 , ω2 ) ∈ Ω2 とする.
限状態機械 (Finite State Automaton，FSA) に限定する． また， プレイヤが a を選択したとき w が生起する同時戦略を FSA に限定したときの期待利得をマルコフ決定
確率を o(w | a) とし， この同時確率を与える分布のこ過程に基づいて計算した利得表から，突然変異付きレとをシグナル分布と呼ぶ. 成分ゲームは無限回繰り返プリケータ方程式を構成し，その帰結を吟味する．

し行われるので，プレイヤ i の割引利得和は割引因子∑ttδ ∈ (0, 1) により ∞t=1 δ gi (a ) となる. ただし，gi (·) の値

その結果，ほぼ公的観測下では AllD や GRIM に加えて，相手を 1 度だけ処罰したら協力に戻る戦略であは表 1 に示す囚人のジレンマの利得表に従う．

る Forgiver (FGV, 図 1c) [2] が広い利得パラメータの領次にプレイヤ 2 の行動に関するプレイヤ 1 のノイズ域で生き残ることがわかった．一方で，TFT は FGV とを含む観測をプレイヤ 1 の私的シグナルとし，ω ∈ {g, b}比べてかなり狭い領域でしか生き残らなかった．

(good，bad) とする．正しい観測ではプレイヤ 2 が C を選択した際のプレイヤ 1 の私的シグナルは g， D を選

gRb(a) GRIM*gPRbgbg

PR(b) TFT

択した際の私的シグナルは b となる. プレイヤ 2 につb*(c) FGV

P

いても同様である． 表 2 にほぼ公的観測のシグナル分布を示す．ここで，Pa1 ,a2 はプレイヤ 1 と 2 の行動プロ
ファイルが (a1 , a2 ) のとき，公的シグナルが GOOD となる確率，e は公的シグナルを見間違える確率（独立誤

図 1: 主要な FSA差）である，
戦略は，そのプレイヤの過去の行動と受け取ったシグナルから現在の行動への写像で表現され，先に述べた

AllC
AllD
FGV
TFT
GRIM

0.8

AllC
AllD

FGV
TFT

WSLS
GRIM

80%
60%
40%

l0.6

100%

abundance

120%

0.4
0%

00.01

0.02

0.2

e0.03

0.040.05

図 3: 独立誤差 e による戦略比率の変化
000.2

0.4

0.60.81g

g や l がやや小さくなることによりプレイヤは初め協力を取るようになるが，裏切りの後に協力に戻ろうとは

図 2: ほぼ公的観測下のダイナミクスしない.
最後に g と l が小さいとき，FGV もしくは TFT が最通り，本研究では状態数 2 以下の非同相な 26 個の FSA大多数となるが，その領域は FGV の方が TFT がよりに限定する．

かなり広く，FGV が TFT を淘汰していると言える．ここのような数ある戦略の中から有効な戦略を発見する方法の 1 つとして，突然変異付きレプリケータダイ
ナミクス [2] がある．本論文では，その方程式を)([ −−x )] + u 1 − x , i = 1, ..., nẋi = xi fi (→x ) − ϕ(→inれは，TFT より FGV の方が見間違えが起こった後の処罰状態から協力状態に戻りやすいためである．
ここで、独立誤差 e がダイナミクスの帰結に与える影響を吟味する．e はほぼ公的観測の特徴である見間違えの共有度合いを決めるパラメータである．図 3 に

g = 0.10, l = 0.10 に e を変化させながら，収束時の戦略→−と定義する．ϕ(·) を全ての戦略の利得の平均 j x j f j ( x )， の比率を示した. 見間違えが共有されやすい (e が比較∑的小さい) ときは，FGV が他の戦略をほぼ淘汰する．一f j (·) を m x j a jm とする．ただし，a jm は戦略 j をとる∑

プレイヤが戦略 m を取るプレイヤと無限回プレイした方で，e が増加して，見間違いが共有されにくくなる (eときの割引利得和である．

が比較的大きい) と FGV はほぼ生き残らなくなり，代3.

ほぼ公的観測下のダイナミクス
図 2 にほぼ公的観測下における最大多数戦略を示す．

わりに TFT と AllC が共存するようになった.

参考文献

最大多数戦略とは，収束時に最も多くの人口を獲得し[1] C. Phelan and A. Skrzypacz. Beliefs and Private Moni-た戦略を意味する．図の横軸は自分の裏切りによる利

toring. Review of Economic Studies, 79(4):1637–1660,

得の増分 g，縦軸は相手の裏切りによる損失 l に対応

2012.

し，0.01 刻みで [0.01, 1.00] をプロットした．ここで， [2] B. Zagorsky, J. Reiter, K. Chatterjee, and M. Nowak.
Forgiver triumphs in alternating prisoner’s dilemma.
シグナル分布のパラメータは Pcc = 0.90, Pcd = Pdc =0.40, PDD = 0.30, e = 0.01，割引因子は δ = 0.9，初期戦
略分布は一様分布，突然変異率 u を 0.01 とした．

PLOS ONE, pp. 1–8, 2013.
[3] ヨンジュン, 岩崎, 神取, 小原, 横尾. 部分観測可能マ

図 2 が示すように，どんな戦略が生き残るかは利得ルコフ決定過程を用いた私的観測付き繰り返しゲー

構造に依存する. まず，g と l が大きいとき，裏切りにムにおける均衡分析プログラム. 情報処理学会論文

よる損益が大きいため，他のどの戦略も協力を維持す

誌, pp. 1234–1246, 2012.

るに十分な将来利得を獲得できない．そのため，AllDが最大多数戦略となり，単独で他戦略を淘汰する. 次[4] 神取. 人はなぜ協調するのか –くり返しゲーム理論
入門–. 三菱経済研究所, 2015.に，g および l が中程度のとき，GRIM が最大多数戦略[5] 西野上, 五十嵐, 岩崎. 私的観測下の繰り返し囚人のとなる. このとき，プレイヤは最初はお互いに協力するジレンマにおける協力のダイナミクス. 第 19 回情が，一度でも裏切りが発生すると永遠に裏切り続ける.

報科学技術フォーラム, 2020.