ゲーム理論第三部 知的都市基盤工学 5 月 30 日 ( 水 5 限 (6:30~8:0
再掲 : 囚人のジレンマ 囚人のジレンマの利得行列 協調 (Cooperte:C プレイヤー 裏切 (Deect:D ( 協調 = 黙秘 裏切 = 自白 プレイヤー C 3,3 4, D,4, 右がプレイヤー の利得左がプレイヤー の利得 ナッシュ均衡点 プレイヤーの合理的な意思決定の結果 (C,C はナッシュ均衡ではない
再掲 : 無限繰り返し囚人のジレンマ 3 4 δ ( δ / ll-c である場合の最適反応戦略 プレイヤー のプレイヤー に対する最適反応戦略 プレイヤー のプレイヤー に対する最適反応戦略 ( δ = / の場合の最適反応戦略 プレイヤー ll-d しっぺ返し プレイヤー ll-c 3,3, 4 3,3 ll-d 4, 4 δ, +δ しっぺ返し 3, 3 3,3 ただし 表中の値は全て δ 倍してある, + δ,4 δ つのナッシュ均衡
フォークの定理 無限繰り返し囚人のジレンマ 3 つの戦略 ll-c, ll-d, しっぺ返しの中から つを選択可能な場合 ナッシュ均衡 { (ll-d, ll-d, ( しっぺ返し, しっぺ返し (ll-d, ll-d 3 4 δ ( δ / 3 4 δ < ( δ </ 回限りのゲームのナッシュ均衡戦略に含まれない行動の組 (C,C の系列が無限繰り返しゲームのナッシュ均衡に含まれる 無限の戦略集合を仮定した場合 ( 一般的な場合に拡大 回限りのゲームのナッシュ均衡戦略に含まれない行動の組 (C,C の系列が無限繰り返しゲームのナッシュ均衡に含まれるか? フォークの定理
ミニマックス行動 定義 ミニマックス行動 戦略形ゲーム G においてプレイヤー に対するミニマックス行動とは mx (, m を満たすプレイヤー の行動ミニマックス利得という m プレイヤー のミニマックス行動 mnmx (, のことで 右辺の値をプレイヤー の プレイヤー が最適反応原理に基づいて選択した行動に対してプレイヤー の利得を最小化するプレイヤー の行動 プレイヤー のミニマックス利得 プレイヤー がミニマックス行動を選択した場合のプレイヤー の利得 プレイヤー が最適反応原理によって行動を選択した場合に最低限獲得可能な利得 ( 保障水準
ミニマックス行動 囚人のジレンマ プレイヤー のミニマックス利得とプレイヤー のミニマックス行動 プレイヤー プレイヤー C D 3, 3 4 C, D, 4, プレイヤー がミニマックス行動 D を選択すれば プレイヤー はミニマックス利得 以上の利得を獲得できない mn mx (, = mn[mx( 3,4, mx(,] = = mn [4,] プレイヤー の C, D に対するプレイヤー の最適反応 プレイヤー が D を選択してプレイヤー の利得を最小化 プレイヤー のミニマックス行動 同様にプレイヤー のミニマックス行動 プレイヤー の :D : ミニマックス利得 プレイヤー の :D : ミニマックス利得 ミニマックス利得の組 (,
個人合理的 定義 プレイヤーの行動の組 が成立するとき 行動の組 = (, プレイヤー とプレイヤー のミニマックス利得 個人合理的 ( v が成立するときをいう > = (, が個人合理的であるとは v ( v ( v ( > v に対して は強く個人合理的であるという
個人合理的 囚人のジレンマにおける個人合理的な行動の組 ミニマックス利得の組 (, 個人合理的な行動の組の条件を満たす利得の組 個人合理的な行動の組 強く個人合理的な場合 (3,3 (C,C 上の利得ベクトルは含まない 強く個人合理的な行動の組の条件を満たす利得の組 (3,3 (, (D,D (, プレイヤー C C 3,3 プレイヤー D 4, (,4 (, ミニマックス利得の組 (, D,4, 個人合理的利得ベクトル集合 (3,3 (4, 強く個人合理的な行動の組 (C,C プレイヤー の利得
フォークの定理 定理 成分ゲーム G の強く個人合理的な任意の行動の組 に対して将来利得の割引因子 δ が 存在して が成り立つ フォークの定理 δ mx mx (, ( を満たせば 繰り返しゲーム * ( s = (,, ( v * * * G のナッシュ均衡点 s = ( s, s,..., =, (, 無限繰り返しゲームのナッシュ均衡の中の一つに強く個人合理的な行動の組を毎回実現する均衡点が存在 = が
フォークの定理 定理 の証明 トリガー戦略 規則 規則 s *, s * 相手のプレイヤーだけが強く個人合理的な任意の行動の 組 = (, ミニマックス行動 の定義 から離脱すれば 以後相手に対する m, m に従う, 上記の場合以外は強く個人合理的な任意の行動 をとる 繰り返し囚人のジレンマでのトリガー戦略 相手が D を出すまで 自分は常に C を出し続ける ( 初回は C を出す 一度相手が D を出せば それ以降のゲームではそれ以降の相手の行動に関係なく D を出し続ける
フォークの定理 定理 の証明 Cse プレイヤー プレイヤー がトリガー戦略を選択 初回からお互いに強く個人合理的な行動を取り続け どちらもそこから離脱することがないので * ( s = が実現する (,,... お互いにトリガー戦略から変更しなかった場合のプレイヤー の t 回目以降の割引利得和は + δ ( +... = である. ( δ (
フォークの定理 3 定理 の証明 Cse プレイヤー が戦略をトリガー戦略 から異なる戦略に変更 プレイヤー は t 回目のゲームでと異なる行動をとる. このとき トリガー戦略の定義から プレイヤー は t + 回目以降のゲームで * s プレイヤー に対するミニマックス行動をとり続ける. 戦略を変更したプレイヤー の t 回目以降の割引利得和は (, + δ v + δ v +... = (, + v である. t 回目の利得 δ δ t+ 回目以降の割引利得和
フォークの定理 4 定理 の証明 3 プレイヤー の t 回目以降の割引利得和 トリガー戦略からの変更に関して 行動 Cse ( 変更しない に対して ならば トリガー戦略 : ( δ δ * s ( Cse : ( 変更した (, + v (, δ + v δ から他の戦略へ変更しても割引利得和を増やせない δ δ プレイヤー のトリガー戦略はプレイヤー のトリガー戦略に対する最適反応戦略 トリガー戦略がナッシュ均衡戦略 プレイヤー とプレイヤー の両方に対して成立
フォークの定理 5 定理 の証明 4 v δ δ δ +, ( ( v, ( mx (, ( mx δ (, ( mx, ( mx ( v δ v δ δ +, ( mx, ( mx ( v δ δ +, ( mx ( ( v δ δ δ +, ( mx ( 右辺を最大化するについても成り立つ (, (,,, ( = 式変形式変形
フォークの定理 6 囚人のジレンマ 強く個人合理的な行動の組 (C,C 割引因子 δの条件 mx (, δ, =, ナッシュ均衡点の実現する行動の組の系列に * t ( s = (,...,,... = (( C, C,..., ( C, C,... が含まれる mx (, 4 3 δ 4 + v = ( が成り立つ場合 フォークの定理 プレイヤー C C 3,3 プレイヤー D 4, (,4 (, ミニマックス利得の組 (, D,4, 個人合理的利得ベクトル集合 (3,3 (4, プレイヤー の利得
再掲 : 無限繰り返し囚人のジレンマ 3 3 4 δ < ( δ </ の場合 プレイヤー : しっぺ返しプレイヤー : ll-d の場合の割引利得和のとる範囲 ( +δ,4 δ プレイヤー の利得 (,4 (, ナッシュ均衡 お互いしっぺ返しの場合の割引利得和 (3,3 (4, プレイヤー ( 4 δ, + δ の利得プレイヤー : ll-d プレイヤー : しっぺ返しの場合の割引利得和のとる範囲 しっぺ返しに対する ll-d の割引利得和 > 4 δ しっぺ返しに対するしっぺ返しの割引利得和 しっぺ返しを選択する誘因がない 3
再掲 : 無限繰り返し囚人のジレンマ 4 3 4 δ ( δ / の場合 プレイヤー : しっぺ返しプレイヤー : ll-d の場合の割引利得和のとる範囲 ( +δ,4 δ プレイヤー の利得 (,4 (, ナッシュ均衡 お互いしっぺ返しの場合の割引利得和 (3,3 ナッシュ均衡 (4, しっぺ返しに対する ll-d の割引利得和 > 4 δ しっぺ返しに対するしっぺ返しの割引利得和 3 しっぺ返しを選択する誘因が発生 プレイヤー ( 4 δ, + δ の利得プレイヤー : ll-d プレイヤー : しっぺ返しの場合の割引利得和のとる範囲
フォークの定理 7 トリガー戦略以外でも強く個人合理的な行動の組 (C,C の系列は ナッシュ均衡戦略により実現可能か? 強く個人合理的な行動の組 (C,C からの離脱に対してミニマックス行動 D を選択する戦略との対戦 ex. しっぺ返し戦略 強く個人合理的な戦略の組に留まる誘因発生の条件 離脱により得られる利得 > + 強い個人合理的な戦略の組から離脱しない場合の割引利得和 強い個人合理的な戦略の組から離脱してミニマックス行動を選択された場合の割引利得和 割引因子 δ が十分に大きいと成立 強く個人合理的な行動の組 (C,C の系列が実現可能
有限繰り返しゲームのナッシュ均衡 有限繰り返しゲーム 繰り返し回数が有限 = 未来に対する不確実がない 割引因子 δ は導入しない 定理 成分ゲーム G が唯一のナッシュ均衡点 もつとき 任意の繰り返し回数 T に対して T 回繰り返しゲーム である ( s * = ( e, e,..., e e = ( e, e T * * * G のナッシュ均衡点 s = ( s, s を は
有限繰り返しゲームのナッシュ均衡 定理 の証明 後ろ向き帰納法で証明 T = の場合 回限りのゲームと同様であるので繰り返しゲームのナッシュ均衡点は成分ゲームのナッシュ均衡点と一致する T = の場合 定理 は成立する
有限繰り返しゲームのナッシュ均衡 3 定理 の証明 T の場合 T 回目のゲーム ( 最後の一回のゲーム 以降のゲームに影響を与えないので T- 回目までのゲームの履歴にかかわらず 回限りのゲームと同様に扱うことができる 合理的な行動の結果は成分ゲーム G のナッシュ均衡 T- 回目のゲーム T 回目のゲームでは既に行動が決定していて T- 回目のゲームは T 回目のゲームに影響を与えない T- 回目までのゲームの履歴にかかわらず T- 回目のゲームも 回限りのゲームと同様に扱うことができる 合理的な行動の結果は成分ゲーム G のナッシュ均衡
有限繰り返しゲームのナッシュ均衡 4 定理 の証明 3 T の場合 回目のゲーム 回目のゲームでも既に行動が成分ゲームのナッシュ均衡戦略と決定していて 回目のゲームは 回目のゲームに影響を与えない 回目のゲームも 回限りのゲームと同様に扱うことができる 合理的な行動の結果は成分ゲーム G のナッシュ均衡 したがって T の場合 毎回のゲームにおけるナッシュ均衡点は成分ゲームのナッシュ均衡点と一致する
有限繰り返しゲームのナッシュ均衡 5 T =,T において定理 が成立しているので 定理 成分ゲーム G が唯一のナッシュ均衡点 もつとき 任意の繰り返し回数 T に対して T 回繰り返しゲーム である ( s * = ( e, e,..., e e = ( e, e T * * * G のナッシュ均衡点 s = ( s, s を は が成立する
有限繰り返しゲームのナッシュ均衡 6 有限繰り返し囚人のジレンマ 定理 の仮定 成分ゲームのナッシュ均衡点が唯一 一回限りの囚人のジレンマのナッシュ均衡点は 定理 の仮定を満たす ( D, D で唯一 有限繰り返し囚人のジレンマのナッシュ均衡 ( s * = (,..., t = (( D, D,..., ( D, D 毎回成分ゲームの均衡点 (D,D が繰り返される
繰り返し囚人のジレンマコンテスト 前述の繰り返し囚人のジレンマの分析 ゲーム全体を俯瞰する立場からの考察 ex. 複数のナッシュ均衡点 フォークの定理 プレイヤー個人の立場からの考察有限繰り返し囚人のジレンマナッシュ均衡戦略 :ll-d 高い利得を獲得できるか? お互いにDを選択すれば お互いCよりも低い利得 実際に繰り返し囚人のジレンマをおこなう場合 どのような戦略を選択すればよいのだろうか? 繰り返し囚人のジレンマコンテスト [Axelrod 984] 複数の戦略プログラムの総当たり対戦
繰り返し囚人のジレンマコンテスト 第 回コンテストの概要 プレイヤー ルール 結果 心理学 経済学 政治学 数学 社会学の分野に属する 4 名に作成されたプログラム + ランダムプログラム 総当り対戦 各対戦は 00 回繰り返しを 5 回おこなう 評価 対戦で得られた利得の合計 優勝 しっぺ返しの戦略 コンテストで用いられた利得行列 上位を占めた戦略の特徴自分から裏切らない = 上品さ (nce キングメーカーの存在 C D C 3,3 4, D,4, 相手が裏切っても再び協調し合える = 心の広さ (orgveness
繰り返し囚人のジレンマコンテスト 3 第 回コンテストの概要 プレイヤー ルール 結果 前回の分野 + コンピュータサイエンス 物理学等の分野に属する 6 名に作成されたプログラム + ランダムプログラム 前回のルール + 繰り返し回数の確率的変動 第 回コンテストの結果を踏まえた参加プログラムの つの傾向. 上品で心が広いプログラム ( しっぺ返しの戦略の踏襲. のようなプログラムから搾取を狙うプログラム 同士では協調 同士で裏切り合い 優勝 しっぺ返しの戦略 上位を占めた戦略の特徴 上品で心が広い 傾向 前回と同様 非協調的な相手 (ex. ll-d には裏切り
繰り返し囚人のジレンマコンテスト 4 最近の研究 プレイヤー 各戦略毎に種 ルール 結果 前回のルール + 繰り返し回数の確率的変動 高い利得を獲得した種が増加する tness 関数 優性種の交代