第1週配布資料 - Info Shako

戦略形ゲーム
1
1.1
戦略形ゲームの定義
• 戦略形ゲーム（games in strategic form）
：G = (N, {Si }i∈N , {fi }i∈N )
· N = {1, 2, . . . , n}：プレイヤーの集合
· Si ：プレイヤー i ∈ N がとりうる戦略（strategies）の集合
· fi : S → R, where S = S1 × S2 × · · · × Sn ：プレイヤー i ∈ N の
利得関数（payoﬀ function）
• 各プレイヤーの目的は自己の利得の最大化．このことと，ゲーム G の
すべての要素はすべてのプレイヤーにとって共有知識．
例１：（囚人のジレンマ）N = {1, 2}，S1 = {U, D}，S2 = {L, R}，
f1 (U, L) = 2，f2 (U, L) = 2, f1 (U, R) = 8, . . ., as shown in Fig. 1.
2
L
R
U
2, 2
8, 0
D
0, 8
5, 5
1
Figure 1: Prisoners’ Dilemma
· n 人戦略形ゲーム G において，戦略の組 s = (s1 , . . . , sn ) に対し，
すべてのプレイヤー i ∈ N について，fi (t1 , . . . , tn ) > fi (si , . . . , sn )
となる戦略 t = (t1 , . . . , tn ) が存在しないとき，s = (s1 , . . . , sn ) は
パレート効率的（Pareto eﬃcient）であるという．
· プレイヤー i ∈ N の２つの戦略 si と ti について，他の n − 1 人の
プレイヤーが持つすべての戦略の組 s−1 ∈ S1 × · · · × Si−1 × Si+1 ×
· · · × SSn に対して，
fi (si , s−1 ) > fi (ti , s−1 )
が成り立つとき，si は ti を支配（dominate）するという．
1
1.2
戦略形ゲームのナッシュ均衡
• n 人戦略形ゲーム G において，すべてのプレイヤー i ∈ N について，
fi (s∗ ) ≥ fi (si , s∗−i ), ∀si ∈ Si
(1)
が成立するとき，そのような戦略の組 s∗ = (s1 , . . . , sn ) をナッシュ均衡
（Nash equilibrium）という．
• 他のすべてのプレイヤーの戦略の組 s−1 = (s1 , . . . , si−1 , si+1 , . . . , sn ) に
対して， si が
fi (si , s−1 ) = max fi (ti , s−i )
ti ∈Si
を満たすとき，si は s−i に対する最適反応（best response）であると
いう．
· ナッシュ均衡ではすべてのプレイヤーが他のすべてのプレイヤー
の戦略に対して最適反応をとっている．
· s−i に対するプレイヤー i の最適反応の集合を Bi (s−i ) で表すこと
にする．これを最適反応対応（best response correspondence）と
いう．
1.3
戦略形ゲームの混合拡大とナッシュ均衡
• Si に含まれるある戦略 si をプレイヤー i が確定的に選択する場合，si
をプレイヤー i の純粋戦略（pure strategy）という．
例２：
（硬貨合わせ）N = {1, 2}，S1 = {U, D}，S2 = {L, R}，f1 (U, L) =
−1，f2 (U, L) = 1, f1 (U, R) = 1, . . ., as shown in Fig. 2.
2
L
R
U
−1, 1
1, −1
D
1, −1
−1, 1
1
Figure 2: Matching Pennies
· 硬貨合わせゲームに純戦略でのナッシュ均衡は存在しない．
2
• Si に含まれる複数の戦略をプレイヤー i 確率的に選択する場合，その
確率分布をプレイヤー i の混合戦略（mixed strategy）という．
˜ = (N, {Qi }i∈N , {Fi }i∈N )
• n 人戦略形ゲーム G の混合拡大：G
· Qi ：Si 上の確率分布の集合．qi ∈ Qi はプレイヤー i ∈ N がとり
うる混合戦略．
· Fi : Q → R, where Q = Q1 × Q2 × · · · × Qn：プレイヤー i ∈ N の
期待利得関数（expected payoﬀ function）．
∑
∑
Fi (q1 , . . . , qn ) =
···
Πnj=1 qj (sj )fi (s1 , . . . , sn ).
s1 ∈S1
sn ∈Sn
˜ において，すべてのプレイヤー i ∈ N について，
• n 人戦略形ゲーム G
∗
Fi (q ∗ ) ≥ Fi (qi , q−i
), ∀qi ∈ Qi
(2)
が成立するとき，そのような混合戦略の組 q ∗ = (q1 , . . . , qn ) を混合戦略
ナッシュ均衡（mixed strategy Nash equilibrium）という．
例３：
（男女の争い）N = {1, 2}，S1 = {U, D}，S2 = {L, R}，f1 (U, L) =
2，f2 (U, L) = 1, f1 (U, R) = −1, . . ., as shown in Fig. 3.
2
L
R
U
2, 1
−1, −1
D
−1, −1
1, 2
1
Figure 3: Battle of Sexes
· 男女の争いゲームに純戦略では２つ，混合戦略では１つのナッシュ
均衡が存在．
• 混合戦略均衡は (q1∗ , q2∗ ), where q1∗ = (3/5, 2/5) and q2∗ = (2/5, 3/5)．均
衡期待利得ベクトルは (1/5, 1/5)．プレイヤー２が L を確率 p2 で選択
するとき，プレイヤー１が U を選択すればプレイヤー１の期待利得は
2p2 − (1 − p2 ) であり，D を選択すれば −p2 + (1 − p2 ) なので，これら
の期待利得が大きくなる純戦略を選択する．
3
1.4
ナッシュ均衡の存在定理
˜ = (N, {Qi }i∈N , {Fi }i∈N ) に
Theorem 1 (Nash, 1950) 有限な n 人ゲーム G
は少なくとも一つのナッシュ均衡が存在する．
˜ の最適反応対応は
• 準備１：混合拡大したゲーム G
Bi (q−i ) = {qi ∈ Qi |Fi (qi , q−1 ) = max Fi (ri , q−i )}.
ri ∈Qi
混合戦略の組 q = (q1 , . . . , qn ) に対して，写像 B : Q 7→ Q を次のように
定義する．
B(q) = B1 (q−1 ) × · · · × Bn (q−n ).
˜ の混合戦略ナッシュ均衡であるとは
q ∗ = (q1 , . . . , qn ) がゲーム G
q ∗ ∈ B(q ∗ )
(3)
であること．つまり，q ∗ は写像 B の不動点．
• 準備２：
（角谷の不動点定理；Kakutani, 1941）コンパクトな凸集合上
で定義される優半連続な凸値対応には少なくとも一つの不動点が存在
する．
4

Download Report