繰り返しゲーム(1)

ゲーム理論 (上級 I)/ゲーム理論特論 I（2015 年度）
教授清水大昌
第 6 回 2015 年 11 月 09 日
[email protected]
http://www-cc.gakushuin.ac.jp/˜20060015/lecture/gradgame2015.html
今回は繰り返しゲームについての基本モデルを紹介する。
繰り返しゲーム
• 繰り返しゲームとはある基本のゲーム (stage game と言う) が何回か繰り返される動学
（展開型）ゲームのこと。
• 均衡概念は普通はサブゲーム完全均衡。
• 過去にプレーヤーが取った行動を所与として現在の行動を決定できる。過去に起こったこ
とを history と呼ぶ。
• 有限回繰り返しゲームと無限回繰り返しゲームとで分析が変わってくる。ただ、教科書な
どで言われているほど結果に変わりはない。
繰り返しゲーム：有限回
• それでは、２企業がベルトラン競争をしている場合、繰り返して市場で出会うことが暗
黙の結託を可能にするかを考えてみよう。まず企業がベルトラン競争を有限回繰り返すと
する。
• 限界費用は両者とも c とする。１回のゲームなら均衡は (c, c) で利潤は (0, 0) となること
は前に示した。
• バックワードインダクションを用いる。よって、最後の期を見てみよう。この場合のナッ
シュ均衡はお互いが限界費用価格を付けることとなる。よって (c, c) で利潤は (0, 0) のま
ま。これはここまでの history が何であってもそれが最適になるため変化のしようがない。
• その前の期を次に見る。その期に何をやっても次期に影響を与えられないので、その期も
普通にナッシュ均衡がプレイされる。このように考えていくと、第１期からずっとそのま
まナッシュ均衡の戦略を採り、 (c, c) となり利潤は (0, 0) のままとなる。静学（１回のゲー
ム）の結果を繰り返すだけで何も新しい結果は出てこない。
• 何回繰り返すゲームでも同じような結果となる。
• あまりにも繰り返す期間が長いと、先の結果の予想が現在に影響するようなことは非現実
的だと考えられる。
• stage game が囚人のジレンマでも同じ。
1
• ただ、もしナッシュ均衡が複数ある場合にはどうなるだろうか？次のゲームを見るとナッ
シュ均衡は (M , C) と (D, R) の二つある。前者は良いナッシュ均衡、後者は悪いナッシュ
均衡である。この stage game を 3 回繰り返そう。まず (D, R) を 3 回繰り返すのも (M ,
C) を 3 回繰り返すのもサブゲーム完全均衡である。ただ、よりよい均衡戦略がある。後
述のトリガー戦略に近い考え方。
– 第 1 期と第 2 期は (U , L) を目指し、第 3 期は (M , C) を目指す。
– もしその状況から逸脱したら、逸脱された方は D もしくは R を選択する。
• このような punishment path (罰則経路) が存在すれば、他のサブゲーム完全均衡の on
path (均衡経路上) での利得を上回れる。
• この戦略がサブゲーム完全均衡になっていることを確認してください。history を効果的
に使っています。
１さん
U
M
D
２さん
L
6 , 6
8 , 2
0 , 0
C
2 , 8
4 , 4
0 , 0
R
0 , 0
0 , 0
0 , 0
繰り返しゲーム：無限回
• それでは、Bertrand stage game を無限回繰り返すとする。無限回なので最終期がなく、
バックワードインダクションでは解けない。
• 毎期 (c, c) と価格付けするのもサブゲーム完全均衡となる。しかし、この設定ならもっと
高い価格で均衡を維持できる。ここではトリガー戦略を扱う。まず、最初は高い価格 (例
えば独占価格 pm ) をつける。以後、両企業がこの価格をずっと付けていれば次の期もそ
の企業は pm をつける。ただし、もしどちらかの企業が１回でも値下げをしたら、その次
の期からは熾烈な価格競争となり限界費用 c という値付けを以降行う。
• この場合のサブゲーム完全均衡の条件として、割引因子が十分大きいことが必要となる。
それを見てみよう。サブゲーム完全均衡では全てのサブゲームでナッシュ均衡になってい
る。つまり、どの期においても均衡戦略から逸脱する誘因がないということである。均衡
戦略を使ったときの割引現在価値を求める。暗黙の結託をしているときには独占利潤を
半々にすると置けば、毎期 Πm /2 得られるので、割引現在価値は次のようになる。
Πm
Πm
Πm
Πm
+δ
+ δ2
+ ··· =
2
2
2
2(1 − δ)
これに対して、結託から裏切る場合に利潤を最大にするためには価格を微少に下げて市場
を独占する。すると今期は利潤 Πm を得られる。ただし、来期からは罰としてベルトラン
均衡が繰り返されるので利潤は 0 となる。よって、割引現在価値も Πm となる。
2
• よって、逸脱しない条件としては「均衡での割引現在価値」≥ 「逸脱したときの割引現在
価値」なので、
Πm
Πm
Πm
Πm
+δ
+ δ2
+ ··· =
≥ Πm
2
2
2
2(1 − δ)
⇐⇒
δ≥
1
2
となる。
• また、これはどの期に逸脱しても同じようになる。例えば第３期に逸脱すると、利潤の流
れは
Πm
Πm
+δ
+ δ 2 Πm
2
2
となり、逸脱しない条件は
m
Πm
Πm
Πm
Πm
2Π
+δ
+δ
+ ··· ≥
+δ
+ δ 2 Πm
2
2
2
2
2
m
m
m
2Π
3Π
4Π
⇐⇒ δ
+δ
+δ
+ · · · ≥ δ 2 Πm
2
2
2
Πm
Πm
Πm
⇐⇒
+δ
+ δ2
+ · · · ≥ Πm
2
2
2
となり、元の条件と一致する。よって、最低割引因子も同じである。
• このように、企業の未来の利得に対する評価がある程度高い場合には暗黙の結託を結ぶこ
とが可能であることが分かった。
• ゲームが無限回繰り返されるという表現に抵抗を持つ人がいるかもしれない。その場合に
は割引因子 δ をゲームが続行する確率と読み替えればゲームが必ず有限回で終わること
が示せる。
フォーク定理
• 実際、無限回繰り返しゲームでは色々なサブゲーム完全均衡が存在することが知られてい
る。これを示す定理を Folk Theorem という。Folk とは民話のという意味で、研究者はみ
んな知っていたがきちんと証明してなかったということである。
• 平均利得について、どのくらい得られるか示したい場合もある。平均の方が比較しやすい
∑∞
ため。なお、各期の利得を πt と置くと、平均利得は (1 − δ) t=1 δ t−1 πt で表される。
• Friedman (1971): ナッシュ均衡で得られる利得を (e1 , e2 , · · · , en ) とする。すると δ が十分
1 に近い場合、もし (x1 , x2 , · · · , xn ) が実現可能で、また ∀i, xi > ei なら (x1 , x2 , · · · , xn )
は平均利得として維持可能。
3
しっぺ返し戦略と最適罰則規則
• トリガー戦略を使うと協調が得られる。ただ、それ以外にも協調出来る方法はある。
• しっぺ返し戦略 (Tit for Tat) とは次のような戦略。(1) 最初は協力する。(2) 次期以降は
相手が前期取った行動を取る。というもの。相手が裏切ったら自分も裏切るが、相手が謝
れば自分も許せるという性質がある。
• Axelrod の名著 Evolution of Cooperation での繰り返しゲームトーナメントで 2 回優勝し
た実績がある。(プログラムとしては最も短い行数のものの一つであったにも関わらず。)
• これはサブゲーム完全均衡だろうか？全てのサブゲームでナッシュ均衡となっているか？
• サブゲーム完全均衡であるが、トリガー戦略のときより協調をしやすくする、つまり最低
割引因子が低くなるようにする方法の一つが最適罰則規則 (optimal penal code) である。
• もし非協調的な戦略を採られた場合、罰則経路 (punishment path) に入る。そこから裏切っ
たらその罰則経路の最初に戻る、もしくは別の罰則経路に移る。プレーヤーごとに罰則経
路がある。
• では次のゲームを考えよう。トリガー戦略では協調を維持する最低割引因子は 1/2。
• そこでつぎのような罰則経路を考えよう。
P1 = {(M, R), (U, C), (U, C), · · ·}, P2 = {(D, C), (M, L), (M, L), · · ·}
• 考える必要があることは (1) 均衡経路から逸脱するインセンティブがあるか (2) 罰則経路
が credible になっているか。
• 罰則経路を長くすれば最低割引因子を下げることができるようになる。
１さん
U
M
D
２さん
L
6 , 6
8 , 2
4 , 0
C
2 , 8
4 , 4
2 , −2
4
R
0 , 4
−2 , 2
−6 , −6

Download Report