今日の目標 今日習う主な事項 ゲームの混合拡大

2006年度システム基礎資料　高橋　真吾
今日の目標
• 混合戦略の意味を理解する。
• ミニマックス定理を理解する。
• 非協力ゲームの形式を理解する。
2006年度
システム基礎
第９回
ゲーム理論入門（２）
高橋 真吾
2
今日習う主な事項
ゲームの混合拡大
鞍点のない場合
„ 混合戦略
„ ミニマックス定理
„ ゲームを解く
確率の導入
„ 非協力ゲーム
3
4
1
2006年度システム基礎資料　高橋　真吾
混合戦略
純戦略の集合
Π 1 = {i | i = 1,2,
ゼロ和２人ゲームの利得関数
, m}
Π 2 = { j | j = 1,2,
, n}
E( p, q) = pAqT = a11 p1q1 + a12 p1q2 + + amn pmqn
1つの戦略
p = ( p1 , p 2 , … , p m )
混合戦略
s.t. p i ≥ 0, p1 + p 2 +
+ pm = 1
⎛ a11
⎜
A = (a ij ) = ⎜
⎜a
⎝ m1
q = (q1 , q 2 , … , q n )
s.t. q j ≥ 0, q1 + q 2 +
＊純戦略は混合戦略の特殊形
+ qm = 1
a1n ⎞
⎟
⎟
a mn ⎟⎠
⎛ q1 ⎞
⎜ ⎟
q =⎜ ⎟
⎜q ⎟
⎝ n⎠
T
i≡ p=(0,…,0,1,0,…,0)
5
ミニマックス定理
混合拡大による一般的ゲーム表現
< N ; {Si }i∈N ; { f i }i∈N > 一般的なゲーム表現
max min pAqT = min max pAqT
混合拡大
< N ;{Qi }i∈N ;{Fi }i∈N >
N
プレーヤ集合
Qi
Si 上の確率分布の集合
Fi
プレーヤiの期待利得関数
Fi : ∏ Gi → R
6
p∈Q1q∈Q2
7
q∈Q2 p∈Q1
8
2
2006年度システム基礎資料　高橋　真吾
ミニマックス定理
ゼロ和２人ゲームを解く
max min pAqT = min max pAqT
p∈Q1q∈Q2
1. 行列の鞍点を調べる
q∈Q2 p∈Q1
存在する
均衡点：上式を満たす戦略（一意とは限らない）
→
存在しない →
最適戦略，ゲームの値を求める
混合拡大
ゲームの値：均衡点における利得（一意に決まる）
ゲームを解く：均衡点とゲームの値を求めること
混合拡大においては均衡点は少なくとも一つ存在
9
ゼロ和２人ゲームを解く
10
⎛ 2 −1 ⎞
⎜
⎟
⎝3 4 ⎠
2. 均衡点を求める
2 −1
3 4
E ( p, q ) = p1q1 − p1 (1 − q1 ) − (1 − p1 )q1 + (1 − p1 )(1 − q1 )
p1 q1に関し線形⇒1または0で最適値
E ( p, (1, 0)) = 2 p1 − 1
E
3 4
E ( p, (0,1)) = −2 p1 + 1
交点が均衡点
⎛1 1⎞
( p1∗ , p2∗ ) = ⎜ , ⎟
⎝2 2⎠
⎛1 1⎞
(q1∗ , q2∗ ) = ⎜ , ⎟
⎝2 2⎠
3
−1
3
3
均衡点：(2,1)
ゲームの値＝3
p
11
12
3
2006年度システム基礎資料　高橋　真吾
⎛ −3 1 ⎞
⎜
⎟
⎝ 1 −5 ⎠
E ( p, q) = −3 p1q1 + p1 (1 − q1 ) + (1 − p1 )q1 − 5(1 − p1 )(1 − q1 )
E ( p,(1,0)) = −4 p1 + 1
−3 1 −3
−3
1 −5 −5
E ( p,(0,1)) = 6 p1 − 5
E ( p,(1,0)) = E ( p,(0,1))
⎛3 2⎞
( p1 , p2 ) = ⎜ , ⎟
⎝5 5⎠
同様に
E ((1,0), q ) = E ((0,1), q) とおいて
1 1
1
混合拡大
13
E ( p, e2 ) = 2 p1 − p2
E ( p, e3 ) = 4 p1 + 2 p2
E ( p, e4 ) = − p1 + 3 p2
E ( p, e5 ) =
3 p2
E ( p, e2 ) = E ( p, e4 )
E ( p, e1 )
( p∗ , q∗ )
E ( p, e3 )
E ( p, e5 )
E ( p, e4 )
⎛4 3⎞
⎛ 4 3 ⎞
p = ⎜ , ⎟ , q∗ = ⎜ 0, ,0, ,0 ⎟
⎝7 7⎠
⎝ 7 7 ⎠
5
7
v=−
E ( p,(0,1))
7
5
14
が均衡点
E ( p, e2 )
∗
v=
⎛3 2⎞
(q1 , q2 ) = ⎜ , ⎟
⎝5 5⎠
p1
定理
⎛ 5 2 4 −1 0 ⎞
⎜
⎟
⎝ −2 −1 2 3 3 ⎠
E ( p, e1 ) = 5 p1 − 2 p2
E ( p,(1,0))
15
∀p, q
E ( p, q ∗ ) ≤ E ( p ∗ , q ∗ ) ≤ E ( p ∗ , q )
16
4
2006年度システム基礎資料　高橋　真吾
定理
は明らか。
∀p, q
∗
∗
∗
m
m
i =1
i =1
∑ E (ei , q∗ ) pi ≤ ∑ E ( p∗ , q∗ ) pi =E ( p∗ , q∗ )
∗
E ( p, q ) ≤ E ( p , q ) ≤ E ( p , q )
が
であるから
E ( p, q ∗ ) ≤ E ( p ∗ , q ∗ )
∀i, j
∗
∗
∗
同様にして
∗
E (ei , q ) ≤ E ( p , q ) ≤ E ( p , e j )
E ( p∗ , q∗ ) ≤ E ( p∗ , q)
17
18
定理
( p∗ , q∗ ) がAの均衡点であるとき
A = (aij ), A ' = ( aij ∗ )
p ∗ A ' e j = p ∗ kAe j + c ≥ kv( A) + c
aij ∗ = kaij + c, k > 0
ei A ' q∗ = ei kAq ∗ + c ≤ kv( A) + c
( p∗ , q∗ ) はA’の均衡点であり
AとA’の最適戦略は同じ
v( A ') = kv( A) + c
v( A ') = kv( A) + c
19
20
5
2006年度システム基礎資料　高橋　真吾
ゲームを線形計画問題として解く
• ゲームの値：v
• aij>0
最大化プレーヤpの問題
a1 j p1 + a2 j p2 +
m
∑p
i =1
i
+ amj pm ≥ v (1 ≤ j ≤ n )
= 1, pi ≥ 0
max v
pi ' =
pi
v
a1 j p1 '+ a2 j p2 '+
+ amj pm ' ≥ 1 (1 ≤ j ≤ n)
pi ' ≥ 0
min
∑p '
i
21
最小化プレーヤqの問題
ai1 q1 + ai 2 q2 +
n
∑q
i =1
j
非協力ゲーム
+ ain qn ≤ v (1 ≤ i ≤ m )
• 非協力非ゼロ和２人ゲーム
• ルール
= 1, q j ≥ 0
– プレーヤ：２人
– 利得の和はゼロとは限らない
– プレーヤは結託しない
– ゲームのプレイは１回
min v
qi ' =
qi
v
ai1q1 '+ ai 2 q2 '+
22
+ aim qm ' ≥ 1 (1 ≤ i ≤ m)
qj ' ≥ 0
max
∑q
j
'
23
24
6
2006年度システム基礎資料　高橋　真吾
非協力均衡
双行列ゲーム
• 先手後手の区別がない
• 面会ゲームの例
• 戦略集合
Π 1 = {i | i = 1,2,
Π 2 = { j | j = 1,2,
彼女
彼氏
待つ
出かける
その場
で待つ
出かける
(0,0)
(10,6)
(6,10)
, m}
, n}
• 利得関数
f 1 (i, j ) = a ij
f 2 (i, j ) = bij
(-6,-6)
25
双行列表現
26
ナッシュ均衡点
• プレーヤ2人のとき
A = (aij ), B = (bij )
⎡ (a11, b11)
G = ( A, B) = ⎢⎢
⎢⎣(am1 , bm1 )
S = S1 × S 2 , fi ( s ) = f i ( p, q), s = ( p, q)
(a1n , b1n ) ⎤
⎥
⎥
(amn, bmn)⎥⎦
s * = ( p * , q * ) ∈ S がナッシュ均衡点
⎧ f 1 ( s * ) = max f 1 ( p, q * )
⎪
p∈S1
⇔⎨
*
f 2 ( p * , q)
⎪ f 2 ( s ) = max
q∈S 2
⎩
解概念
ナッシュ均衡点
27
ナッシュ均衡点からは離脱する合理的理由がない
28
7
2006年度システム基礎資料　高橋　真吾
ナッシュ均衡点
最適応答戦略
• 一般の定義（プレーヤn人）
s = ( s1 , s2 ,… , sn ) ∈ S1 ×
s− i
× S n がナッシュ均衡点
( s1 ,… , si −1 , si +1 ,… , sn )
s−i に対するプレーヤiの最適応答戦略
∀i ∈ N ∀ti ∈ Si
f i ( s1 ,..., si −1, si , si +1, ..., sn ) ≥ f i ( s1 ,..., si −1,ti , si +1, ..., sn )
s− i
のもとで利得を最大にするプレーヤiの戦略
29
30
f1 ( s* ) = max f1 ( p, q* )
p∈S1
ナッシュ均衡点
a
p
q
⎛ (3 0)
⎜
⎝ ( 2 1)
b
( −1 2 ) ⎞
⎟
(3 4) ⎠
最適応答戦略集合の共通部分
aに対する最適応答
31
bに対する最適応答
32
8
2006年度システム基礎資料　高橋　真吾
ナッシュ均衡点は？
f 2 ( s* ) = max f 2 ( p∗ , q)
q∈S2
a
q
⎛ (3 0)
⎜
⎝ ( 2 1)
彼女
( −1 2 ) ⎞
⎟
(3 4) ⎠
彼氏
p
b
待つ
出かける
その場
で待つ
出かける
(0,0)
(10,6)
(6,10)
(-6,-6)
pに対する最適応答
qに対する最適応答
33
34
⎛ ( −1, −1) (2,3) ⎞
⎜ (3, 2) (0,0) ⎟
⎝
⎠
ナッシュ均衡点
(1,2), (2,1)
35
9