6.大人数クラスの運営法 ゲーム理論 出席の取り方 まわし方(4通り) →出席表を2回まわす 1回目10:50~ 2回目11:20~ 所要時間:40分 まわし方(4通り) T1(前,前),T2(前,後) T3(後,前),T4(後,後) 講義回数をN回とすると、N-1回以上の講義に出席すれば確実に単位を確保できる。 教授は、学生がサインをしたらすぐに教室を出て行ってしまうのを防ぐために、出席表を2回まわすことにする。 学生がa~eのどこに座ればいかに教室にいる時間を減らせるかを調べようとするもの。 前提として、学生は出席表に2回サインした後直ちに席を立つことにする。 a~eのそれぞれの位置で、何分滞在しているかを調べると・・・
滞在時間 T1 T2 T3 T4 a 35 75 45 b 55 c 50 d e T1(前,前) T2(前,後) T3(後,前) T4(後,後) T1 T2 T3 T4 b 35 55 c 50 d aとbを比較すると・・・aに座るよりbに座ったほうがどんな場合でも滞在時間が少ない dとeを比較すると・・・eに座るよりdに座ったほうがどんな場合でも滞在時間が少ない →aとeは削除できる⇒右の表 もし教授がサイコロを振って出席表の回し方を決めるとすると、T1,T2,T3,T4はそれぞれ1/4の確率で実現する。 b,dは分散100 cは分散0 →スリルを好む人:b,d 安定を好む人:c ⇒教授が、もしサイコロを使わずにゲーム理論、ここでは最も単純なゼロ和2人ゲームを取り上げるが、その前に・・・
前提 取り得る手の集合 S1=bに座る S2=cに座る S3=dに座る T1=(前,前) T2=(前,後) T3=(後,前) T4=(後,後) 学生がSj、教授がTkを 選んだときの 学生の利得(教授の損失)ajkを 学生が教室に座っていないで済む時間(分) とする T1 T2 T3 T4 S1 55 35 S2 40 S3 講義時間は90分とする 90-滞在時間=学生が教室に座わっていないですむ時間
ゼロ和2人ゲーム 教授から学生への支払い行列は 学生の選ぶべき手(行:横を見ればよい) S2:最悪でも40の利得(40分は居なくてもよい) S1,S3:運が悪いと35しか利得が得られない(居なくてもよい時間が35分しかない) ∴S2 教授の選ぶ手(列:縦を見ればよい) T1とT3,T2とT4は全く同一であることがわかる →“2回目の出席表を前から回すか、後ろから回すか”だけが本質的 ⇒T3,T4を削除できる 教授はどちらの手を選んでも、損失55なので、どちらも差がない。仮にT1を選ぶとする。 →学生は「教授がT1を選ぶ」ことが分かると40から50に利得を増やそうとしてS1に変更する。 →教授が「学生がS1を選ぶ」ことがわかると55から35に損失を減らそうとしてT2に変更する。 →それを知った学生はS3に変更→それを知った教授はT1に変更 ⇒このようにして、堂堂巡りをしてしまう ⇒混合戦略の考え方を導入することで、均衡解が得られる
混合戦略 学生のミニマクス戦略 学生がS1,S2,S3を選ぶ確率 →それぞれχ1,χ2,χ3とする 教授が T1を選んだ時の平均的利益→z1 →それぞれχ1,χ2,χ3とする 教授が T1を選んだ時の平均的利益→z1 T2を選んだ時の平均的利益→z2 とする 学生はz1とz2の最悪のケースを想定して 小さい方を最大にするχ1,χ2,χ3を選ぶ 混合戦略はどの戦略を確率を用いて決定する戦略のこと。 この場合は必ず均衡が存在する。 ゼロ和2人ゲーム(純粋戦略の1つ)は混合戦略の特殊なケースといえる。 混合戦略でχ=(1,0,0)のような場合が純粋戦略である 「小さい方を最大にする」→このような作戦はミニマクス戦略と呼ばれている
定式化 目的関数:z=min{z1,z2} →最大化 制約条件: χ1+χ2+χ3=1 ・・・① 目的関数:z=min{z1,z2} →最大化 制約条件: χ1+χ2+χ3=1 ・・・① z1=55χ1+40χ2+35χ3 ・・・② z2=35χ1+40χ2+55χ3 ・・・③ χ1≧ 0,χ2≧ 0,χ3≧0 ①:確率は足すと1 ⇒①よりχ3=1-χ1-χ2と変形し、②,③に代入し、χ3を消去する z1=35+20χ1+5χ2,z2=55-20χ1-15χ2
変形後 目的関数:35+20χ1+5χ2 →最大化 制約条件: 2χ1+χ2=1 χ1+χ2≦1 χ1≧0,χ2≧0 目的関数:35+20χ1+5χ2 →最大化 制約条件: 2χ1+χ2=1 χ1+χ2≦1 χ1≧0,χ2≧0 ⇒χ1*= ,χ2*=0,χ3*= ,z*=45 暫定的にz1=z2という条件を追加 目的関数:z1 →35+20χ1+5χ2 35+20χ1+5χ2=kとするとχ2=-4χ1+1/5k-7 制約条件: z1=z2より、2χ1+χ2=1:線分PQ χ3=1-χ1-χ2≧0より、χ1+χ2≦1 χ1≧0,χ2≧0 χ1=1/2,χ3=1/2より、コインを投げて表が出ればb,裏が出ればdに座ればよいことがわかる
混合戦略 教授のマクシミン戦略 教授がT1,T2を選ぶ確率 →それぞれy1,y2とする →それぞれy1,y2とする 学生がS1,S2,S3を選んだ時の平均損失 →それぞれw1,w2,w3とする 教授はw1,w2,w3の中で最大のものを 最小とするy1,y2を選ぶ 「最大のものを最小にする」→このような作戦をマクシミン戦略という
定式化 目的関数:w=max{w1,w2,w3} →最小化 制約条件: y1+y2=1 ・・・① w1=55y1+35y2 ・・・② 目的関数:w=max{w1,w2,w3} →最小化 制約条件: y1+y2=1 ・・・① w1=55y1+35y2 ・・・② w2=40y1+40y2 ・・・③ w3=35y1+55y2 ・・・④ y1≧0,y2≧0 ⇒①よりy2=1-y1として、②~④に代入し、y2を消去すると・・・
変形後 w1=20y1+35 w2=40 w3=-20y1+55 最大値を0≦y1≦1のもとで 最小化 ⇒y1* = ,y2* = ,w* =45 y1≧0,y2=1-y1≧0より0≦y1≦1 y1=1/2,y2=1/2より、 2回目の際にコインを投げて、 表が出たら前から、裏が出たら後ろから配れば、平均して45の損失で済む。
均衡点 学生の平均利益 (y1 ,y2 )=(1/2,1/2) 教授の平均損失(χ1 ,χ2,χ3 ) =(1/2,0,1/2) 学生の平均利益 (y1 ,y2 )=(1/2,1/2) →45よりも増加できない 教授の平均損失(χ1 ,χ2,χ3 ) =(1/2,0,1/2) →45よりも減少できない 平均利益:χ1,χ2,χ3をどのように選んでも、45以上にはならない 平均損失:y1,y2を他の値に変更しても、45よりも減少させることはできない よってもし相手の戦略を知ったとしても、自分の戦略を変える必要が無く、解は均衡する。 ミニマクス戦略→(χ1 *,χ2 *,χ3 *)のこと マクシミン戦略→(y1 *,y2 *)のこと
均衡点 学生,教授のどちらも自分の戦略は変えない 学生のミニマクス戦略(χ1*, χ2*,χ3*) 教授のマクシミン戦略(y1*,y2*,y3*) を、出席ゲームの“均衡解”という 平均利益:χ1,χ2,χ3をどのように選んでも、45以上にはならない 平均損失:y1,y2を他の値に変更しても、45よりも減少させることはできない よってもし相手の戦略を知ったとしても、自分の戦略を変える必要が無く、解は均衡する。 ミニマクス戦略→(χ1 *,χ2 *,χ3 *)のこと マクシミン戦略→(y1 *,y2 *)のこと
一般化(ミニマクス戦略) としたとき z=min{z1,・・・,zn}を最大化する 確率ベクトル(χ1,・・・,χm)を選択 としたとき z=min{z1,・・・,zn}を最大化する 確率ベクトル(χ1,・・・,χm)を選択 これは線形計画問題に定式化できる。1次等式・不等式の制約条件の下で1次式を最大化する線形計画問題になるので、単体法を使って解くことができる。
線形計画問題に定式化 目的関数: z →最大化 制約条件: z≦a11χ1+・・・+am1χm z≦a1nχ1+・・・+amnχm 目的関数: z →最大化 制約条件: z≦a11χ1+・・・+am1χm z≦a1nχ1+・・・+amnχm χ1+・・・+χm=1 χ1≧0,・・・,χm≧0
一般化(マクシミン戦略) としたとき w=max{w1,・・・,wm}を最小化する 確率ベクトル(y1,・・・,yn)を選択
線形計画問題に定式化 目的関数: w →最小化 制約条件: w≧ a11y1+・・・+a1nyn w≧ am1y1+・・・+amnyn 目的関数: w →最小化 制約条件: w≧ a11y1+・・・+a1nyn w≧ am1y1+・・・+amnyn y1+・・・+yn=1 y1≧ 0,・・・,yn≧ 0
ミニマクス定理 線形計画問題に変形した2つの問題の 最適解をそれぞれ (χ1*,・・・,χm*,z*),(y1*,・・・,yn*,w*) とする ⇒w* =z* が成立 (χ1* ,・・・,χm* ),(y1* ,・・・,yn* )が それぞれの“均衡戦略”となる これら2つの線形計画問題は双対問題である