囚人のジレンマ×無限回 - はなし約二分の一

やること
囚人のジレンマを無限回やるやつをテーマとします。

1. 前提事項
2. 実際の計算
3. 以上より...
4. まとめ

1. 前提事項

今回は、次の表を使用する。
　 Bさん
　　　　　　協力　裏切
Aさん　協力　 [3, 3] [0, 5]
　　裏切 [5, 0] [1, 1]

※[]の中身は、[Aさんの利得, Bさんの利得]

　数値の元ネタは、アクセルロッドの論文*1のTABLE Ⅰ

囚人のジレンマを無限回行うという場合の合計利得を計算する際には、 $0 \lt δ \lt 1$ となる割引率 $δ$ を用いて、

　1回目　 2回目　 3回目　 ...
　[利得] + $δ$ ×[利得] + $δ^2$ ×[利得] ...

のように、未来のゲームで得る利得には $δ$ が掛かっていくことが多いので、今回はそれに従う。

これは、 $δ$ が、
・未来の利益よりも今の利益を重視する傾向性を表している
・各回ごとにゲームが終了する確率を表している
というような考え方に基づいているため...らしい*2。
（※個人的には後者の考え方が好き）

例えば、両者が裏切を選択し続けた場合、それぞれの利得は、
$1 + δ×1 + δ^2×1 + ... = \frac{1}{1-δ}$
のように計算できる。

で、このような設定において、
・Aさんが戦略α、Bさんが戦略βを用いてゲームに臨んだ
とする。このときに、
・Aさんが戦略αをやめて他の戦略に変更すると、自分の利得（orその期待値）が高くなるかどうか
を検討するらしい。

今回Aさんは、
・戦略αをやめた方が自分の利得が高くなる場合は、戦略αをやめる
・戦略αを続けた方が自分の利得が高くなる場合は、戦略αを続ける
ものとする（※Bさんも同じような想定とします）。

囚人のジレンマと言えば、対戦する両者が自分の利得を最大化しようとすると今回の表では[1, 1]が選ばれてしまい、どう見てももっと良いはずの[3, 3]が選ばれないというものだった。
で、囚人のジレンマを無限回行った場合、状況に変化があるかどうかを計算してみるというテーマである*3。

※各回のゲームは、(協力, 裏切)のように書いて、
　Aさんが協力を選択し、Bさんが裏切を選択した
　というようにしておく。

2. 実際の計算

2-1. 裏切戦略

まずは、「相手の手に関わらず裏切りを選択し続ける」という戦略をお互いが採っている場合を考えてみる。

この場合ゲームの進行は、
1回目 2回目
(裏切, 裏切) → (裏切, 裏切)→...
のようになるが、このときのAさんの利得は上で計算したように $\frac{1}{1-δ}$ である。

もしも、Aさんがt回目にこの戦略をやめて突然協力を選択した場合を考えると、そのときの利得は、
$1 + δ×1 + δ^2×1 + ... + δ^{t-1}×0 + δ^t×1 + ... = \frac{1}{1-δ} - δ^{t-1}$
であるため、 $δ^{t-1}$ 分確実に損をすることになる。

となると、Aさんが自分の利得を最大化しようとするならば、Aさんは裏切戦略を変更することができなくなってしまう。

同様のことをBさんの立場から計算すると、Bさんも戦略を変更できないことになるため、このパターンではお互いに戦略を変えることができないという結論が導かれる。

2-2. 協力戦略

逆に、お互いに「相手の手に関わらず協力を選択し続ける」場合を考えてみる。

この場合、ゲームの進行は
1回目 2回目
(協力, 協力) → (協力, 協力)→...
のようになるため、Aさんの利得は
$3 + δ×3 + ... = \frac{3}{1-δ}$
である。

Aさんが $t$ 回目にこの戦略をやめ、裏切りを選んだ場合の利得は、
$3 + δ×3 + ... + δ^{t-1} × 5 + δ^t × 3 + ...$
$= \frac{3}{1-δ} - δ^{t-1} × 3 + δ^{t-1} × 5$
$= \frac{3}{1-δ} + δ^{t-1} × 2$
ということで、 $δ^{t-1} × 2$ の分得することが分かる。

したがって、このパターンではAさんは協力戦略をやめて裏切りを選んだ方が得ということになるだろう。

Bさんの側から考えると、Bさんも協力戦略をやめた方が得であるため、どちらも戦略を変えてくるだろうという結論になる（と思う）。

2-3. トリガー戦略

このテの考察における重要戦略として、「トリガー戦略」というものがある。

これは、

・相手が裏切るまでは自分は協力を選び続ける

・相手が一度でも裏切ったら、自分は裏切りを選び続ける

という「絶対に許さない作戦」を指す。

お互いにトリガー戦略を採った場合、ゲームの進行は

1回目 2回目
(協力, 協力) → (協力, 協力)→...

となることから、Aさんの利得は $\frac{3}{1-δ}$ となる。

ここで、Aさんが戦略を変更して裏切を選んだ場合の利得の変化を考える。

$t$ 回目にAさんが裏切を選ぶと、 $t+1$ 回目以降Bさんは裏切を選択してくる。そのため、Aさんが自分の利得を最大化するには、Aさんも裏切をし続けるしかなくなる。

つまり、
1回目 2回目　　　　　　 t回目　　　　　t+1回目
(協力, 協力) → (協力, 協力)→...→（裏切, 協力）→（裏切, 裏切）→...
という進行になる。

この場合の利得は、
1回目～ $t-1$ 回目までの合計が
$3 + δ×3 + ... + δ^{t-2} ×3 = \frac{3 - δ^{t-1}}{1-δ}$
$t$ 回目が
$δ^{t-1}×5$
$t+1$ 回目以降が
$δ^t×1 + δ^{t+1}×1... = \frac{δ^t}{1-δ}$
となる。

これらの合計が $\frac{3}{1-δ}$ より大きい場合、Aさんはトリガー戦略をやめる方が得ということになり、 $\frac{3}{1-δ}$ 以下の場合、トリガー戦略を継続することになる。

ここでは、トリガー戦略を継続する条件を調べてみる。なので、
$\frac{3}{1-δ} \geq \frac{3 - δ^{t-1}}{1-δ} + δ^{t-1}×5 + \frac{δ^t}{1-δ}$
となる。

$0 \lt δ \lt 1$ を考慮してこれを解くと、
$δ \geq 1/2$
となる。したがって、割引率が0.5以上のとき、Aさんは戦略を変更すると損をすることが分かる。

同様にBさんも戦略を変更できないため、 $δ \geq 1/2$ であるならば、
(協力, 協力) → (協力, 協力)→...
というゲームを続けるしかないような状態になる。

ここから、無限回の囚人のジレンマではお互いに協力するような均衡状態が存在する言える。

2-4. しっぺ返し戦略

次に、「しっぺ返し戦略 vs. しっぺ返し戦略」について検討する。

しっぺ返し戦略とは、
・最初は協力する
・前回相手が裏切ったら、こちらも1回裏切り返す
という戦略を指す。

囚人のジレンマと言えばしっぺ返し戦略というイメージの人もいるかもしれません。

お互いにしっぺ返し戦略を採った場合、
1回目 2回目
(協力, 協力) → (協力, 協力)→...
となることから、今回もAさんの利得は $\frac{3}{1-δ}$ となる。

ここで、Aさんが $t$ 回目に裏切りを選択するときの利得を考える。
$t$ 回目までの利得はトリガー戦略と同じなので、
$\frac{3-3δ^{t-1}}{1-δ} + 5δ^{t-1}$
のようになる。
で、 $t+1$ 回目以降については、場合分けで検討します。

(1) $t+1$ 回目以降は協力に戻す場合

$t+1$ 回目以降、
(協力, 裏切)→(協力,協力)→(協力, 協力)→...
という元の形に戻るので、利得は
$0 + 3δ^{t+1} + 3δ^{t+2} + ... = \frac{3δ^{t+1}}{1-δ}$
となる。

この場合、
$\frac{3}{1-δ} \geq \frac{3-3δ^{t-1}}{1-δ} + 5δ^{t-1}+ \frac{3δ^{t+1}}{1-δ}$
であればAは戦略を変更すると損をするため、（ $0 \lt δ \lt 1$ であることに注意して）これを解くと、
$δ \geq 2/3$
である。

(2) $t+1$ 回目以降
$t+1$ 回目以降、
(裏切, 裏切)→(裏切, 裏切)→...
という形になるが、トリガー戦略のときに出てきた状態と同じなので、
$δ \geq 1/2$
となるだろう。

(1),(2)をまとめると、
$δ \geq 2/3$
であれば、Aさんは「しっぺ返し戦略」から離脱できないし、相手のBさんも「しっぺ返し戦略」をやめることができないということになる。

つまり、この場合も
(協力, 協力) → (協力, 協力)→...
という均衡となる。

2-5. 運ゲー戦略

変則的な例として、次のような戦略を考えてみる。
Aさん（運ゲー戦略①）
・相手が「運ゲー戦略②」をとり続けている限り、自分は90%の確率で協力を選ぶ
・相手が「運ゲー戦略②」から外れた場合、以降裏切り続ける

Bさん（運ゲー戦略②）
・相手が「運ゲー戦略②」をとり続けている限り、自分は80%の確率で協力を選ぶ
・相手が「運ゲー戦略②」から外れた場合、以降裏切り続ける

この戦略を採ったときのAさんの利得期待値は、
$0.72×3 + 0.08×5 + 0.02×1 = 2.58$

これまでと同様に、 $t$ 回目以降、Aさんが運ゲー戦略①を継続する場合と外れる場合を比較する。

運ゲー戦略①を継続する場合は、
$2.58 + 2.58×δ + ... = \frac{2.58}{1-δ}$

運ゲー戦略①を辞める場合、
・ $t$ 回目に得られる利得期待値を $0.8×5 + 0.2×1 = 4$ とする
・ $t+1$ 回目以降、Bさんは裏切りをしてくるので、こちらも裏切りを選択する

として、
$2.58 + 2.58×δ + 2.58×δ^{t-2} + ... +4×δ^{t-1} + 1×δ^t + ...$
$= \frac{2.58 - 2.58×δ^{t-1}}{1-δ} + 4×δ^{t-1} + \frac{δ^t}{1-δ}$
となる。

したがって、
$\frac{2.58}{1-δ} \geq \frac{2.58 - 2.58×δ^{t-1}}{1-δ} + 4×δ^{t-1} + \frac{δ^t}{1-δ}$
のとき、Aさんは運ゲー戦略①を継続するしかないということになる。

$0 \lt δ \lt 1$ であることに注意してこれを解くと、
$δ \geq 0.47333...$

同様に、
$δ \geq 0.5594594...$
のとき、Bさんも戦略を変更することができなくなる。

したがって、 $δ \geq 0.5594594...$ のときには両者とも運ゲー戦略を継続し、このときの期待利得は、
Aさん: $\frac{2.58}{1-δ}$
Bさん: $\frac{2.63}{1-δ}$
である。

このように、
・両者の期待利得が等しくならない
・期待利得が $\frac{1}{1-δ}$ でも $\frac{3}{1-δ}$ でもない
ような均衡パターンも存在する。

これらについて、一般的に証明したものをフォーク定理と呼ぶ...らしい*4。

2-6. 寛容なしっぺ返し戦略

最後に、寛容なしっぺ返し戦略を取り上げてみる。

この戦略は、

相手が裏切りを選択した場合、次のターンに自分は確率 $r$ で裏切りを選択する

というものである。

計算過程をがっつり省きますが、 $t$ 回目にAさんが裏切りを選択し、
(1) $t+1$ 回目以降協力に戻す場合、

$δ \geq 2/3r$

(2) $t+1$ 回目以降協力に戻す場合、
$δ \geq 1/2r$
となる。

条件としては(1)の方が厳しいので、

$δ \geq 2/3r$

のときには、寛容なしっぺ返し戦略同士の場合、お互いに戦略を変えられないと言える。

詳しく見ると、 $δ$ が1に非常に近い状態ならば、 $r=2/3$ (3回に1回見逃す)くらいまで寛容になることが可能。

3. 以上より...

さて、このことから現実においてどのようなことが言えるだろうか。

3-1. その1

まずは、自己利益の最大化を目的とした場合であっても、お互いに協力し続けるというパターンがあり得るということは言える。

上で見たように、裏切り戦略で均衡するパターンや中途半端な利得期待値で均衡するというパターンも存在するが、お互いに利得3を獲得し続けるというパターンも実際に存在している。

囚人のジレンマ的な状況であっても、自分の利得を優先することで、同時に全体の利得が最大になることが可能...と言えるかもしれない。

しかも、寛容なしっぺ返し戦略を見る限り、けっこう寛容な戦略でもそれが可能だったりする...ような気がします。

そう、我々は協力し合った方が基本的には得なのです！

（･･･本当に？）

3-1. その2

しっぺ返し戦略と言えば、アクセルロッドの研究が有名だと思われる。

が、後年の研究*5において、複数人でチーミングをして、

・チーム内の1人をひたすら押し上げる

・チーム外の人と対戦したときは、ひたすら足を引っ張る

という戦略（主人と奴隷戦略と呼ぶようです）をとると、押し上げられた1人が好成績を取ることが判明している。

しかし、この戦略は「自分の利得を高くする」というここまでの前提に沿っておらず、

・自分以外の1人の利益を優先する

・自分の利益よりも他人の足を引っ張ることを優先する

という方針となっているため、ここまでの計算は適用できない。

そのため、主人と奴隷戦略を用いて何か言えることがあるかというと、意外と特にないようなのだと思われます。

例えば「囚人のジレンマ的なシチュエーションにおいて、全体の利得を最大化するにはどうすればいいか？」とか「自分の利得と全体の利得のどちらを優先すべきか？」みたいな問題を考えるときに、「主人と奴隷戦略を使うと、何人かを犠牲に1人が好成績を収めますよ」と答えても、残念ながら全体の利得にも自分の利得にも回答にならない。

（一方で、「しっぺ返し戦略やトリガー戦略は、全体の利得の合計と個人の利得を両立させられる」という回答は、みんな自分の利得を高めようとするという前提に基づけば、それっぽい回答に見えそうな気がします）

3-3. その3

なお「自分の利得の最大化と全体の利得の合計の最大化は、常に両立させることが可能か」については、たぶん無理だと思っています。

例えば
協力　裏切
　協力 (0, 0) (0, 3)
裏切 (1, 0) (1, 1)
の場合、全体の利得の合計を最大化するのは(協力, 裏切)のパターン（合計3）だが、Aさんは協力を選ばないため、お互いに裏切るパターン（合計2）が選ばれることになるだろう。さらに、お互いに裏切るパターンから他のパターンに変更すると、必ずどちらかが損をするという状況となる。

囚人のジレンマのケースでは個人の利得と全体の利得が両立可能だったので問題は無かったが、この場合のように自分の利得と全体の利得のどちらを優先すべきかみたいな問題は、ここでは解答が出せないように思われる（未検討）。

ここに解答を出すとすると、

・均衡している状態＝望ましい状態

・合計が大きい方＝望ましい状態

のような、何らかの前提をおく必要があるだろう。

...という訳で、我々は協力し合った方が基本的には得とは必ずしも言えないという感じ...？

もちろん、協力がいつも無意味という訳でもないはずである。「約束を破って自分だけ抜け駆けする」というようなシチュエーションは、囚人のジレンマと似たような状況として描ける可能性が高いだろうし、そのような場合はお互いに約束を破れないという結果が実現することは大いにありそうに見える。

（一方「自分の利益と全体の利益がぶつかる」は「見返りを一切求めず寄付を行う」とか？）

4. まとめ

・囚人のジレンマのシチュエーション「は」見た目に反して協調路線が優秀

・ある程度寛容でもどうにかなる

*1:Axelrod, R. (1980). "Effective choice in the Prisoner's Dilemma." Journal of Conflict Resolution, 24(1), 3–25.

*2:Aumann, R. (1981) "Survey of repeated games." Essays in game theory and mathematical economics : in honor of Oskar Morgenstern, p.11-42

*3:計算の概略などはネットでググって出てきた資料を一部参考にしました。
例えば、

・上條良夫「ゲーム論 I 第十一回」
・mas178 『読書メモ』「ゲーム理論・入門新版 (岡田章) 第07章繰り返しゲーム」

など

*4:Wikipediaの記事

*5:Wikipediaの記事