パソコンでゲームの理論 第1,2章 ゼロ和２人ゲーム ゼミ合宿 東京理科大学理学部第２部数学科・統計学ゼミ

Presentation on theme: "パソコンでゲームの理論 第1,2章 ゼロ和２人ゲーム ゼミ合宿 東京理科大学理学部第２部数学科・統計学ゼミ"— Presentation transcript:

1 パソコンでゲームの理論 第1,2章 ゼロ和２人ゲーム ゼミ合宿 東京理科大学理学部第２部数学科・統計学ゼミ
日時：2002年9月14日（土）～16日（月） 場所：下部ホテル（山梨県西八代郡下部町） ゼミ合宿 パソコンでゲームの理論 第1,2章 ゼロ和２人ゲーム 梅原嘉介・Ｆ．シャオ 日本評論社(1997) 東京理科大学 理学部第２部数学科４年 　　谷口伸也 （ ） 　田村潤一 （ ） 　　小川　勝 （ ） 　　　　　 （ ） 　　吉岡秀雄 （ ） 2018/11/7

2 Contents ゲーム理論の概略 ゼロ和２人ゲーム 純粋戦略 混合戦略 線形計画法による一般解法 まとめ 今後の発展 参考文献
ミニマックス原理 ナッシュ均衡 混合戦略 線形計画法による一般解法 利得行列の変換 コード紹介 まとめ 今後の発展 参考文献 ゲーム理論といえば、第74回アカデミー賞・最優秀作品賞を受賞した『ビューティフルマインド』に触れないわけにはいかない。一般の人に、ゲーム理論、ナッシュ教授を紹介した極めて異例な好作品であった。 ゲーム理論の概略 1 ゼロ和２人ゲーム 1+1 純粋戦略 (1)ナッシュ均衡 2+2 最適反応戦略 ナッシュ均衡 純粋戦略 (2)ミニマックス定理 2+2 マックスミニ／ミニマックス戦略 ミニマックス定理 混合戦略 2+2 ナッシュ均衡とミニマックス定理 1 まとめ 1 10 2018/11/7

3 1.ゲーム理論の概略 ゲーム理論とは？ 協力ゲームと非協力ゲーム J. von Neumann & O.Morgenstern
Theory of Games and Economic Behavior (1944)が起源。 意思決定のための理論 ただし、他の複数の人間が、どのような意思決定を行ってくるかを考慮し意識しつつ、そのなかで、自らが合理的な意思決定を行う。 協力ゲームと非協力ゲーム 非協力ゲーム 競争状態にある当事者が、話し合いなどなく、独自に意思決定を行う場合。 値下げ競争、じゃんけん、囲碁将棋など。 協力ゲーム 当事者間の話し合いを許し、共同行動を考慮する場合。 入札談合（⇒公正取引委員会の監視）、CO2排出取引など。 今回は、こちら 2018/11/7

4 2.ゼロ和２人ゲーム (1)ゲームのルール ゲームのルール プレイヤーの数は２人。
登場人物は２人で、その２名が意思決定を行う。 ゲームの結果についての２人のプレイヤーの利得の和は常にゼロ。 勝者の利得が　 ならば、敗者の利得は　　 で合計０。 各プレイヤーのとりうる戦略の数は有限。 有限なので数学的取り扱いが楽（行列表現、確率ベクトルなど）。 ゲームは１回限りである。 各プレイヤーが、１つの戦略を提示して、ゲームの結果が決まり、終了。 相手がどの戦略を採用してくるかはわからない。 戦略は、同時に提示するものと考える。 ２人ゼロ和 2018/11/7

5 2.ゼロ和２人ゲーム (2)構成要素と行列表現 ゲームの構成要素 ゲームの行列表現 プレイヤー：意思決定主体 戦略：選択した行動
利得：結果、評価・得点 ゲームの行列表現 ２人ゼロ和でない場合は、プレイヤー別の利得行列が必要。 ２人ゼロ和の場合は、一方の利得行列があればＯＫ。 図表① Ａから見た利得行列 Ｂ 戦略１ 戦略２ Ａ -1 +3 +2 +4 図表② Ｂから見た利得行列 Ａ 戦略１ 戦略２ Ｂ +1 -2 -3 -4 2018/11/7

6 2.ゼロ和２人ゲーム まとめ ここからは、ゼロ和２人ゲームに話を限定します。 しばらくの間、戦略は２つづつとした２×２利得行列で考察します。
最後に、一般のｍ×ｎ利得行列の場合の線形計画法を利用した解法を取り上げます。 2018/11/7

7 3.純粋戦略 ゲームの解（game solution） TypeⅠの場合 TypeⅡの場合 妥協点を探るための概念 Ａ：Ａの利得の最大化
Ｂ：Ａの利得の最小化 を目指したときの妥協点。 TypeⅠの場合 ゲームの解(値)が存在する。 TypeⅡの場合 ゲームの解(値)が存在しない。 妥協点を探るための概念 ミニマックス原理 ナッシュ均衡 TypeⅠ Ｂ 戦略１ 戦略２ Ａ -1 +3 +2 +4 TypeⅡ Ｂ 戦略１ 戦略２ Ａ -1 +3 +2 +1 2018/11/7

8 3.純粋戦略 a.ミニマックス原理 マックスミニ戦略 Ａにとっての戦略選択法。
① Ａの各戦略に対し、Ｂが最善の戦略で応じた場合のＡの最小利得を算出。 ② Ａの最小利得の中でも最大の利得の値をマックスミニ値（　）。 Ａがとる戦略（Ａの利得最大化）↑ ↑Ｂの最善な戦略（Ａの利得最小化） TypeⅠ Ｂ Ａの 最小利得 戦略１ j =1 戦略２ j =2 Ａ 戦略１ i =1 -1　 +3　 戦略２ i =2 +2　 +4　 ＜ ＜ ＜ 2018/11/7

9 3.純粋戦略 a.ミニマックス原理 ミニマックス戦略 Ｂにとっての戦略選択法。
① Ｂの各戦略に対し、Ａが最善の戦略で応じた場合のＡの最大利得を算出。 ② Ａの最大利得の中でも最小の利得の値をミニマックス値（　）。 Ｂがとる戦略（Ａの利得最小化）↑ ↑Ａの最善な戦略（Ａの利得最大化） TypeⅠ Ｂ 戦略１ j =1 戦略２ j =2 Ａ 戦略１ i =1 -1　 +3　 戦略２ i =2 +2　 +4　 Ａの最大利得 ＜ ＜ ＜ 2018/11/7

10 3.純粋戦略 a.ミニマックス原理 ゲームの値が定まる場合（ミニマックス原理） マックスミニ値＝ミニマックス値なら、お互いの妥協点が一致。
TypeⅠ Ｂ Ａの 最小利得 戦略１ j =1 戦略２ j =2 Ａ 戦略１ i =1 -1　 +3　 戦略２ i =2 +2　 +4　 Ａの最大利得 2018/11/7

11 3.純粋戦略 a.ミニマックス原理 ゲームの値が定まらない場合もあり 一般には、マックスミニ値≦ミニマックス値が成り立つ（証明略）。
マックスミニ値＝ミニマックス値ならゲームの値は定まる。 マックスミニ値＜ミニマックス値ならゲームの値は定まらない。 TypeⅡ Ｂ Ａの 最小利得 戦略１ j =1 戦略２ j =2 Ａ 戦略１ i =1 -1　 +3　 戦略２ i =2 +2　 +1　 Ａの最大利得 2018/11/7

12 3.純粋戦略 b.ナッシュ均衡 最適反応戦略 ナッシュ均衡 戦略１ 戦略１ 戦略２ 戦略２
⇒ 相手のある戦略のもとで、自らの利得を最大にする戦略。 ナッシュ均衡 ⇒ お互いに自分のとる戦略が相手のとる戦略に対する最適反応戦略になっている場合。 ゼロ和２人ゲームでは、ナッシュ均衡はゲームの解を確定させる。 TypeⅠ Ｂ 戦略１ 戦略２ Ａ -1 +3 +2 +4 ナッシュ均衡 Ａが戦略１を選択するとき Ｂは戦略１が最適反応戦略 ① 戦略１ 戦略１ ③ ② ④ 戦略２ 戦略２ 2018/11/7

13 3.純粋戦略 b.ナッシュ均衡 ナッシュ均衡がない場合 戦略１ 戦略１ 戦略２ 戦略２
どこからスタートしても、矢印を追っていくと、一筆書きになってしまう。 ゲームの値は定まらない。 TypeⅡ Ｂ 戦略１ 戦略２ Ａ -1 +3 +2 +1 ① 戦略１ 戦略１ ③ ④ 戦略２ 戦略２ ② 2018/11/7

14 ⇔ マックスミニ値＝ミニマックス値 ナッシュ均衡が存在する 3.純粋戦略 まとめ 混合戦略の導入 ゼロ和２人ゲームが解けるためには？
実は、純粋戦略では解けなくても、混合戦略まで考えれば解ける。 ⇒次章にて、議論。 マックスミニ値＝ミニマックス値 ⇔ ナッシュ均衡が存在する 2018/11/7

15 4.混合戦略 確率概念の導入 混合戦略とは、選択する戦略を確率的に決定する方法。
両者とも事前に相手の戦略を知らないという前提なので、独立となり、積の法則から、下表のような２次元確率分布で考察することが可能。 ２×２混合戦略時の確率分布表 Ｂ 戦略１ q1 = q 戦略２ q2 = 1-q Ａ 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

16 4.混合戦略 期待利得（ＥＡ）の計算 各利得値にそこでの確率を乗じて合計する。 Ｂ 戦略１ q1 = q 戦略２ q2 = 1-q Ａ
TypeⅡ（上）と確率分布（下） Ｂ 戦略１ q1 = q 戦略２ q2 = 1-q Ａ p1 = p -1 　p × q +3 　p ×(1-q) p2 = 1-p +2 (1-p)× q +1 (1-p)×(1-q) 2018/11/7

17 4.混合戦略 Ａの最適反応戦略 Ｂの最適反応戦略 ＥＡ ∀p ＥＡ ∀q
Ｂの戦略選択確率（ｑ）に対して、期待利得（ＥＡ）を最大化するＡの戦略選択確率（ｐ）を求める。 Ｂの最適反応戦略 Ａの戦略選択確率（ｐ）に対して、期待利得（ＥＡ）を最小化するＢの戦略選択確率（ｑ）を求める。 Case *1 q p ＥＡ ① >0 <2/5 p=1 -4q+3 ② =0 =2/5 ∀p 7/5 ③ <0 >2/5 p=0 q+1 Case *2 p q ＥＡ ① >0 <1/5 q=0 2p+1 ② =0 =1/5 ∀q 7/5 ③ <0 >1/5 q=1 -3p+2 2018/11/7

18 4.混合戦略 期待利得（ＥＡ）の最大化 期待利得（ＥＡ）の最小化 Case q p ＥＡ ① <2/5 p=1 -4q+3 ②
=2/5 ∀p 7/5 ③ >2/5 p=0 q+1 Case p q ＥＡ ① <1/5 q=0 2p+1 ② =1/5 ∀q 7/5 ③ >1/5 q=1 -3p+2 ナッシュ均衡 ｐ=1/5, ｑ=2/5 交点は、互いに相手の戦略に対する最適反応戦略になっているので、ナッシュ均衡となる。 ｑ TypeⅡ ① ③ ② ① ③ ② Ｂ 戦略１ 戦略２ Ａ -1 +3 +2 +1 ｐ

19 ゼロ和２人ゲームは必ず解ける！ 4.混合戦略 まとめ 省略したこと 「必ず解ける」とかいいつつ、一般の場合の証明にはなっていません。
TypeⅠのように、解が純粋戦略で表現できる場合も、本章の枠組みで解いた解と一致する。ある戦略に確率１、それ以外の戦略に確率０が割り振られるだけ。 ２×２ではなく、一般のｍ×ｎ利得行列については、線形計画法の枠組みで解くことができる。 ⇒次章にて紹介。 ゼロ和２人ゲームは必ず解ける！ 2018/11/7

20 5.線形計画法による一般解法 a.利得行列の変換
アルゴリズムの考え方 Ａ：混合戦略、Ｂ：純粋戦略とする。 Ｂがどの戦略を選択してきても、　以上の利得が得られるとすれば、この　を最大化するような混合戦略を見つけることを考える。 一般的な利得行列 Ｂ 戦略１ 戦略２ ･･･ 戦略ｎ Ａ 戦略１　p1 a11 a12 a1n 戦略２　p2 a21 a22 a2n 戦略ｍ　pm am1 am2 amn 2018/11/7

21 5.線形計画法による一般解法 a.利得行列の変換
線形計画法の枠組みへ 　　　　であることが必要であるが、行列要素を なるようにしてから解けばよい。 2018/11/7

22 5.線形計画法による一般解法　b.コード紹介 混合戦略におけるTypeⅡの例で取り上げた２×２利得行列に関するサンプル 2018/11/7

23 5.線形計画法による一般解法　b.コード紹介 　因みに、SASで線形計画法を実行するには、 SAS/OR にあるLPプロシージャを利用できる。 SAS/OR がない場合は、SAS/IML のサンプルプログラムに線形計画法があるので利用できる。 2018/11/7

24 ゼロ和２人ゲームは必ず解ける！ ナッシュ均衡とミニマックス原理 一般には、線形計画法の流用で
6.まとめ ゼロ和２人ゲームは必ず解ける！ ナッシュ均衡とミニマックス原理 一般には、線形計画法の流用で 2018/11/7

25 7.今後の発展 非ゼロ和ゲーム 協力ゲーム 展開型ゲーム 情報の非対称問題 2018/11/7

26 8.参考文献 梅原嘉介・Ｆ.シャオ, 『パソコンでゲームの理論』, 日本評論社, 武藤滋夫, 『ゲーム理論入門』, 日本経済新聞社,
２１２ｐ,（１９９７） 本発表のための指定教科書だが、あまり参考としなかった。 武藤滋夫, 『ゲーム理論入門』, 日本経済新聞社, ２４２ｐ,（２００１） ナッシュ均衡からミニマックス定理へと展開される好書。 鈴木光男，『ゲーム理論入門』，共立出版， ２７０ｐ，(１９８１) 一般のｍ×ｎ利得行列を線形計画法で解く方法は、こちらの本を参考にして、Mathematica でコーディングを行った。 2018/11/7

27 2018/11/7

28 3.非ゼロ和２人ゲーム(参考) (1)恋人の語らい
図表① Ａ(男)の利得行列 図表② Ｂ(女)の利得行列 Ｂ 女 ｻｯｶｰ 映画 Ａ 男 +2 -1 -2 +1 Ａ 男 ｻｯｶｰ 映画 Ｂ 女 +1 -2 -1 +2 恋人の語らい型ゲーム 一緒に行動したほうが、お互いに利得が大きい。 しかし、お互いに好みが異なるので、どちらかが妥協しないとプラスの利得が得られない。 実際には相談(協力)して決めるから大丈夫？ 図表③ 恋人の語らい利得双行列 Ｂ 女 ｻｯｶｰ 映画 Ａ 男 (+2,+1) (-1,-1) (-2,-2) (+1,+2) 足してゼロでないから非ゼロ和。 2018/11/7

29 3.非ゼロ和２人ゲーム(参考) (2)囚人のジレンマ
図表① (囚人)Ａの利得行列(刑期) 図表② (囚人)Ｂの利得行列(刑期) 囚人 Ｂ 黙秘 自白 Ａ -2 -9 -1 -5 囚人 Ａ 黙秘 自白 Ｂ -2 -9 -1 -5 囚人のジレンマ型ゲーム ２人の囚人は、別々の監獄にいて相談は不可能とする。司法取引は想定する。 お互いに黙秘が最大の利得であるが、どちらかが裏切るという可能性を孕んでいる。 図表③ 囚人のジレンマ利得双行列 囚人 Ｂ 黙秘 自白 Ａ (-2,-2) (-9,-1) (-1,-9) (-5,-5) 2018/11/7