2014/5/22
鞍点のないゲーム
純粋戦略・・・ある1つの戦略を確定的に選択
マキシミン、ミニマックス ⇒ 最適戦略（鞍点）
鞍点・・・自分の最適戦略が相手も最適戦略
次のゲームの最適戦略は？
P2の戦略
B1
B2
A1
5
2
P1の
戦略
A2
3
4
P1の戦略（マキシミン）・・・A1：2、A2：3 ⇒ A2
P2の戦略（ミニマックス）・・・B1：5、B2：4 ⇒ B2
しかし、お互いに相手の戦略は分かっている
鞍点のないゲーム ~続き~
P1の
戦略
A1
A2
① P2の戦略がB2ならP1は戦略（A2）の変更不要
② P1の戦略がA2ならP2は戦略B1への変更が有利
③ P2が戦略をB1に変更することは予測できるので、P1は
戦略をA1に変更した方が有利
④ この行動も予想できるのでP2は戦略をB2に変更する
・・・
⇒ 純粋戦略では最適戦略が定まらない（鞍点がない）
混合戦略
鞍点のないゲームでは、複数の戦略を確率的に混合
して期待利得（期待損失）の最大化（最小化）をはかる
P1が戦略（A1, A2）をとる確率：（p1, p2）・・・p1+p2=1
P2が戦略（B1, B2）をとる確率：（q1, q2）・・・q1+q2=1
P1の
戦略
A1（p1）
A2（p2）
P2の戦略
B1（q1）
B2（q2）
5
2
3
4
P1の期待利得が最大になる確率（p1, p2）を定める
P2の期待損失が最小になる確率（q1, q2）を定める
P1の戦略～続き～
q1、q2は未知なので最悪の場合を想定する
(1) 3 + 2p1 < 4－2p1 のとき、（つまり、p1 < 1/4 ）
q1=1、q2=0で最小期待利得 3 + 2p1 となる
(2) 3 + 2p1 > 4－2p1 のとき、（つまり、p1 > 1/4 ）
q1=0、q2=1で最小期待利得 4－2p1 となる
したがって、最小期待利得zは
p1 < 1/4 のとき、 z = 3 + 2p1
p1 > 1/4 のとき、 z = 4－2p1
この利得が最大になるようなp1を求める
マクシミンより
P1の戦略： A2
ミニマックスより
P2の戦略： B2
P2の戦略
B1
B2
5
2
3
4
P1の戦略
 P1の期待利得
P2の戦略がB1のとき
利得1＝5 p1 + 3 p2＝5 p1 + 3 (1 - p1)＝3 + 2 p1
P2の戦略がB2のとき
利得2＝2 p1 + 4 p2＝ 2 p1 + 4 (1 - p1)＝4 - 2 p1
P2がB1、B2を選択する確率はq1、q2なので
期待利得＝利得1 x q1 + 利得2 x q2
＝(3 + 2 p1) q1 + (4 - 2 p1) q2
最小期待利得の最大化
zを縦軸、p1を横軸として最小期待利得を図示する
右の図より2つの直線の交点で最大となる
3 + 2p1＝ 4－2p1
z
z = 3+2p1
∴ p1＝ 1/4
4
このときの利得は、
z ＝3 + 2×(1/4)＝3.5
5
3.5
3
z = 4－2p1 2
0
1/4
P1の最適戦略は、
戦略（A1, A2）を確率( p1, p2 )=( 1/4, 3/4 ) でとる
このとき、期待利得は3.5
p1
1
1
2014/5/22
P2の戦略
 P2の期待損失
P1がA1をとったとき
5q1+2q2=5q1+2(1-q1)=2+3q1
P2の戦略～続き～
P1の A1: p1
戦略 A2: p
2
P2の戦略
B1: q1 B2: q2
5
2
3
4
(2) 2+3q1 > 4－q1 のとき、 (つまり、q1 > 1/2)
p1=1、p2=0で最大損失 2+3q1 となる
P1がA2をとったとき
3q1+4q2=3q1+4(1-q1)=4 - q1
したがって、最大期待損失zは
q1 < 1/2 のとき、 z = 4－q1
q1 > 1/2 のとき、 z = 2 + 3q1
この損失が最小になるようなq1を求める
P1がA1、A2を選択する確率はp1、p2なので
期待損失= (2+3q1) p1 + (4 - q1) p2
最大損失の最小化
ミニマックス定理
右の図より2つの直線の交点で最小となる
3q1 + 2＝ 4－q1
z = 2+3q1 5
∴ q1＝ 1/2
4
3.5
3
このときの利得は、
z = 4 －q1
2
z ＝ 4－1/2＝3.5
q1
0
p1、p2は未知なので、最悪の場合を想定する
(1) 2+3q1 < 4－q1 のとき、 (つまり、q1 < 1/2)
p1=0、p2=1で最大損失 4－q1 となる
1/2
1
P2の最適戦略は、
戦略（B1, B2）を確率(q1, q2)=(1/2, 1/2)でとる
このとき、期待損失は3.5
 ２人定和ゲームが鞍点を持つならば純粋戦
略により最適戦略を求めることができる。
 鞍点が存在しない場合でも、混合戦略を許せ
ば、各プレイヤーの最適戦略は必ず存在し、
ゲームの値zを求めることができる。
⇒ 相手がどのような戦略をとろうとも期待利得
（損失）はz以上（以下）となる。
ジョン・フォン・ノイマン
練習1
混合戦略により次のゲームにおける解を求めよ。
P1の
戦略
A1: p1
A2: p2
P2の戦略
B1: q1 B2: q2
1
3
5
2
練習2
次のゲームにおいて
（１）両者ともA3を選択することはないことを示せ
（２）このゲームが完全決定的でないことを示せ
（３）混合戦略によりゲームの解を求めよ
A1: p1
P1の
A2: p2
戦略
A3: p3
P2の戦略
A1: q1 A2: q2 A3: q3
70, 30 55, 45 71, 29
55, 45 70, 30 75, 25
51, 49 35, 65 70, 30
2

Download Report