ゲーム理論とシミュレーション 囚人のジレンマ

2013/7/12
コンピュータモデルで社会を観る
ゲーム理論とシミュレーション
システム創成学専攻
鳥海不二夫
囚人のジレンマ
• 二人のプレイヤーがどちらかの行動を選択
– 協調(Cooperation)
– 裏切り(Defection)
• 選択の組合せによって，異なる得点
– 両者が協調すれば双方+3
– 裏切りあえば双方+1
– 片方だけ協調し他方が裏切ると，協調側は±0，裏切り者+5
プレイヤーＢの行動
協調
裏切り
協調
3, 3
0, 5
裏切り
5, 0
1, 1
プレイヤーＡの行動
2
1
2013/7/12
繰り返し囚人のジレンマゲーム
• 囚人のジレンマゲームを複数回行う
• それぞれの試合では決められた回数の対戦
– 試合が終了すると最終的な得点を記録
• すべてのプレイヤーは総当りで他のすべての
プレイヤーと対戦
• 複数回の囚人のジレンマではどのような戦略
が強いのか？
– 一回の囚人のジレンマでは裏切りが必ず有利
– 複数回だとどういう戦略が勝つのか
3
戦略（行動ルール）
• エージェントは次の手を決定する戦略を持つ
– 各プレイヤーは，過去の手を記憶
– 過去の手を使って次の自分の手を決定
前回協調されたか
ら，裏切ってやろう
常に裏切れば
必ず勝てる
4
2
2013/7/12
用意した戦略
•
ALL-C
•
ALL-D
•
PER-CD
•
TFT
•
TF2T
•
JOSS
•
FRIEDMAN
•
RANDOM
•
TFTLastD
•
AllCLastD
– 相手の手に関係なく、必ず協調する
– 相手の手に関係なく、必ず裏切る
– 協調、裏切り、協調、裏切り・・・・を繰り返す
– 最初は協調し、次からは相手が前回とった行動を真似する
– 最初は協調し、2回連続して相手が裏切ったときに、裏切る
– TFTと同様に、最初は協調し、相手に裏切られると裏切り返す。相手が協調した場合には、9
割協調して、1割裏切る
– 最初は協調し、相手が裏切らないかぎり協調を続ける。相手が一度でも裏切ると、それ以降
はずっと裏切り続ける
– 相手の手に関係なく、協調と裏切りをランダムに選択する
– 普段はTFTと同じ．最後だけ裏切る
– 普段はAllC，最後だけ裏切る
5
対戦結果
AllC
AllC
AllD
PreCD
TFT
TF2T
Joss
Friedman
Random
TFTLastD
AllCLastD
AllD
0
50
40
30
30
31.9
30
40.1
32
32
0
0
5
9
8
9
9
4.9
9
1
PreCD TFT
TF2T Joss Friedman Random TFTLastD AllCLastD
15
30
30 27.2
30
14.8
27
27
30
14
18
14
14
30.2
14
46
0
28
40 26.1
12
22.2
24
36
23
0
30 26.6
30
21.6
27
27
15
30
0 27.2
30
18
27
27
23.5
28.6 31.6
0
25.4
22.4
26.2
28.7
27
30
30 24.8
0
27.3
27
27
22.6
24.2
33 22.8
12
0
22.4
36.5
24
32
32 27.7
32
22.5
0
28
16
32
32 29.2
32
16.5
28
0
6
3
2013/7/12
獲得スコア
• TFTLastDが強い
– AllCLastDもAllCより好成績
– 最後に裏切る戦略は優秀
7
相手によって結果は異なる
• 対戦相手によって強い戦略は異なる
– AllCがいないとAllDは勝てない
– 実際には何が強いのか？
8
4
2013/7/12
進化ゲーム
• 生物世界を模したゲーム
– 弱い戦略は淘汰されていく
– 強い戦略が残っていくとどうなるのか
1位
• 囚人のジレンマにおける戦略進化
– 得点がとれなかった戦略を排除
– ランダムに新しい戦略を導入
2位
3位
• 強い戦略だけが生き残っていく
– どのような戦略が増えるのか？
4位
9
用意した戦略
•
ALL-C
•
ALL-D
•
PER-CD
•
TFT
•
TF2T
•
JOSS
•
FRIEDMAN
•
RANDOM
•
TFTLastD
•
AllCLastD
– 相手の手に関係なく、必ず協調する
– 相手の手に関係なく、必ず裏切る
– 協調、裏切り、協調、裏切り・・・・を繰り返す
– 最初は協調し、次からは相手が前回とった行動を真似する
– 最初は協調し、2回連続して相手が裏切ったときに、裏切る
– TFTと同様に、最初は協調し、相手に裏切られると裏切り返す。相手が協調した場合には、9
割協調して、1割裏切る
– 最初は協調し、相手が裏切らないかぎり協調を続ける。相手が一度でも裏切ると、それ以降
はずっと裏切り続ける
– 相手の手に関係なく、協調と裏切りをランダムに選択する
– 普段はTFTと同じ．最後だけ裏切る
– 普段はAllC，最後だけ裏切る
10
5
2013/7/12
戦略の進化
• LastDがやはり強い
– ただし，協調路線が増加
11
生き残った戦略数
• 最後に裏切る系が強い
– TFT,Friedmanも強くなる
– AllDはほとんど勝ち残れない
12
6
2013/7/12
囚人のジレンマの複雑性
• 単純なルール
– 利得表と二つの行動
• 複雑な結果
– 人間社会を模したような現象
• 「罰を与える」行動が強い
• 協調だけでは出し抜かれる
• 人間社会への理解
– 人間の本質から社会がどう成り立つかを推定
– 人は協調する→協調の方が得なことがある
13
2x2対称ゲーム
• 利得表によって異なる意味合いを持つ
– 囚人のジレンマが代表
– それ以外にも様々な状況が考えられる
プレイヤーＢの行動
協調
裏切り
協調
௔
௕
ߨ௖௖
, ߨ௖௖
௔
௕
ߨ௖ௗ
, ߨௗ௖
裏切り
௔
௕
ߨௗ௖
, ߨ௖ௗ
௔
௕
ߨௗௗ
, ߨௗௗ
プレイヤーＡの行動
14
7
2013/7/12
チキンゲーム
• 度胸試しのゲーム
– 別々の車に乗った2人が向かい合う
– 互いの車に向かって一直線に走行する
– 先にハンドルを切った方の負け
15
チキンゲーム
• 度胸試しのゲーム
– 別々の車に乗った2人が向かい合う
– 互いの車に向かって一直線に走行する
– 先にハンドルを切った方の負け
16
8
2013/7/12
チキンゲーム
• ゲームの構造
– お互い裏切る(=ぶつかる)→最悪(双方死亡)
– 自分だけ協調する(=避ける)→かなり悪い(チキンと呼ば
れる)
– お互い協調する(=お互い避ける)→まあまあ(どちらもチ
キンじゃないし，死なない)
– 相手だけ協調する→最高(相手がチキンとなる)
プレイヤーＢの行動
協調
裏切り
協調
3, 3
1, 5
裏切り
5, 1
0, 0
プレイヤーＡの行動
17
チキン・ゲームのポイント
• 囚人のジレンマケースとの相違
– どちらの戦略も他の戦略に優越していない
• 協調・裏切りどちらがよいとも言えない
– 相手の手の逆が正解
• 相手がよけないなら自分はよける方がよい
• 相手が避けるなら自分はよけない方がいい
• 衝突の恐怖
– どちらも相手がよけることを期待する
18
9
2013/7/12
チキンゲームの必勝法
• 囚人のジレンマの必勝法
– 「お人好しそうな人を選ぶ」
• では，チキンゲームでは？
– ハンドルを取り外して車の外に放り出す
– 酒を飲んで正常な判断が出来ないことをアピー
ル
• 「絶対に裏切る」ことをアピール
– 相手は協調せざるを得ない
– 殺伐とした世界
19
鹿狩りゲーム
• 森で鹿またはウサギを狩る問題
– 鹿は2人で協力しないと狩れない
– ウサギは一人でも狩れる
– 鹿は量も多いし嬉しい
– ウサギは微妙
• どう考えても鹿をとる方がお得
– ではあるが・・・
20
10
2013/7/12
鹿狩りゲーム
• 鹿狩りゲームの定式化
– 協調=鹿を狩る
– 裏切り=ウサギを狩る
• 協調すればお互いに得をする
– 相手に裏切られるなら裏切ったほうがマシ
– 裏切るメリットはないけど
プレイヤーＢの行動
協調
裏切り
協調
5, 5
0, 3
裏切り
3, 0
1, 1
プレイヤーＡの行動
21
公共財ゲーム
• 公共財ゲーム(Public Goods Game)とは
– 全員が協力し合うと幸せな世界
– 一人だけ裏切っても影響が小さい
• たとえば・・・
– ある漁港を考える
– 一定の水揚げ量を守るとずっと魚が捕れて幸せ
– 一人だけ裏切るといっぱい魚が捕れて超幸せ
– 全員が裏切ると魚が捕れなくなって不幸
22
11
2013/7/12
公共財ゲーム
• 囚人のジレンマの1対多への拡張
– 仮想的に2x2ゲームとして定式化可能
• ある資源をどのように使うか
– 協調：決められた量だけ利用する
– 裏切り：自分だけたくさん使う
みんなが協調
みんなが裏切り
自分が協調
割と嬉しい
一人だけ
悲しい
自分が裏切り
一番うれしい
誰も
うれしくない
23
公共財ゲームで
協調を促進する
ためには？
24
12
2013/7/12
公共財ゲームにおける協調の促進
• 規範ゲーム
– 裏切りに対する罰則(規範)
• 裏切りが発見されると罰せられる
罰する
裏切り者
Axelrod, R.: An Evolutionary Approach to Norms,
American Political Science Review, Vol. 80, No. 4, pp. 1095–1111(1986)
25
罰則の効果
• どの程度罰則が効果的かシミュレーションで
確認
– 罰則が存在しても裏切る人は高得点を実現でき
るのか
– 罰則があるから強調する人が増えるのか
• シミュレーションで確認
– 人をエージェントとして表現
– どんな戦略を持ったエージェントが有利か
26
13
2013/7/12
規範ゲーム
• エージェントは「大胆さ」と「復讐度」の２つのパラメータ
を持つ
– 大胆さ(B)＝裏切る確率
– 復讐度(V)＝裏切りを罰する確率
n人囚人のジレンマ
0
裏切らない
-1
裏切る
-1
-1
0
0
0
3
0
-1
-1
0
27
規範ゲーム
• エージェントは「大胆さ」と「復讐度」の２つのパラメータ
を持つ
– 大胆さ(B)＝裏切る確率
– 復讐度(V)＝裏切りを罰する確率
規範ゲーム
-1
裏切る
-1
裏切りを発見&罰する
-2
-1
-9
0
裏切らない
0
3
-1
0
0
-1
0
0
28
14
2013/7/12
n人P.D.・規範ゲーム
復讐度
j punishes i
大胆さ
i gets P=-9
j gets E=-2
Vj
j sees i
S
i defects i gets T=3
others get
H=-1
S<Bi
each i
j does not punish i
each i<>j
j does not see i
i dose not defect
n-person P.D.
basic norms game
29
進化
高い利得のエージェントをコピー
利得の高いエージェント
GAによる進化
エージェントパラメータ
大胆さ(B)＝裏切る確率
復讐度(V)＝裏切りを罰する確率
30
15
2013/7/12
シミュレーション条件
• エージェント数：20
• シミュレーション期間：100ステップ
• シミュレーション中の「大胆さ」「復讐度」の集団内
の平均値を計算してプロット
31
Axelrod実験（規範ゲーム）
協調の崩壊
協調の達成
• 協調する場合としない場合が存在
– 常に強調するわけではない
32
16
2013/7/12
公共財ゲームにおける協調の促進
• 規範ゲーム
– 裏切りに対する罰則(規範)
• 裏切りが発見されると罰せられる
• メタ規範ゲーム
– 罰しないことに対する罰則(メタ規範)
• 裏切りを見ても罰しないと罰せられる
• メタ規範の存在が協調を促進
Axelrod, R.: An Evolutionary Approach to Norms,
American Political Science Review, Vol. 80, No. 4, pp. 1095–1111(1986)
33
懲罰によるメタ規範
罰する
裏切り者
罰しない
罰しない人を
罰する
34
17
2013/7/12
メタ規範ゲーム
• エージェントは「大胆さ」と「復讐度」の２つのパラメータ
を持つ
– 大胆さ(B)＝裏切る確率
– 復讐度(V)＝裏切りを罰する確率
n人囚人のジレンマ
0
裏切らない
-1
裏切る
0
0
-1
-1
0
3
0
-1
-1
0
35
メタ規範ゲーム
• エージェントは「大胆さ」と「復讐度」の２つのパラメータ
を持つ
– 大胆さ(B)＝裏切る確率
– 復讐度(V)＝裏切りを罰する確率
規範ゲーム
-1
裏切る
-1
裏切りを発見&罰しない
裏切りを発見&罰する
-2
-1
-9
裏切る
-1
-9
-1
-1
3
3
-1
メタ規範ゲーム
-1
-1
-1
裏切り罰しない
ことを発見
&罰する
-2
36
18
2013/7/12
n人P.D.・規範ゲーム・メタ規範ゲーム
復讐度
復讐度
j punishes i
大胆さ
k punishes j
i gets P=-9
j gets E=-2
Vj
Vk
k sees j
j sees i
S
i defects i gets T=3
others get
H=-1
S<Bi
each i
j gets P’=-9
k gets E’=-2
S
k does not punish j
j does not punish i
each k<>i, j
each i<>j
k does not see j
j does not see i
i dose not defect
n-person P.D.
basic norms game
metanorms game
37
Axelrodの実験（メタ規範）
協調の達成
協調の達成
38
19
2013/7/12
実験結果
• 規範ゲーム：3パターンの結果
– 中程度の復讐度、大胆さ≒０
– 大胆さも復讐度もほとんどない
– 高い大胆さ、低い復讐度
• メタ規範ゲーム：規範が常に成立
– 高い復讐度、低い大胆さ
39
メタ規範があれば
協調は
保障されるのか？
40
20
2013/7/12
シミュレーション期間・集団規模を変
化
• 集団規模：２０－１００
• シミュレーション期間：100,1000,10000,100000
• 各条件において50回の試行
• シミュレーション最終期の「大胆さ」「復讐度」の集団内の
平均値を計算してプロット
前のパラメータ
大 胆さ （
裏 切り）
集団規模=60, 10 世代後
集団の最終平均利得
（ ０回繰返し）
世代数(log)
集団規模(20-100)
41
規範ゲーム：集団規模と世代を変化
規範ゲーム
大 胆さ
世代数(log)
集団規模(20-100)
•
•
集団規模=20では世代を ばすことで
集団規模が大きくなると 定
全に崩壊
– 裏切りが発見される回数が増え、懲罰されるコストが
–
常に しい相互
社会
常に大きくなる
42
21
2013/7/12
規範ゲームでは協調は崩壊
Boldness
復讐度
Vengefulness
大胆さ
• 一度は協調
• その後懲罰へのビリーライドによって崩壊
•
間の問題
43
メタ規範：集団規模と世代を変化
のデータ
規範ゲーム
メタ規範ゲーム
大 胆さ
世代数(log)
集団規模(20-100)
• 集団規模=20では世代が超 期（１０
で崩壊
• 集団規模が大きくなると 定
世代）
44
22
2013/7/12
メタ規範の超
期における崩壊
• 協調が達成（大胆さ＝０）されると復讐しない
エージェントが 入できる
Boldness
Vengefulness
45
メタ規範の超
期における崩壊
• 復讐度（懲罰）が 常に低く低 した （裏切り
がないので判別されない）、
に裏切りが増
加することが められずに崩壊
Boldness
Vengefulness
46
23
2013/7/12
メタ規範の超
•
期における崩壊
い期間の間に、このような復讐度の低
数多くおこり、崩壊する
が
Boldness
Vengefulness
47
ここまでのまとめ
規範
崩壊
メタ規範
崩壊
裏切り率
Axelrod’s
parameters
Generations
Axelrod’s
parameters
Generations
• 協調が達成されるといわれるメタ規範でも世代が く
なると崩壊する
• メタ規範で協調を 定的に存続させることは可能か？
48
24
2013/7/12
社会的ロキチンの導入
• 社会的ロキチン
–
く 数、常に裏切るエージェントを導入
– ロキチン：弱 化した
を
することで
を
つくり
– ここでは、常に裏切るエージェント=ロキチン＝5%
– 社会的ロキチン＝（裏切り,懲罰）=(B,V)=（１，０）
数の
る
•
–
（裏切り）に することで、
に対する
を
力＝懲罰の必 性の認
49
社会的ロキチンの導入（規範ゲーム）
規範ゲーム
大 胆さ
世代数(log)
集団規模(20-100)
ロキチンなし
• もともと裏切りが
的になりやすいので、常に
裏切るエージェントの存在は、裏切りを促進する
効果
50
25
2013/7/12
社会的ロキチンの導入（メタ規範ゲー
ム）
規範ゲーム
大 胆さ
世代数(log)
集団規模(20-100)
ロキチンなし
• ロキチンAgentの存在によって、常にだれかに裏切られるという
のある社会なので復讐度（V）を げることが
別になら
ない
– 悪をたたく、悪を
したら さない、というルールが
に守られる
51
社会的ロキチンの有 による試行
ロキチンなし
ロキチンあり
• ロキチンなしでは、協調達成 に復讐度が
することを
ことができない
–
がなくなる
52
26
2013/7/12
ここまでのまとめ
• メタ規範= 期的には裏切り
– 本協調
– く小さな確率で裏切りへ推
– いったん推 すると裏切りで 定
• 社会的ロキチンの導入
– 数の常に裏切るエージェント
– メタ規範における
な協調が実現
53
どんなワクチンが有効？
必要なのは悪か？
正義の味方か？
54
27
2013/7/12
どのようなロキチンが有効なのか
• 社会的ロキチン
– 常に裏切るビリーライダー
•
人
– 決して裏切らず、罰さず
•
平
– 決して裏切らず、悪を罰する
• 必殺
人
– 自分も悪だが、悪は さない
55
つのロキチンパターンの効果
人
（０，０）
平
（０，１）
社会的
ロキチン
（１，０）
必殺
人
（１，１）
56
28
2013/7/12
つのロキチンパターンの効果
人
社会的ロキチン
平
必殺
人
57
社会的ロキチンによる協調の
• 集団の中に 数のロキチン
調が 定する
性
入によって協
– 平
– 社会的ロキチン
– 必殺
人
• 社会的ロキチン、必殺
人が最も
定
58
29
2013/7/12
協調を守る社会的ロキチン
• 社会において協調を
持する規範
象度・モデル化
構
規範
悪人が
判
タギ
除されると実
TFT
しない
社会的ロキチン
数の 協調が 在することで
な社会
59
のまとめ
• 囚人のジレンマのシミュレーション
– 最後は裏切ろう
• さまざまなゲーム
– チキンと鹿
• ゲーム理論のシミュレーション
– 悪い人もいたほうがよい
60
30