More than 3 years have passed since last update.

見間違えのある囚人のジレンマゲームをPythonで実装してみた

Last updated at 2020-07-03Posted at 2020-07-01

見間違えのある囚人のジレンマゲームをPythonで実装してみました．そのプログラムを使って，繰り返し囚人のジレンマゲームのある戦略をシミュレーション実験してみました．

囚人のジレンマゲームは，主に経済分野で企業間の談合といった協調行動を分析するために使われたりします．その他にも様々な応用事例があります．

従来の囚人のジレンマゲームモデルでは，事後的に，**相手の行動を直接観測できる（完全観測）**という仮定がされていて，それを基にプレイヤーたちは，次の行動を決めることができました．しかし，現実社会では相手の行動が完全に観測できないことは多くあります．この場合，従来のモデルでは，それら状況をうまく捉えることができません．

そこで，近年，不完全観測の囚人のジレンマゲームが盛んに研究されています．不完全観測では，相手の行動を直接観測できない代わりに，相手の行動に依存した**シグナル（信号）**を観測できるとします．

今回はこの不完全観測の繰り返し囚人のジレンマゲームをシミュレーションしていきます．

囚人のジレンマゲームとは？

囚人のジレンマゲームとは、ゲーム理論における最も代表的なゲームの１つです．このゲームは，よく以下の得点表で与えられます．

このゲームのルールは，２人のプレイヤー$X$と$Y$がそれぞれ，協力（$C$：Cooperate）または，裏切り（$D$：Defect）かを選びます．各プレイヤーが選んだ行動によって，得点が決まります．

プレイヤー$X$と$Y$がお互い$C$を選べば，両者はそこそこ良い得点である$1$点を得ることができます．$X$と$Y$のどちらかが$C$を選び，もう一方が$D$を選べば，$C$を選んだプレイヤーは最も低い得点である$-0.5$点を得ることになり，$D$を選んだプレイヤーは最も高い得点である$1.5$点を得ることができます．$X$と$Y$がお互い$D$を選べば，両者は，少ない得点である$0$点を得ることになります．お互い$C$を選べば，両者の得点を合わせると$2\ (=1+1)$となり，全体にとっては最も良い得点になり，相手に一方的に裏切られると，裏切られたプレイヤーは大損をするといった構造になっています．

このように，各プレイヤーは本当は協力し合いたいと思っているのに，裏切りに誘惑されてしまうというジレンマがあります．

１回のゲームの施行において，利己的なプレイヤー間では協力が実現しません（ナッシュ均衡）．一方で，このゲームを無期限に渡って繰り返す繰り返し囚人のジレンマゲームにおいては，利己的なプレイヤー間においても，協力が実現されるということが理論的に証明されています（フォークの定理）．

そこで，この繰り返し囚人のジレンマゲームにおいて，どんな戦略が強いかが研究されてきました（アクセルロッドの実験）．

不完全私的観測付き繰り返しゲーム

プレーヤーが過去に採った行動をすべて正確に観測できる**完全観測（Perfect Monitoring）**を仮定する従来の囚人のジレンマゲームとは異なります．**不完全観測（Imperfect Private Monitoring）では，過去のプレイヤーたちの行動を直接観測することができません．その代わり，前回のプレイヤーの行動に依存したシグナルを観測すると仮定します．今回のゲームでは，個別のシグナルを受けとる私的観測（Private Monitoring）**を仮定します．この各プレイヤーが受け取るシグナルは，相手は観測することができません．

具体例

不完全私的観測の囚人のジレンマゲームは，以下の小売店の価格競争を想定しています．

小売店の価格競争では，同じ商品を売っているとして，その商品の価格を維持するか，価格を下げるかによって，売り上げを確保しようとします．

実際の小売店の利益は，来客数（シグナル）と商品の価格（自分の行動）によって決まります．例えば，お互いに価格を維持（協力）をしていれば，お客さんは一方の店に偏ることなく，高い値段で商品を売ることができ，両店舗とも，そこそこ高い利益を確保することができます．

※お客さんは，各店舗の商品の値段によって，増減するので，囚人のジレンマと同じ構造を持ちます．

そのような状況では，以下の場合が想定されます．本来であれば，各店舗が価格維持していれば，両店舗とも高い利益を得ることができますが，来客数はさまざまな要因によって変動します．例えば，予測できない需要ショックや近隣に知らずのうちに新しく同様な店舗ができることによって，店舗の客が減るかもしれません（下図）．店舗の利益は，各店舗が決めた商品の値段（行動）が直接利益に結び付くわけではないということがポイントです．

一方で，店舗は相手に知られないように，商品を値下げし，お客さんを獲得することもできます（カタログ価格より低い値段をお客さんの前のみで提示など）．そのような状況を従来の囚人のジレンマゲームでとらえることはできません．

そのような状況を不完全私的観測付き繰り返しゲームは想定しています．

ゲームの内容

ゲームを定義します．

以下の得点表で与えられるゲームを繰り返し行います．

このゲームのルールは，$2$人のプレイヤー$X$と$Y$がそれぞれ，協力（$C$：Cooperate）または，裏切り（$D$：Defect）かを選びます．各プレイヤーが選んだ行動によって，得点が決まります．

基本的に相手プレイヤーが$C$を選んだとき，自分はgoodを意味する$g$というシグナルを観測します．そのとき，自分が$C$の行動を選択していれば$1$点を得ます．また，$D$の行動を選択していれば$1.5$点を得ます．同様に，相手プレイヤーが$D$を選んだとき，自分はbadを意味する$b$というシグナルを観測します．そのとき，自分が$C$の行動を選択していれば$-0.5$点を得ます．また，$D$の行動を選択していれば$0$点を得ます．

ここまでの仮定は従来の囚人のジレンマゲームとほぼ同じです．

観測エラーを定義します．

今回のモデルでは，行動に関するシグナル$g$と$b$が環境などの要因でエラーが起き反転することとします．

相手プレイヤーが$C$を選んだとしても，自分は，相手が$D$を選んだことを意味する$b$というシグナルを得ることがあります．反対に，相手が$D$を選んだとしても，自分は，相手が$C$を選んだことを意味する$g$というシグナルを得ることがあります．このように，実際の行動を意味するシグナルと逆のシグナルを観測することを観測エラーと言います．

今回は，プレイヤーの一方のみがエラーする確率を$\epsilon$，両方エラーする確率を$\xi$と定義します．このエラー率$\epsilon$，$\xi$はあまり大きくないとします．

プレイヤーの戦略を定義します．

プレイヤー$X$の戦略を，${\bf p}=(p_{Cg},p_{Cb},p_{Dg},p_{Db}; p_0)$と定義します．この戦略，記憶１（Memory-One）戦略と呼ばれます．この戦略を使うプレイヤーは，前回のゲームの結果のみを考慮して，今回の行動（$C$ or$ D$）を確率的に決定します．

例えば，$p_{Cg}$は，前回のゲームで，プレイヤー$X$が$C$を選び，$g$を観測したとき，今回のゲームで協力する確率となります．$p_{Cb}$は，前回のゲームで，プレイヤー$X$が$C$を選び，$b$を観測したとき，今回のゲームで協力する確率となります．その他も同様に考えます．$p_0$は，初回のゲームで協力する確率です．

プレイヤー$Y$の戦略は，同様に，${\bf q}=(q_{Cg},q_{Cb},q_{Dg},q_{Db}; q_0)$とします．

以下の図は，ゲームの状態が$CC$（相互協力）から$CD$（$X$が協力，$Y$が裏切り）へと遷移する例です．この図は，各プレイヤーが決めた行動によって，どのように各プレイヤーがシグナルを観測し，上記で定義した戦略を基に，次の状態に遷移するかを理解することができます．今回のシミュレーションでは関係ありませんが，これをマルコフ過程と捉えることができて，以下のような遷移図から，このゲームの遷移行列を定義することができます．

Pythonプログラム

以下のPythonプログラムは上記を実装しました．シミュレーションによって，どんな戦略が強いかを調べることができます．以下では，各プレイヤーの戦略を${\bf p}=(1/2,1/2,1/2,1/2; 1/2)$と${\bf q}=(1/2,1/2,1/2,1/2; 1/2)$としています．ゲームの繰り返し回数を$100000$回としています．エラー率は，$\epsilon=0.05$と$\xi=0.05$と設定しています．

import random

max_t = 100000 # ゲームの繰り返し回数

point  = {'x' : 0, 'y' : 0} # プレイヤーの合計点数
action = {'x' : None, 'y' : None} # プレイヤーの行動 C or D
signal = {'x' : None, 'y' : None} # プレイヤーの観測したシグナル
state  = {'x' : '0', 'y' : '0'} # ゲームの状態を設定
payoff = {'Dg':1.5, 'Cg':1.0, 'Db':0, 'Cb':-0.5} # ゲームの得点
epsilon = 0.05; xi = 0.05 # 一方のみがエラー，両方エラーする確率

p = {'Cg':1/2, 'Cb':1/2, 'Dg':1/2, 'Db':1/2, '0' :1/2} # プレイヤーXの戦略
q = {'Cg':1/2, 'Cb':1/2, 'Dg':1/2, 'Db':1/2, '0' :1/2} # プレイヤーYの戦略

# 繰り返しゲーム
for t in range(max_t):
    # 前回のゲームの結果を基に，C or Dを選択する
    action['x'] = 'C' if random.random() < p[state['x']] else 'D'
    action['y'] = 'C' if random.random() < q[state['y']] else 'D'
    # シグナル
    signal['x'] = 'g' if action['y'] == 'C' else 'b'
    signal['y'] = 'g' if action['x'] == 'C' else 'b'
    # 観測エラー
    if random.random() < 2 * epsilon:
        player = 'x' if random.random() < 0.5 else 'y'
        if signal[player] == 'g':
            signal[player] = 'b'
        else:
            signal[player] = 'g'
    elif 2 * epsilon < random.random() < 2 * epsilon + xi:
        for player in ['x', 'y']:
            if signal[player] == 'g':
                signal[player] = 'b'
            else:
                signal[player] = 'g'
    # 行動とシグナルを基に利得を配分
    for player in ['x', 'y']:
        if action[player] == 'C' and signal[player] == 'g':
            point[player] += payoff['Cg']
        elif action[player] == 'C' and signal[player] == 'b':
            point[player] += payoff['Cb']
        elif action[player] == 'D' and signal[player] == 'g':
            point[player] += payoff['Dg']
        elif action[player] == 'D' and signal[player] == 'b':
            point[player] += payoff['Db']        
        # ゲームの結果を代入
        state[player] = action[player] + signal[player]

# 各プレイヤーの平均点数を出力
print('Player X: {} Points'.format(point['x'] / max_t))
print('Player Y: {} Points'.format(point['y'] / max_t))

このプログラムを実行すると，以下の実行結果が得られます．．

Player X: 0.49855 Points
Player Y: 0.49827 Points

つまり，${\bf p}=(1/2,1/2,1/2,1/2; 1/2)$と${\bf q}=(1/2,1/2,1/2,1/2; 1/2)$の戦略を対戦させたとき，
ほぼ同点の結果となることがわかります．これは当然の結果です．

次に，いろいろな戦略を試してみたいと思います．

Zero-determinant戦略を実験する

Zero-determinant戦略（ゼロ行列式戦略：ZD戦略）は，囚人のジレンマゲームのある１つの戦略です．以前，囚人のジレンマゲームの相手を搾取する戦略(Qiita)で紹介しました．このZD戦略は，シンプルな戦略で，記憶１戦略$\bf p$や$\bf q$で定義することができます（ZD戦略の導出自体は少々難しい）．今回は，この見間違えがある囚人のジレンマゲームにおいて，この戦略を実験していきます．

ZD戦略は，有名な部分戦略として，Equalizer戦略やExtortion戦略があります．Equalizer戦略は，相手の平均得点を固定ことができ，Extortion戦略のExtortionは恐喝という意味で，この戦略は相手の得点を搾取することができます．

細かい説明はここまでとして，この戦略を実験していきます．

Equalizer戦略

相手がどんな戦略であっても，相手の得点を固定することができます．相手の平均得点を$0.5$点にさせるEqualizer戦略${\bf p} = (0.8, 0.365217,0.634783, 0.2;1/2)$と${\bf q}=(1/2,1/2,1/2,1/2; 1/2)$と設定し，シミュレーションを実行すると，以下の結果が得られます．

Player X: 0.496385 Points
Player Y: 0.50177 Points

確かに，Player Y: 0.50177 Pointsとなっていて，相手の得点が$0.5$点に近いことがわかります．たまたまかもしれないので，相手の戦略を囚人のジレンマゲームでは最強な常に裏切り戦略（$ALLD$戦略）${\bf q}=(0,0,0,0;0)$でも試してみると，以下の結果が得られます．

Player X: -0.004545 Points
Player Y: 0.50022 Points

やはり，Player Y: 0.50022 Pointsとなっていて，相手の得点が$0.5$点に近いことがわかります．

以下の図は，上の戦略のほかに相手の戦略$\bf q$を乱数で，いろいろを与えてみて，シミュレーションを行ったものです．$\bf q$は100戦略分生成して，それぞれでプログラムを実行しました．この図からどんな相手の戦略$\bf q$であっても，相手は$0.5$点に固定されてしまっていることがわかります．

※灰色の線で囲まれた領域は，実現可能な利得関係の領域です．二人のプレイヤーの利得関係は必ずこの領域のどこかになります．縦軸がEqualizer戦略を採るプレイヤーの得点，横軸が相手の得点としています．

したがって，Equalizer戦略は，エラーがあるときも，相手の戦略に関わらず，相手の得点を固定することができます．

Extortion戦略

Extortion戦略は，エラーなしの普通の囚人のジレンマゲームでは，相手の得点を搾取する戦略であることが知られています．最も強い常に裏切り戦略（$ALLD$戦略）やExtortion戦略に対しては，引き分けで返すことができます．

エラーありの場合ではそれが可能なのか？

Equalizer戦略のときに作成した図と同じように，乱数で相手の戦略$\bf q$をいろいろ変えて，Extortion戦略とゲームを行わせると，以下の図が得られます．

※赤点は相手が$ALLD$戦略，青点は相手が$ALLC$戦略（常に協力戦略）のときのものです．縦軸がExtortion戦略を採るプレイヤーの得点，横軸が相手の得点としています．

この図から，もはやExtortion戦略は$ALLD$戦略（赤点）に勝てなくなってしまっていることがわかります．一方で，$ALLD$戦略以外の大部分の戦略に対しては，まだまだ勝つことができています．

エラーがない場合は，Extortion戦略は$ALLD$戦略に対して，引き分けという結果にさせることができ，$ALLD$からの搾取を防ぐことができていました．しかし，エラーが入ると，$ALLD$戦略からの搾取を許す結果となってしまいました．一方で，$ALLD$戦略以外の戦略に対しては，搾取できるということがわかりました．

まとめ

見間違えのある囚人のジレンマゲームのシミュレーションをPythonで実装してみました．今回のプレイヤーの戦略は，単純な記憶１戦略としていますが，もしかすると，記憶を増やした戦略や学習を入れた戦略にするともっと強い戦略が見つかるかもしれません．

今回は，Zero-determinant戦略を実験してみました．エラーある場合でもなお，Equalizer戦略は相手の得点を固定することができ，Extortion戦略は$ALLD$戦略に対しては，搾取を許してしまうが，その他の大部分の戦略に対しては，搾取することができるということがわかりました．したがって，エラーがある場合でも，ある程度有効な戦略であるとはいえるのではないかと思います．

強い戦略やおもしろい戦略などを見つけることができたら，ぜひ教えてください(>_<)