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

Slides:



Advertisements
Similar presentations
最上 亮.  近年標的型と呼ばれるサイバー攻撃が増え、大 企業や、政府機関が情報窃取型の標的型メール 攻撃の被害を受けている。  標的型メール攻撃による個人情報漏えいは、企 業に莫大な損失を与えるとともに、信頼を失う。  現在サイバー攻撃における攻撃者、防御者の戦 略をゲーム理論的にモデル化する研究がおこな.
Advertisements

ゲーム理論の誕生と発展 von Neumann & Morgenstern The Theory of Games and Economic Behavior.
新ゲーム理論 第Ⅰ部 非協力ゲームの理論 第2章 戦略形ゲームのナッシュ均衡
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
ゲーム理論・ゲーム理論Ⅰ(第2回) 第2章 戦略形ゲームの基礎
人工知能概論 第4回 探索(3) ゲームの理論.
内容 部分ゲーム完全均衡点 -部分ゲーム -部分ゲーム完全均衡点 -2段階完全情報ゲーム シュタッケルベルク均衡点
ゲーム理論・ゲーム理論Ⅰ (第4回) 第3章 完全情報の展開形ゲーム
シミュレーション論Ⅰ 第13回 意思決定とシミュレーション.
ゲーム理論・ゲーム理論Ⅰ (第8回) 第5章 不完全競争市場の応用
© Yukiko Abe 2014 All rights reserved
上級価格理論II 第3回 2011年後期 中村さやか.
ゲーム理論・ゲーム理論Ⅰ (第6回) 第4章 戦略形ゲームの応用
「生き残り競争」から抜け出したい! -ゲーム理論入門- 東京国際大学オープンキャンパス (2014年8月23日) 経済学部体験授業
新ゲーム理論ゼミ 第5章 「繰り返しゲーム」 M1 松村 草也.
第四回 線形計画法(2) 混合最大値問題 山梨大学.
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
Extremal Combinatorics 14.1 ~ 14.2
初級ミクロ経済学 -ゲーム理論入門- 2014年12月19日 古川徹也 2014/12/19.
法と経済学(file 6) ゲーム理論2 今日の講義の目的 (1)展開型ゲームという考え方を理解する (2)後方帰納法の考え方を理解する
10.Private Strategies in Games with Imperfect Public Monitoring
政策決定のプロセス 政策過程論 公共選択 ゲームの理論.
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
初級ミクロ経済学 -ゲーム理論入門- 2014年12月15日 古川徹也 2014年12月15日 初級ミクロ経済学.
ゲーム理論・ゲーム理論Ⅰ(第3回) 第2章 戦略形ゲームの基礎
評価関数を用いた エージェント間の交渉 5月28日 河目 瞬
確率・統計輪講資料 6-5 適合度と独立性の検定 6-6 最小2乗法と相関係数の推定・検定 M1 西澤.
データ構造と アルゴリズム 知能情報学部 新田直也.
集団における適応 知識構造論講座 下嶋研究室          M1 関本 和弘.
『企業と市場のシミュレーション』 井庭 崇 第12回: 貨幣の自生と自壊モデル
ネットワーク上を拡散する 技術革新のシミュレーション 日本大学文理学部 情報システム解析学科 谷研究室 安藤勇希 帆苅裕貴
第Ⅲ部 ゲーム理論の役割と歴史 第17章 ゲーム理論の役割 2008/07/01(火) ゲーム理論合宿 井上麻衣子.
慶應義塾大学経済学部 グレーヴァ香子 Takako Fujiwara-Greve
新ゲーム理論 第Ⅰ部 非協力ゲームの理論 第1章 非協力ゲームの戦略形
第13章 フォンノイマン/モルゲンシュテイン解
シミュレーション論Ⅰ 第11回 意思決定とシミュレーション.
第Ⅱ部 協力ゲームの理論 第9章 シャープレイ値.
第Ⅱ部 協力ゲームの理論 第7章 交渉問題 2008/07/01(火) ゲーム理論合宿 M1 北川直樹.
一橋大学大学院経済学研究科 岡田 章(おかだ あきら)
シミュレーション論 Ⅱ 第14回 まとめ.
シミュレーション論 Ⅱ 第15回 まとめ.
応用社会システム計画 (第10回) ここで、学習すること 学籍番号: 氏名: ■これまでの講義内容の整理 ■計画問題の設定と手法
数学 ---> 抽象化、一般化 より複雑な関係ー>解析学 一次関数 y=ax+b より多くの要素ー>線形代数 x y f(x) y1 x1
第3回 確率変数の平均 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
6.大人数クラスの運営法 ゲーム理論 出席の取り方 まわし方(4通り) →出席表を2回まわす 1回目10:50~ 2回目11:20~
独立成分分析 1.問題は何か:例:解法:全体の見通し 2007/10/17 名雪 勲.
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
第Ⅱ部 協力ゲームの理論 第10章 コア 2008/07/01(火) ゲーム理論合宿.
線 形 代 数 (linear algebra) linear ・・・ line(直線)の形容詞形 直線的な、線形の、一次の
意外と身近なゲーム理論 へなちょこ研究室 p.
25. Randomized Algorithms
第Ⅱ部 協力ゲームの理論 第16章 破産問題 2008/07/02(水) ゲーム理論合宿 M1 浦田淳司.
母分散の信頼区間 F分布 母分散の比の信頼区間
今井 浩 東京大学情報理工学系研究科 コンピュータ科学専攻 ERATO今井量子計算機構プロジェクト,JST
第Ⅱ部 協力ゲームの理論 第11章 仁(nucleolus) 2008/07/02(水) ゲーム理論合宿 M1 浦田淳司 nucleolus
4. システムの安定性.
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
問題作成、解説担当:中島 副担当:坪坂、松本
第Ⅱ部 協力ゲームの理論 第7章 提携形ゲームと配分 2008/07/01(火) ゲーム理論合宿 M1 藤井敬士.
第16章 動的計画法 アルゴリズムイントロダクション.
ORの手法ゲームの理論3 (Excelによるゲーム理論実習)
第Ⅱ部 協力ゲームの理論 第14章 交渉集合.
確率と統計2007(最終回) 平成20年1月17日(木) 東京工科大学 亀田弘之.
or-8. ゲーム理論 (オペレーションズリサーチを Excel で実習するシリーズ)
囚人のジレンマ ―― 裏切りのインセンティブ ――
第Ⅰ部 非協力ゲームの理論 第6章 情報の価値 2008/07/01(火) ゲーム理論合宿 M2 渡辺美穂.
割り当て問題(assignment problem)
人工知能概論 第4回 探索(3) ゲームの理論.
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
Presentation transcript:

パソコンでゲームの理論 第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