第2週配布資料 - Info Shako

1.5
混合戦略ナッシュ均衡の計算例
• N = {1, 2}，S1 = {U, D}，S2 = {L, R}，f1 (U, L) = a1 ，f2 (U, L) = a2 ,
f1 (U, R) = b3 , . . ., as shown in Fig. 4. Assume that a1 > a2 , a4 > a3 ,
b1 > b3 , and b4 > b2 .
2
L
R
U
a1 , b1
a3 , b3
D
a2 , b2
a4 , b4
1
Figure 4: A Bimatrix Game
· 純戦略ナッシュ均衡は (U, L) と (D, R)．
• プレイヤー i ∈ N の混合戦略を qi = (pi , 1 − pi ) とする．ここで p1 =
Prob(U )，p2 = Prob(L) である．各プレイヤー i の最適反応を求めよ．
· プレイヤー 2 の混合戦略 q2 = (p2 , 1 − p2 ) に対するプレイヤー 1 の
期待利得：
p2 a1 + (1 − p2 )a3
p2 a2 + (1 − p2 )a4
if player 1 chooses U with probability 1
if player 1 chooses D with probability 1.
このとき，プレイヤー 1 は p2 a1 + (1 − p2 )a3 > p2 a2 + (1 − p2 )a4 ，
つまり，
p2 ((a1 − a2 ) + (a4 − a3 )) > a4 − a3
ならば，確率 1 で U を選択することで期待利得を最大にできる．
よって，プレイヤー 1 の最適反応対応は次の通り．

a4 − a3

∗

=
0
if
p
p
2 <

1

(a1 − a2 ) + (a4 − a3 )







a4 − a3
B1 (q2 ) = p∗1 = [0, 1] if p2 =
(a1 − a2 ) + (a4 − a3 )








a4 − a3


if p2 >
.
p∗1 = 1
(a1 − a2 ) + (a4 − a3 )
1
· プレイヤー 1 の混合戦略 q1 = (p1 , 1 − p1 ) に対するプレイヤー 2 の
期待利得：
p1 b1 + (1 − p1 )b2
p1 b3 + (1 − p1 )b4
if player 2 chooses L with probability 1
if player 2 chooses R with probability 1.
このとき，プレイヤー 2 は p1 b1 + (1 − p1 )b2 > p1 b3 + (1 − p1 )b4 ，
つまり，
p1 ((b1 − b3 ) + (b4 − b2 )) > b4 − b2
ならば，確率 1 で L を選択することで期待利得を最大にできる．
よって，プレイヤー 1 の最適反応対応は次の通り．

b4 − b2


p∗2 = 0
if p1 <


(b1 − b3 ) + (b4 − b2 )







b4 − b2
B2 (q1 ) = p∗2 = [0, 1] if p1 =

(b1 − b3 ) + (b4 − b2 )







b4 − b2


p∗2 = 1
if p1 >
.
(b1 − b3 ) + (b4 − b2 )
• ナッシュ均衡 q ∗ = (q1∗ , q2∗ ) とは q1 ∈ B1 (q2∗ ) かつ q2∗ ∈ B2 (q1 ) を同時に満
たす戦略の組なので，((1, 0), (1, 0))，((0, 1), (0, 1)) と
)
(
U2
V1
U1
V2
,
), (
,
) ,
(
U2 + V2 U2 + V2 U1 + V1 U1 + V1
where U1 = a1 − a2 , V1 = a4 − a3 , U2 = b1 − b3 , and V2 = b4 − b2 .
· 横軸に p1 ，縦軸に p2 をとって，最適反応対応 B1 (q2 ) と B2 (q1 ) の
グラフを描いてみよ．定義より，それらの交点がナッシュ均衡．
• ナッシュ均衡の計算アルゴリズムは，Lemke-Howson algorithm を嚆矢
として，不動点計算法（fixed point algorithm）という応用数学の一分
野として発展した1 ．
1.6
ナッシュ均衡の応用例
• N = {1, 2}，Si = {qi ∈ R+ } for i ∈ N , fi (q1 , q2 ) = pqi − ci qi for i ∈ N .
p = max(0, a − b(q1 + q2 )), where a > 0, b > 0
and a > ci > 0.
1
Lemke, C.E., and Howson, J. (1962) “Equilibrium Points of Bimatrix Games,” SIAM
Journal of Applied Mathematics 12, 413-423.
2
· a − b(q1 + q2 ) ≥ 0 より，qi ≤ (a/b) − qj (i ̸= j)．よって，
{
(a − b(q1 + q2 ) − ci )qi if 0 ≤ qi ≤ (a/b) − qj
fi (q1 , q2 ) =
−ci qi
if (a/b) − qj < qi
• 各プレイヤーの最適反応対応を求めよ．
· １階の条件（first order condition）∂fi /∂qi = a−ci −2bqi −bqj = 0
より，

 a − ci − bqj
if 0 ≤ q2 ≤ (a − ci )/b.
Bi (qj ) =
2b

0
otherwise
２階の条件（second order condition）も確認せよ．
• ナッシュ均衡 q ∗ = (q1∗ , q2∗ ) とは q1 ∈ B1 (q2∗ ) かつ q2∗ ∈ B2 (q1 ) を同時に満
たす戦略の組なので，
( a − 2c + c a − 2c + c )
2
1
1
2
,
.
(q1∗ , q2∗ ) =
3b
3b
· このとき，p∗ = (a + c1 + c2 )/3 であり，均衡利得は
fi (q1∗ , q2∗ ) =
(a − 2ci + cj )2
.
9b
• （練習問題１）上記の例の両プレイヤーの最適反応対応を描け．
• （練習問題２）パレート効率的な戦略の組 qˆ = (ˆ
q1 , qˆ2 ) を
qˆ ∈ arg max f1 (q1 , q2 ) + f2 (q1 , q2 )
q1 ,q2
で定義する．ナッシュ均衡 q ∗ = (q1∗ , q2∗ ) はパレート最適か．
3

Download Report