６．大人数クラスの運営法 ゲーム理論 出席の取り方 まわし方（４通り） →出席表を２回まわす １回目１０：５０～ ２回目１１：２０～

Presentation on theme: "６．大人数クラスの運営法 ゲーム理論 出席の取り方 まわし方（４通り） →出席表を２回まわす １回目１０：５０～ ２回目１１：２０～"— Presentation transcript:

1 ６．大人数クラスの運営法 ゲーム理論 出席の取り方 まわし方（４通り） →出席表を２回まわす １回目１０：５０～ ２回目１１：２０～
所要時間：４０分 まわし方（４通り） Ｔ１（前,前），Ｔ２（前,後） Ｔ３（後,前），Ｔ４（後,後） 講義回数をＮ回とすると、Ｎ－１回以上の講義に出席すれば確実に単位を確保できる。 教授は、学生がサインをしたらすぐに教室を出て行ってしまうのを防ぐために、出席表を２回まわすことにする。 学生がａ～ｅのどこに座ればいかに教室にいる時間を減らせるかを調べようとするもの。 前提として、学生は出席表に２回サインした後直ちに席を立つことにする。 ａ～ｅのそれぞれの位置で、何分滞在しているかを調べると･･･

2 滞在時間 Ｔ１ Ｔ２ Ｔ３ Ｔ４ ａ ３５ ７５ ４５ ｂ ５５ ｃ ５０ ｄ ｅ Ｔ１（前，前）　Ｔ２（前，後）　Ｔ３（後，前）　Ｔ４（後，後） Ｔ１ Ｔ２ Ｔ３ Ｔ４ ｂ ３５ ５５ ｃ ５０ ｄ ａとｂを比較すると･･･ａに座るよりｂに座ったほうがどんな場合でも滞在時間が少ない ｄとｅを比較すると･･･ｅに座るよりｄに座ったほうがどんな場合でも滞在時間が少ない →ａとｅは削除できる⇒右の表 もし教授がサイコロを振って出席表の回し方を決めるとすると、Ｔ１，Ｔ２，Ｔ３，Ｔ４はそれぞれ１/４の確率で実現する。 ｂ，ｄは分散100　ｃは分散０　→スリルを好む人：ｂ，ｄ　安定を好む人：ｃ ⇒教授が、もしサイコロを使わずにゲーム理論、ここでは最も単純なゼロ和２人ゲームを取り上げるが、その前に･･･

3 前提 取り得る手の集合 Ｓ１＝ｂに座る Ｓ２＝ｃに座る Ｓ３＝ｄに座る Ｔ１＝（前，前） Ｔ２＝（前，後） Ｔ３＝（後，前）
Ｔ４＝（後，後） 学生がＳｊ、教授がＴｋを 選んだときの 学生の利得（教授の損失）ａｊｋを 学生が教室に座っていないで済む時間（分）　　　とする Ｔ１ Ｔ２ Ｔ３ Ｔ４ Ｓ１ ５５ ３５ Ｓ２ ４０ Ｓ３ 講義時間は９０分とする ９０－滞在時間＝学生が教室に座わっていないですむ時間

4 ゼロ和２人ゲーム 教授から学生への支払い行列は 学生の選ぶべき手（行：横を見ればよい） Ｓ２：最悪でも４０の利得（４０分は居なくてもよい）
Ｓ１，Ｓ３：運が悪いと３５しか利得が得られない（居なくてもよい時間が３５分しかない） ∴Ｓ２ 教授の選ぶ手（列：縦を見ればよい） Ｔ１とＴ３，Ｔ２とＴ４は全く同一であることがわかる →“２回目の出席表を前から回すか、後ろから回すか”だけが本質的 ⇒Ｔ３，Ｔ４を削除できる 教授はどちらの手を選んでも、損失５５なので、どちらも差がない。仮にＴ１を選ぶとする。 →学生は「教授がＴ１を選ぶ」ことが分かると４０から５０に利得を増やそうとしてＳ１に変更する。 →教授が「学生がＳ１を選ぶ」ことがわかると５５から３５に損失を減らそうとしてＴ２に変更する。 →それを知った学生はＳ３に変更→それを知った教授はＴ１に変更 ⇒このようにして、堂堂巡りをしてしまう ⇒混合戦略の考え方を導入することで、均衡解が得られる

5 混合戦略 学生のミニマクス戦略 学生がＳ１，Ｓ２，Ｓ３を選ぶ確率 →それぞれχ１，χ２，χ３とする 教授が Ｔ１を選んだ時の平均的利益→ｚ１
　　　→それぞれχ１，χ２，χ３とする 教授が 　　Ｔ１を選んだ時の平均的利益→ｚ１ 　　Ｔ２を選んだ時の平均的利益→ｚ２ 　とする 学生はｚ１とｚ２の最悪のケースを想定して 　　小さい方を最大にするχ１，χ２，χ３を選ぶ 混合戦略はどの戦略を確率を用いて決定する戦略のこと。 この場合は必ず均衡が存在する。 ゼロ和２人ゲーム（純粋戦略の１つ）は混合戦略の特殊なケースといえる。 混合戦略でχ＝（１，０，０）のような場合が純粋戦略である 「小さい方を最大にする」→このような作戦はミニマクス戦略と呼ばれている

6 定式化 目的関数：ｚ＝ｍｉｎ｛ｚ１，ｚ２｝ →最大化 制約条件： χ１＋χ２＋χ３＝１ ･･･①
目的関数：ｚ＝ｍｉｎ｛ｚ１，ｚ２｝　　→最大化 制約条件： χ１＋χ２＋χ３＝１　　　　　　 ･･･① 　ｚ１＝５５χ１＋４０χ２＋３５χ３　　　･･･②　　　 　ｚ２＝３５χ１＋４０χ２＋５５χ３　　　･･･③ 　χ１≧ ０，χ２≧ ０，χ３≧０ ①：確率は足すと１ ⇒①よりχ３＝１－χ１－χ２と変形し、②,③に代入し、χ３を消去する ｚ１＝３５＋２０χ１＋５χ２，ｚ２＝５５－２０χ１－１５χ２

7 変形後 目的関数：３５＋２０χ１＋５χ２ →最大化 制約条件： ２χ１＋χ２＝１ χ１＋χ２≦１ χ１≧０，χ２≧０
目的関数：３５＋２０χ１＋５χ２　→最大化 制約条件：　 ２χ１＋χ２＝１ χ１＋χ２≦１ χ１≧０，χ２≧０ ⇒χ１*＝　　，χ２*＝０，χ３*=　　，ｚ*＝４５ 暫定的にｚ１＝ｚ２という条件を追加 目的関数：ｚ１　→３５＋２０χ１＋５χ２ ３５＋２０χ１＋５χ２＝ｋとするとχ２＝－４χ１＋1/5ｋ－７ 制約条件： ｚ１＝ｚ２より、２χ１＋χ２＝１：線分PQ χ３=１－χ１－χ２≧０より、χ１＋χ２≦１ χ１≧０，χ２≧０ χ１＝１/２，χ３＝１/２より、コインを投げて表が出ればｂ，裏が出ればｄに座ればよいことがわかる

8 混合戦略 教授のマクシミン戦略 教授がＴ１，Ｔ２を選ぶ確率 →それぞれｙ１，ｙ２とする
　　→それぞれｙ１，ｙ２とする 学生がＳ１，Ｓ２，Ｓ３を選んだ時の平均損失　→それぞれｗ１，ｗ２，ｗ３とする 教授はｗ１，ｗ２，ｗ３の中で最大のものを 　　最小とするｙ１，ｙ２を選ぶ 「最大のものを最小にする」→このような作戦をマクシミン戦略という

9 定式化 目的関数：ｗ＝ｍａｘ｛ｗ１，ｗ２，ｗ３｝ →最小化 制約条件： ｙ１＋ｙ２＝１ ･･･① ｗ１＝５５ｙ１＋３５ｙ２ ･･･②
目的関数：ｗ＝ｍａｘ｛ｗ１，ｗ２，ｗ３｝　→最小化 制約条件： 　ｙ１＋ｙ２＝１　　　　　　　･･･① 　ｗ１＝５５ｙ１＋３５ｙ２　　　･･･② 　ｗ２＝４０ｙ１＋４０ｙ２　　　･･･③ 　ｗ３＝３５ｙ１＋５５ｙ２　　　･･･④ 　ｙ１≧０，ｙ２≧０ ⇒①よりｙ２＝１－ｙ１として、②～④に代入し、ｙ２を消去すると･･･

10 変形後 ｗ１＝２０ｙ１＋３５ ｗ２＝４０ ｗ３＝－２０ｙ１＋５５ 最大値を０≦ｙ１≦１のもとで 最小化
⇒ｙ１* ＝　　，ｙ２* ＝　　，ｗ* ＝４５ ｙ１≧０，ｙ２＝１－ｙ１≧０より０≦ｙ１≦１ ｙ１＝１/２，ｙ２＝１/２より、 ２回目の際にコインを投げて、 表が出たら前から、裏が出たら後ろから配れば、平均して４５の損失で済む。

11 均衡点 学生の平均利益 （ｙ１ ，ｙ２ ）＝（１/２，１/２） 教授の平均損失（χ１ ,χ２,χ３ ） ＝（1/2，0，1/2）
学生の平均利益　　（ｙ１ ，ｙ２ ）＝（１/２，１/２） →４５よりも増加できない 教授の平均損失（χ１ ,χ２,χ３ ） ＝（1/2，0，1/2） →４５よりも減少できない 平均利益：χ１,χ２,χ３をどのように選んでも、４５以上にはならない 平均損失：ｙ１,ｙ２を他の値に変更しても、４５よりも減少させることはできない よってもし相手の戦略を知ったとしても、自分の戦略を変える必要が無く、解は均衡する。 ミニマクス戦略→（χ１ *,χ２ *,χ３ *）のこと マクシミン戦略→（ｙ１ *,ｙ２ *）のこと

12 均衡点 学生，教授のどちらも自分の戦略は変えない 学生のミニマクス戦略(χ１*, χ２*,χ３*)
教授のマクシミン戦略(ｙ１*，ｙ２*，ｙ３*) を、出席ゲームの“均衡解”という 平均利益：χ１,χ２,χ３をどのように選んでも、４５以上にはならない 平均損失：ｙ１,ｙ２を他の値に変更しても、４５よりも減少させることはできない よってもし相手の戦略を知ったとしても、自分の戦略を変える必要が無く、解は均衡する。 ミニマクス戦略→（χ１ *,χ２ *,χ３ *）のこと マクシミン戦略→（ｙ１ *,ｙ２ *）のこと

13 一般化（ミニマクス戦略） としたとき ｚ＝ｍｉｎ｛ｚ１，･･･，ｚｎ｝を最大化する 確率ベクトル（χ１，･･･，χｍ）を選択
　　　　　　　　　　　　　　　　　　　　　　としたとき ｚ＝ｍｉｎ｛ｚ１，･･･，ｚｎ｝を最大化する 確率ベクトル（χ１，･･･，χｍ）を選択 これは線形計画問題に定式化できる。１次等式・不等式の制約条件の下で１次式を最大化する線形計画問題になるので、単体法を使って解くことができる。

14 線形計画問題に定式化 目的関数： ｚ →最大化 制約条件： ｚ≦ａ１１χ１＋･･･＋ａｍ１χｍ ｚ≦ａ１ｎχ１＋･･･＋ａｍｎχｍ
目的関数：　ｚ　→最大化 制約条件： 　ｚ≦ａ１１χ１＋･･･＋ａｍ１χｍ 　ｚ≦ａ１ｎχ１＋･･･＋ａｍｎχｍ 　χ１＋･･･＋χｍ＝１ 　χ１≧０,･･･,χｍ≧０

15 一般化（マクシミン戦略） 　　　　　　　　　　　　　　　　　　　としたとき ｗ＝ｍａｘ｛ｗ１，･･･，ｗｍ｝を最小化する 確率ベクトル（ｙ１，･･･，ｙｎ）を選択

16 線形計画問題に定式化 目的関数： ｗ →最小化 制約条件： ｗ≧ ａ１１ｙ１＋･･･＋ａ１ｎｙｎ ｗ≧ ａｍ１ｙ１＋･･･＋ａｍｎｙｎ
目的関数：　ｗ　→最小化 制約条件： 　ｗ≧ ａ１１ｙ１＋･･･＋ａ１ｎｙｎ 　ｗ≧ ａｍ１ｙ１＋･･･＋ａｍｎｙｎ 　ｙ１＋･･･＋ｙｎ＝１ 　ｙ１≧ ０，･･･，ｙｎ≧ ０

17 ミニマクス定理 線形計画問題に変形した２つの問題の 最適解をそれぞれ
(χ１*,･･･,χｍ*,ｚ*)，(ｙ１*,･･･,ｙｎ*,ｗ*)　とする ⇒ｗ* ＝ｚ* 　が成立 　（χ１* ，･･･，χｍ* ），（ｙ１* ，･･･，ｙｎ* ）が 　　　　　　　　　それぞれの“均衡戦略”となる これら２つの線形計画問題は双対問題である