新ゲーム理論ゼミ 第５章 「繰り返しゲーム」 M1 松村 草也.

Presentation on theme: "新ゲーム理論ゼミ 第５章 「繰り返しゲーム」 M1 松村 草也."— Presentation transcript:

1 新ゲーム理論ゼミ 第５章 「繰り返しゲーム」 M1 松村 草也

2 第５章 - 目次 有限繰り返しゲーム 無限繰り返しゲーム フォーク定理 囚人のジレンマの無限繰り返しゲーム 錯誤と寛容 繰り返しゲームの要素
支配型固定型戦略 トリガー戦略（永久処罰引き金内蔵戦略） 反射戦略（しっぺ返し戦略） 仏の顔も３度まで戦略 錯誤と寛容 フォーク定理 繰り返しゲームの要素

3 有限繰り返しゲーム limited repeated game

4 チェーンストア・パラドックスから 小売店が市場に参入してくる状況を想定する．１度ならば協調的行動をとった方が利得が大きいことが予想される．しかし，何度もそれを許すことは，チェーン店としての牙城を危ぶませるものである． 同じゲームでも，１度きりなのか，大きな流れの中での１度なのかによって，プレイヤーが選択する行動は異なってくるに違いない． この章では，同一のゲームが繰り返される場合について考えてみる．

5 例１：囚人のジレンマの２回繰り返しゲーム ペイオフマトリックス ルール １回目はプレイヤー1,2は互いに独立に自分の戦略を選択する。
協調行動C 競争行動D 2,2 0,3 3,0 1,1 ルール １回目はプレイヤー1,2は互いに独立に自分の戦略を選択する。 ２回目は１回目の各プレイヤーの戦略と得られた利益を知った上で互いに独立に戦略を選択する。 繰り返しゲームにおけるプレイヤーの利得は２回の成分ゲームの合計。 各プレイヤーは２回で終了することを知っている。

6 例１：囚人のジレンマの２回繰り返しゲーム では，前回のゲームとの関連によって 戦略を分類するとどうなるか？
Q：プレイヤーは純戦略をいくつもっている？ P1 P2 P1 P2 １度目のゲームでは情報集合は１ ２度目のゲームでは情報集合は４ 合わせて５つの情報集合が存在． 25 = 32 の純戦略をそれぞれ持っている． (CCCCC),(CCCCD),(CCCDC),...,(DDDDD) では，前回のゲームとの関連によって 戦略を分類するとどうなるか？

7 有限繰り返しゲーム - 戦略の組み合わせで考える
２回目ゲーム時の純戦略を４つに分類 １回目の結果に無関係に常にCを取る。(CCCC) １回目に相手のプレイヤーが取った行動と同じ行動を取る。 １回目に相手のプレイヤーが取った行動と違う行動を取る。 １回目の結果に無関係に常にDを取る。(DDDD) C1 C2 C3 C4 D1 D2 D3 D4 4,4 2,5 0,6 3,3 1,4 5,2 4,1 2,2 6,0 2,2* C D 均衡点は((D4),(D4))になる．つまり(DDDDD)．

8 有限繰り返しゲーム - まとめ 最後のゲームについては，１回きりのゲームと同じように考え，支配戦略を取る．
頂点から底点に向かって，逆戻り推論法を適用することが出来るのが特徴． 有限回であるという共通認識がある限り同じことが起こる． 有限回ならチェーン店も許してくれるということか？ ん？

9 無限繰り返しゲーム endless repeated game

10 観測されている事実 囚人のジレンマの均衡利得はパレート最適ではないが，囚人のジレンマ的状況が繰り返されるとプレーヤ間に暗黙の協調が生まれ，協調的行動がとられ，パレート最適な利得ベクトルが実現することが観察されている． 「無限に繰り返す」という状況下で行う意思決定を考えることで，より現実的な考察が可能になるのではないだろうか？

11 例１：囚人のジレンマの無限繰り返しゲーム １回目のプレイにおいて、プレイヤーは他のプレイヤーと独立に自分の行動を選択。
ペイオフマトリックス 協調行動C 競争行動D 5,5 0,8 8,0 2,2 ルール １回目のプレイにおいて、プレイヤーは他のプレイヤーと独立に自分の行動を選択。 t+1回目のプレイでは、これまでに各プレイヤーが取った戦略と利益を知った上で独立に行動を選択。 プレイヤーのゲーム全体としての利益は毎回の利益の平均とする。

12 無限繰り返しゲーム - ４つの戦略例 α：支配戦略固定型戦略 β：トリガー戦略 γ：反射戦略（しっぺ返し戦略） δ：仏の顔も３度まで戦略
無限に繰り返すため，純戦略の列挙は不可能． 行動パターンも無限に存在するが，その中からいくつかを挙げて考える． α：支配戦略固定型戦略 β：トリガー戦略 γ：反射戦略（しっぺ返し戦略） δ：仏の顔も３度まで戦略

13 無限繰り返しゲーム - 戦略の内容比較 α 支配戦略固定型戦略 β トリガー戦略 γ 反射戦略 δ 仏の顔も３度まで戦略 １回目 Dを選択
Cを選択 ２回目以降 反射行動 相手がDを 選択したら それ以降 Dを選択 反射行動 （次はD） ３回まではCを選択 それ以降は反射行動

14 無限繰り返しゲーム - 均衡点への到達 正確に戦略を保つならば， （α,α）,（β,β）,（γ,γ）,（δ,δ）,（β,γ）,（β,δ）,（γ,δ） の戦略組み合わせはどれも均衡点． 相手が裏切りを行った際の仕返しの方法が異なる． ⇒３回目のゲームで裏切りを行い，その後元の戦略に 戻ると仮定した場合の，戦略ごとの仕返し機能を比較 してみる．

15 無限繰り返しゲーム - 戦略の仕返し機能比較
【α：支配戦略固定型戦略】 【β：トリガー戦略】 【γ：反射戦略】 【δ：仏の顔も３度まで戦略】

16 シミュレーション 各プレイヤは10個ずつの戦略を持っている． 戦略が指示する行動と異なる行動を0.03の確率で行う（偶然手番の導入）
Dを行うべきときに確率pでCを行う．（混合戦略） ゲームの繰り返し回数は200回

17 例３.１人vs不特定多数の繰り返しゲーム 警察官が不特定多数のドライバーに対して取り締まりを行う状況を仮定する．
警察官はT：取り締まる，N：放置するの２つの行動をとり，ドライバーはこれを知った上でS：慎重に運転する，D：無法運転をするという選択を行う． ドライバーは慎重に運転していても過失をp(0<p<0.5)の確率で行う（偶然手番と考える）

18 １回限りの取り締まりゲームの場合 ペイオフマトリックス
SS SD DS DD T：取り締まり 4-3p,3-2p 1,2 N：放置 4-p,3+p 2,4 0<p<0.5 (T,SD)，(N,DD)という２つの均衡点は警察が取り締まりを行うならば慎重に運転を行い，行わなければ違法運転を行うことを意味する．

19 繰り返し取り締まりゲームのシミュレーション
ドライバーが過失を起こす確率をα=0.1とする． 警察は定常戦略T,Nの他に，状態反応戦略A(a)を有する．aを超えたら取り締まる． 200回のシミュレーションを行った結果から平均利得を用いる． ：ドライバーが慎重に運転してもt-1回目までに起こす交通違反回数の期待値 ：ドライバーがt-1回目までに起こした交通違反回数 ＝

20 繰り返し取り締まりゲームのシミュレーション
シミュレーション結果の利得行列 SS SD DS DD T：取り締まり 3.73,2.82 1.00,2.00 A(1) 3.84,2.99 3.69,2.85 1.99,2.36 1.01,2.01 A(1.2) 3.91,3.09 3.67,2.87 A(3) 3.33,3.11 N：放置 2.00,4.00 (A(1.2),SS)は実際の交通違反回数が期待値の1.2倍を上回ったら取り締まりを行うという戦略． この時の均衡利得(3.91,3.09)はパレート最適で，常に取り締まるか取り締まらないかよりも望ましい戦略となっている．

21 フォークの定理 fork theory

22 繰り返しゲームの表現方法 成分ゲームG=(N,S,F) ただしNはプレイヤー集合，Sは戦略集合，Fは利得関数
繰り返される回数　成分ゲームGはT回繰り返される． 戦略　成分ゲームGの戦略を「行動」と，繰り返しゲームΓの戦略と区別して呼ぶことが多い． ゲームの経歴　t回目のプレイの結果をまとめてベクトルで示したもの(1≤t≤T) 平均利得と割引利得 平均利得 割引利得 rは割引率

23 フォークの定理 「１回限りの場合必ずしもパレート最適な利得が得られないゲームでも，無限回繰り返すことによって，パレート最適な利得を実現する戦略が存在する．」

24 保留点（ミニマックス点） 保留点（ミニマックス点）を以下のように定義する． 相手に対して最小プレイヤーかのごとく振る舞った場合に，相手の利得を抑えられうる最小の値．逆に言えばそのプレイヤーにとって最小限の利得として保留される値． なお，一般的にミニマックス値≥マックスミニ値になることが知られている．

25 個人合理的実現可能集合 無限繰り返しゲームΓの利得ベクトルxが保留点vをパレート支配するとき，xは個人合理的であるという．
ゲームΓの実現可能集合に属しつつ，個人合理的な利得ベクトルの集合を， 個人合理的実現可能集合という．

26 図解 左のゲームの保留点はv=(5,6)である．
P2 左のゲームの保留点はv=(5,6)である． 左下の図の個人合理的実現可能集 合内の任意の点が，部分ゲーム完 全均衡点をつくる戦略の組によっ て実現されることを保証するのが， フォークの定理である． 4,8 6,4 3,6 2,0 4,6 6,1 5,3 7,5 0,6 P1 ゲームΓの成分ゲーム v(5,6) 個人合理的実現可能集合 ゲームΓの実現可能集合

27 補足 - フォークの定理の成立条件 プレイヤーは将来の利得をあまり割り引かない．(rは十分0にちかい)
Siはユークリッド空間におけるコンパクトな部分集合である FiはS上の連続な実数値関数である． 成分ゲームGにおいて，混合戦略の範囲で考えた時の個人合理的集合はn次元である．この条件はn人ゼロ和ゲームでは実現可能集合はn-1次元だが，そのような場合を除くことを意味している．