パソコンでゲームの理論 第1,2章 ゼロ和2人ゲーム ゼミ合宿 東京理科大学理学部第2部数学科・統計学ゼミ 日時:2002年9月14日(土)~16日(月) 場所:下部ホテル(山梨県西八代郡下部町) ゼミ合宿 パソコンでゲームの理論 第1,2章 ゼロ和2人ゲーム 梅原嘉介・F.シャオ 日本評論社(1997) 東京理科大学 理学部第2部数学科4年 谷口伸也 (2199123) 田村潤一 (2199126) 小川 勝 (2198044) (2198351) 吉岡秀雄 (2198415) 2018/11/7
Contents ゲーム理論の概略 ゼロ和2人ゲーム 純粋戦略 混合戦略 線形計画法による一般解法 まとめ 今後の発展 参考文献 ミニマックス原理 ナッシュ均衡 混合戦略 線形計画法による一般解法 利得行列の変換 コード紹介 まとめ 今後の発展 参考文献 ゲーム理論といえば、第74回アカデミー賞・最優秀作品賞を受賞した『ビューティフルマインド』に触れないわけにはいかない。一般の人に、ゲーム理論、ナッシュ教授を紹介した極めて異例な好作品であった。 ゲーム理論の概略 1 ゼロ和2人ゲーム 1+1 純粋戦略 (1)ナッシュ均衡 2+2 最適反応戦略 ナッシュ均衡 純粋戦略 (2)ミニマックス定理 2+2 マックスミニ/ミニマックス戦略 ミニマックス定理 混合戦略 2+2 ナッシュ均衡とミニマックス定理 1 まとめ 1 10 2018/11/7
1.ゲーム理論の概略 ゲーム理論とは? 協力ゲームと非協力ゲーム J. von Neumann & O.Morgenstern Theory of Games and Economic Behavior (1944)が起源。 意思決定のための理論 ただし、他の複数の人間が、どのような意思決定を行ってくるかを考慮し意識しつつ、そのなかで、自らが合理的な意思決定を行う。 協力ゲームと非協力ゲーム 非協力ゲーム 競争状態にある当事者が、話し合いなどなく、独自に意思決定を行う場合。 値下げ競争、じゃんけん、囲碁将棋など。 協力ゲーム 当事者間の話し合いを許し、共同行動を考慮する場合。 入札談合(⇒公正取引委員会の監視)、CO2排出取引など。 今回は、こちら 2018/11/7
2.ゼロ和2人ゲーム (1)ゲームのルール ゲームのルール プレイヤーの数は2人。 登場人物は2人で、その2名が意思決定を行う。 ゲームの結果についての2人のプレイヤーの利得の和は常にゼロ。 勝者の利得が ならば、敗者の利得は で合計0。 各プレイヤーのとりうる戦略の数は有限。 有限なので数学的取り扱いが楽(行列表現、確率ベクトルなど)。 ゲームは1回限りである。 各プレイヤーが、1つの戦略を提示して、ゲームの結果が決まり、終了。 相手がどの戦略を採用してくるかはわからない。 戦略は、同時に提示するものと考える。 2人ゼロ和 2018/11/7
2.ゼロ和2人ゲーム (2)構成要素と行列表現 ゲームの構成要素 ゲームの行列表現 プレイヤー:意思決定主体 戦略:選択した行動 利得:結果、評価・得点 ゲームの行列表現 2人ゼロ和でない場合は、プレイヤー別の利得行列が必要。 2人ゼロ和の場合は、一方の利得行列があればOK。 図表① Aから見た利得行列 B 戦略1 戦略2 A -1 +3 +2 +4 図表② Bから見た利得行列 A 戦略1 戦略2 B +1 -2 -3 -4 2018/11/7
2.ゼロ和2人ゲーム まとめ ここからは、ゼロ和2人ゲームに話を限定します。 しばらくの間、戦略は2つづつとした2×2利得行列で考察します。 最後に、一般のm×n利得行列の場合の線形計画法を利用した解法を取り上げます。 2018/11/7
3.純粋戦略 ゲームの解(game solution) TypeⅠの場合 TypeⅡの場合 妥協点を探るための概念 A:Aの利得の最大化 B:Aの利得の最小化 を目指したときの妥協点。 TypeⅠの場合 ゲームの解(値)が存在する。 TypeⅡの場合 ゲームの解(値)が存在しない。 妥協点を探るための概念 ミニマックス原理 ナッシュ均衡 TypeⅠ B 戦略1 戦略2 A -1 +3 +2 +4 TypeⅡ B 戦略1 戦略2 A -1 +3 +2 +1 2018/11/7
3.純粋戦略 a.ミニマックス原理 マックスミニ戦略 Aにとっての戦略選択法。 ① Aの各戦略に対し、Bが最善の戦略で応じた場合のAの最小利得を算出。 ② Aの最小利得の中でも最大の利得の値をマックスミニ値( )。 Aがとる戦略(Aの利得最大化)↑ ↑Bの最善な戦略(Aの利得最小化) TypeⅠ B Aの 最小利得 戦略1 j =1 戦略2 j =2 A 戦略1 i =1 -1 +3 戦略2 i =2 +2 +4 < < < 2018/11/7
3.純粋戦略 a.ミニマックス原理 ミニマックス戦略 Bにとっての戦略選択法。 ① Bの各戦略に対し、Aが最善の戦略で応じた場合のAの最大利得を算出。 ② Aの最大利得の中でも最小の利得の値をミニマックス値( )。 Bがとる戦略(Aの利得最小化)↑ ↑Aの最善な戦略(Aの利得最大化) TypeⅠ B 戦略1 j =1 戦略2 j =2 A 戦略1 i =1 -1 +3 戦略2 i =2 +2 +4 Aの最大利得 < < < 2018/11/7
3.純粋戦略 a.ミニマックス原理 ゲームの値が定まる場合(ミニマックス原理) マックスミニ値=ミニマックス値なら、お互いの妥協点が一致。 TypeⅠ B Aの 最小利得 戦略1 j =1 戦略2 j =2 A 戦略1 i =1 -1 +3 戦略2 i =2 +2 +4 Aの最大利得 2018/11/7
3.純粋戦略 a.ミニマックス原理 ゲームの値が定まらない場合もあり 一般には、マックスミニ値≦ミニマックス値が成り立つ(証明略)。 マックスミニ値=ミニマックス値ならゲームの値は定まる。 マックスミニ値<ミニマックス値ならゲームの値は定まらない。 TypeⅡ B Aの 最小利得 戦略1 j =1 戦略2 j =2 A 戦略1 i =1 -1 +3 戦略2 i =2 +2 +1 Aの最大利得 2018/11/7
3.純粋戦略 b.ナッシュ均衡 最適反応戦略 ナッシュ均衡 戦略1 戦略1 戦略2 戦略2 ⇒ 相手のある戦略のもとで、自らの利得を最大にする戦略。 ナッシュ均衡 ⇒ お互いに自分のとる戦略が相手のとる戦略に対する最適反応戦略になっている場合。 ゼロ和2人ゲームでは、ナッシュ均衡はゲームの解を確定させる。 TypeⅠ B 戦略1 戦略2 A -1 +3 +2 +4 ナッシュ均衡 Aが戦略1を選択するとき Bは戦略1が最適反応戦略 ① 戦略1 戦略1 ③ ② ④ 戦略2 戦略2 2018/11/7
3.純粋戦略 b.ナッシュ均衡 ナッシュ均衡がない場合 戦略1 戦略1 戦略2 戦略2 どこからスタートしても、矢印を追っていくと、一筆書きになってしまう。 ゲームの値は定まらない。 TypeⅡ B 戦略1 戦略2 A -1 +3 +2 +1 ① 戦略1 戦略1 ③ ④ 戦略2 戦略2 ② 2018/11/7
⇔ マックスミニ値=ミニマックス値 ナッシュ均衡が存在する 3.純粋戦略 まとめ 混合戦略の導入 ゼロ和2人ゲームが解けるためには? 実は、純粋戦略では解けなくても、混合戦略まで考えれば解ける。 ⇒次章にて、議論。 マックスミニ値=ミニマックス値 ⇔ ナッシュ均衡が存在する 2018/11/7
4.混合戦略 確率概念の導入 混合戦略とは、選択する戦略を確率的に決定する方法。 両者とも事前に相手の戦略を知らないという前提なので、独立となり、積の法則から、下表のような2次元確率分布で考察することが可能。 2×2混合戦略時の確率分布表 B 戦略1 q1 = q 戦略2 q2 = 1-q A p1 = p p1×q1 = p ×q p1×q2 = p ×(1-q) p2 = 1-p p2×q1 =(1-p)×q p2×q2 = (1-p)×(1-q) 2018/11/7
4.混合戦略 期待利得(EA)の計算 各利得値にそこでの確率を乗じて合計する。 B 戦略1 q1 = q 戦略2 q2 = 1-q A TypeⅡ(上)と確率分布(下) B 戦略1 q1 = q 戦略2 q2 = 1-q A p1 = p -1 p × q +3 p ×(1-q) p2 = 1-p +2 (1-p)× q +1 (1-p)×(1-q) 2018/11/7
4.混合戦略 Aの最適反応戦略 Bの最適反応戦略 EA ∀p EA ∀q Bの戦略選択確率(q)に対して、期待利得(EA)を最大化するAの戦略選択確率(p)を求める。 Bの最適反応戦略 Aの戦略選択確率(p)に対して、期待利得(EA)を最小化するBの戦略選択確率(q)を求める。 Case *1 q p EA ① >0 <2/5 p=1 -4q+3 ② =0 =2/5 ∀p 7/5 ③ <0 >2/5 p=0 q+1 Case *2 p q EA ① >0 <1/5 q=0 2p+1 ② =0 =1/5 ∀q 7/5 ③ <0 >1/5 q=1 -3p+2 2018/11/7
4.混合戦略 期待利得(EA)の最大化 期待利得(EA)の最小化 Case q p EA ① <2/5 p=1 -4q+3 ② =2/5 ∀p 7/5 ③ >2/5 p=0 q+1 Case p q EA ① <1/5 q=0 2p+1 ② =1/5 ∀q 7/5 ③ >1/5 q=1 -3p+2 ナッシュ均衡 p=1/5, q=2/5 交点は、互いに相手の戦略に対する最適反応戦略になっているので、ナッシュ均衡となる。 q TypeⅡ ① ③ ② ① ③ ② B 戦略1 戦略2 A -1 +3 +2 +1 p
ゼロ和2人ゲームは必ず解ける! 4.混合戦略 まとめ 省略したこと 「必ず解ける」とかいいつつ、一般の場合の証明にはなっていません。 TypeⅠのように、解が純粋戦略で表現できる場合も、本章の枠組みで解いた解と一致する。ある戦略に確率1、それ以外の戦略に確率0が割り振られるだけ。 2×2ではなく、一般のm×n利得行列については、線形計画法の枠組みで解くことができる。 ⇒次章にて紹介。 ゼロ和2人ゲームは必ず解ける! 2018/11/7
5.線形計画法による一般解法 a.利得行列の変換 アルゴリズムの考え方 A:混合戦略、B:純粋戦略とする。 Bがどの戦略を選択してきても、 以上の利得が得られるとすれば、この を最大化するような混合戦略を見つけることを考える。 一般的な利得行列 B 戦略1 戦略2 ・・・ 戦略n A 戦略1 p1 a11 a12 a1n 戦略2 p2 a21 a22 a2n 戦略m pm am1 am2 amn 2018/11/7
5.線形計画法による一般解法 a.利得行列の変換 線形計画法の枠組みへ であることが必要であるが、行列要素を なるようにしてから解けばよい。 2018/11/7
5.線形計画法による一般解法 b.コード紹介 混合戦略におけるTypeⅡの例で取り上げた2×2利得行列に関するサンプル 2018/11/7
5.線形計画法による一般解法 b.コード紹介 因みに、SASで線形計画法を実行するには、 SAS/OR にあるLPプロシージャを利用できる。 SAS/OR がない場合は、SAS/IML のサンプルプログラムに線形計画法があるので利用できる。 2018/11/7
ゼロ和2人ゲームは必ず解ける! ナッシュ均衡とミニマックス原理 一般には、線形計画法の流用で 6.まとめ ゼロ和2人ゲームは必ず解ける! ナッシュ均衡とミニマックス原理 一般には、線形計画法の流用で 2018/11/7
7.今後の発展 非ゼロ和ゲーム 協力ゲーム 展開型ゲーム 情報の非対称問題 2018/11/7
8.参考文献 梅原嘉介・F.シャオ, 『パソコンでゲームの理論』, 日本評論社, 武藤滋夫, 『ゲーム理論入門』, 日本経済新聞社, 212p,(1997) 本発表のための指定教科書だが、あまり参考としなかった。 武藤滋夫, 『ゲーム理論入門』, 日本経済新聞社, 242p,(2001) ナッシュ均衡からミニマックス定理へと展開される好書。 鈴木光男,『ゲーム理論入門』,共立出版, 270p,(1981) 一般のm×n利得行列を線形計画法で解く方法は、こちらの本を参考にして、Mathematica でコーディングを行った。 2018/11/7
2018/11/7
3.非ゼロ和2人ゲーム(参考) (1)恋人の語らい 図表① A(男)の利得行列 図表② B(女)の利得行列 B 女 サッカー 映画 A 男 +2 -1 -2 +1 A 男 サッカー 映画 B 女 +1 -2 -1 +2 恋人の語らい型ゲーム 一緒に行動したほうが、お互いに利得が大きい。 しかし、お互いに好みが異なるので、どちらかが妥協しないとプラスの利得が得られない。 実際には相談(協力)して決めるから大丈夫? 図表③ 恋人の語らい利得双行列 B 女 サッカー 映画 A 男 (+2,+1) (-1,-1) (-2,-2) (+1,+2) 足してゼロでないから非ゼロ和。 2018/11/7
3.非ゼロ和2人ゲーム(参考) (2)囚人のジレンマ 図表① (囚人)Aの利得行列(刑期) 図表② (囚人)Bの利得行列(刑期) 囚人 B 黙秘 自白 A -2 -9 -1 -5 囚人 A 黙秘 自白 B -2 -9 -1 -5 囚人のジレンマ型ゲーム 2人の囚人は、別々の監獄にいて相談は不可能とする。司法取引は想定する。 お互いに黙秘が最大の利得であるが、どちらかが裏切るという可能性を孕んでいる。 図表③ 囚人のジレンマ利得双行列 囚人 B 黙秘 自白 A (-2,-2) (-9,-1) (-1,-9) (-5,-5) 2018/11/7