新ゲーム理論 第Ⅰ部 非協力ゲームの理論 第1章

新ゲーム理論
第Ⅰ部 非協力ゲームの理論
第2章 戦略形ゲームのナッシュ均衡
M1 北川直樹
内容
ナッシュ均衡点
ミニマックス均衡点
寡占市場の均衡
混合戦略による均衡点
1.
2.
3.
4.
•
•
混合戦略
混合戦略による均衡点
5. 非協力n人ゲーム
6. 非協力ゲーム理論の性格
1. ナッシュ均衡点の性格
2. ナッシュ均衡理論の性格
内容
1. ナッシュ均衡点
2. ミニマックス均衡点
3. 寡占市場の均衡
4. 混合戦略による均衡点
•
•
混合戦略
混合戦略による均衡点
5. 非協力n人ゲーム
6. 非協力ゲーム理論の性格
1. ナッシュ均衡点の性格
2. ナッシュ均衡理論の性格
ナッシュ均衡点
例1)非協力2人ゲームを考える
<
4,4
4,3
<
3,6
<
2,5
5,4
5,5
<
<
<
<
0,3
0,9
<
戦略Ⅲ
<
<
戦略Ⅱ
8,8
<
戦略Ⅰ
<
A
B 戦略Ⅰ 戦略Ⅱ 戦略Ⅲ
このゲームでは、2人のプレイヤーの持つ戦略間に
支配関係がない.
ナッシュ均衡点
• 各プレーヤーは、自分が取った戦略に対する相手
の反応を考える
A
• プレイヤーAの戦略:ⅰ
• プレーヤーBの戦略: j
B
戦略Ⅰ 戦略Ⅱ 戦略Ⅲ
戦略Ⅰ
8,8
0,9
5,4
戦略Ⅱ
0,3
5,5
4,4
戦略Ⅲ
2,5
4,3
3,6
ナッシュ均衡点
• プレイヤーAの考え
• プレイヤーBの考え
– ⅰ=1のとき
– j=1のとき
• max(8,9,4)=9、 j=2
– ⅰ=2のとき
• max(8,0,2)=8、 ⅰ=1
– j=2のとき
• max(3,5,4)=5、 j=2
– ⅰ=3のとき
• max(0,5,4)=5、 ⅰ=2
– j=3のとき
• max(5,3,6)=6、 j=3
A
• max(5,4,3)=5、 ⅰ=1
B 戦略Ⅰ 戦略Ⅱ 戦略Ⅲ
戦略Ⅰ
8,8
0,9
5,4
戦略Ⅱ
0,3
5,5
4,4
戦略Ⅲ
2,5
4,3
3,6
均衡点
ナッシュ均衡点
• 最適反応戦略の均衡点
– プレイヤーAが戦略Ⅱ、プレーヤーBも戦略Ⅱの
とき、どちらのプレーヤーも自分の戦略を変えて
も利得は増加しない。
A
均衡点/ナッシュ均衡点
(ⅰ, j )=(2 , 2)
B
戦略Ⅰ 戦略Ⅱ 戦略Ⅲ
戦略Ⅰ
8,8
0,9
5,4
戦略Ⅱ
0,3
5,5
4,4
戦略Ⅲ
2,5
4,3
3,6
ナッシュ均衡点
• 最適反応原理
– 相手がある戦略をとったときに、その戦略のもと
で自分の利得を最大にするように行動する
• 最適反応戦略の均衡点(ナッシュ均衡点)
– 2人のとる戦略が互いに相手の戦略の最適反応
戦略になっている
ナッシュ均衡点
• 非協力2人ゲームの戦略形
プレイヤー 2人 : i  {1,2}
プレイヤー iの戦略とその集合 : Si  {si }
戦略の組とその集合:
S  S1  S2  {s  (s1, s2:) s1  S1, s2  S2}
プレーヤーiの持つ利得関数
xi  fi (s1, s2 ), i  1,2
ナッシュ均衡点
• 次の条件をみたすSの点を均衡点という

1


1


)  max f (s

, s ) : s S

f1 (s , s2 )  max f1 (s1 , s2 ) : s1  S1
f 2 (s , s2


1
2

s  (s , s2 )

1
2
2
2
ナッシュ均衡点/均衡点
前回の「支配される戦略は使わない」という戦略原理によって到達
した均衡点や支配戦略均衡点は、ナッシュ均衡点の特別な場合
ナッシュ均衡点
• 最適反応戦略の集合
・プレイヤー1の戦略 s1に対する
プレーヤー2の最適反応戦略の集合R2 (s1 )
R2 (s1 )  s 2 S2 , f 2 (s1 , s2 )  max f 2 (s1 , s2 )
s 2 S2


・プレイヤー 2の戦略s2に対する
プレーヤー1の最適反応戦略の集合R1 (s2 )
R1 (s2 )  s1 S1 , f1 (s1 , s2 )  max f1 (s1 , s2 )
s1S1


ナッシュ均衡点
• 最適反応集合
• プレーヤー1の最適反応集合
– プレイヤー2の戦略s2とそれに対するプレーヤー1の最適
反応戦略の組の集合(D1)
• プレイヤー2の最適反応集合
– プレイヤー1の戦略s1とそれに対するプレーヤー2の最適
反応戦略の組の集合(D2)
D1  s  (s1, s2 ) : s2  S2 , s1  R1 (s2 )
D2  s  (s1, s2 ) : s1  S1, s2  R2 (s1 )
ナッシュ均衡点
• ナッシュ均衡点の集合(D)
D  D1  D2
• 例1の場合
 1,1 2,2 1,3 
D   1,2 2,2 3,3 
D  D  D   2,2 
D1 
2
1
2
A
B
戦略Ⅰ 戦略Ⅱ 戦略Ⅲ
戦略Ⅰ
8,8
0,9
5,4
戦略Ⅱ
0,3
5,5
4,4
戦略Ⅲ
2,5
4,3
3,6
内容
1. ナッシュ均衡点
2. ミニマックス均衡点
3. 寡占市場の均衡
4. 混合戦略による均衡点
•
•
混合戦略
混合戦略による均衡点
5. 非協力n人ゲーム
6. 非協力ゲーム理論の性格
1. ナッシュ均衡点の性格
2. ナッシュ均衡理論の性格
ミニマックス均衡点
• 例2)ゼロ和2人ゲーム(立地ゲーム)
同じ製品を販売する2つの会社A、Bがある
全体の需要を100とすると各町の需要は、20、40、20、20である。
ともに、ある道路に沿って等間隔に位置している4つの町の中の1つに、
・・• A社は、各町について、もしA社がB社よりその町に近けれ
新しい店を出したいと思っている。
ばその町の需要の80%、B社より遠ければ40%、同じ距離な
らば60%を得ることができる
A社
20人
40人
プレイヤー
B社
20人
20人
需要
1町
2町
3町
4町
戦略
ミニマックス均衡点
• A社がⅰ町に、B社が j 町に出店したときのA社の利
得をaij、B社の利得をbijとすると
bij =100- aij
• 企業Bの利得をbij ´=- aijと置き換えると(ゼロ和ゲーム)、
企業Aの利得行列をA=[aij]とすると利得行列Gは
60,
72,
G  aij  
64,

56,
 
48,
60,
56,
52,
56,
64,
60,
48,
64

68
72

60
ミニマックス均衡点
非協力ゼロ和2人ゲームでは
• A社は、利得aijを最大にしようと行動する
– 最大化プレイヤー
– 最大化戦略
• B社は、利得aijを最小にしようと行動する
– 最小化プレイヤー
– 最小化戦略
ミニマックス均衡点
• マックスミニ戦略
• Aの戦略ⅰに対抗するBの最小化戦略 j
i  1に対しては , min(60,48,56,64)  48, j  2
i  2に対しては , min(72,60,64,68)  60, j  2
i  3に対しては , min(64,56,60,72)  56, j  2
i  4に対しては , min(56,52,48,60)  48, j  3
• Bが最適反応戦略である最小化戦略をとるとすると
Aは、
max(48,60,56,48)  maxmin ai j  60
i
j
ミニマックス均衡点
• ミニマックス戦略
• Bの戦略 j に対抗するAの最小化戦略 i
j  1に対しては , max(60,72,64,56)  72, i  2
j  2に対しては , max(48,60,56,52)  60, i  2
j  3に対しては , max(56,64,60,48)  64, i  2
j  4に対しては , max(64,68,72,60)  72, i  3
• Aが最適反応戦略である最大化戦略をとるとすると
Bは、
min(72,60,64,72)  min maxai j  60
j
i
ミニマックス均衡点
• 最大化プレイヤーAがマックスミニ戦略(i=2)、
最小化プレイヤーBがミニマックス戦略(j=2)のとき
maxmin ai j  min maxai j  60
i
j
j
i
均衡点 : (ⅰ, j )=(2 , 2)
ミニマックス均衡点
※相手のとる戦略に対して最適反応戦略なのでこのゲームのナッシュ均衡点
ミニマックス均衡点
• ミニマックス原理
– 最大化プレイヤーがマックスミニ戦略ととり、最小化
プレイヤーがミニマックス戦略をとる行動原理。
• ミニマックス戦略
– マックスミニ戦略とミニマックス戦略をまとめて呼ぶ。
• ミニマックス均衡点
– マックスミニ戦略とミニマックス戦略との組。
• 問題点
– 非ゼロ和ゲームの場合、ミニマックス原理は合理的
な行動原理ではない。
内容
1. ナッシュ均衡点
2. ミニマックス均衡点
3. 寡占市場の均衡
4. 混合戦略による均衡点
•
•
混合戦略
混合戦略による均衡点
5. 非協力n人ゲーム
6. 非協力ゲーム理論の性格
1. ナッシュ均衡点の性格
2. ナッシュ均衡理論の性格
寡占市場の均衡
例3)クールノーの複占市場
1. 2つの企業をプレイヤー1、プレイヤー2とする。
2. 両者は、無差別な財を市場に供給している。
3. プレイヤー1の戦略S1、供給量x1
プレイヤー2の戦略S2、供給量x2
S1  x1 : 0 ≦ x1 ≦ M1
S2  x2 : 0 ≦ x2 ≦ M 2 
M1、 M:適当な正の数
2
※今までと違うのは、戦略が連続量ってこと
寡占市場の均衡
例3)クールノーの複占市場
4. 財の価格をpとし、x1、x2で表すと
p  maxa  bx1  x2 , 0 , a>0, b>0
5. 2つの企業の費用関数をC1、C2とすると
C1  c1 x1, ただし a>c1>0
C2  c1x1, ただし a>c2>0
6. 2つの企業の利得関数をy1,y2とすると、p>0のとき
y1  px1  c1x1  a  c1 x1  bx1 x1  x2 
y2  px2  c2 x2  a  c2 x2  bx2 x1  x2 
総売上
総費用
寡占市場の均衡
• 相手の供給量に対する最適反応戦略を求める
y1
 a  c1  bx1  bx1  x2   0
x1
ここを探す感じ
 2 y1
 b  b  2b<0
2
x1
– 企業1の企業2の戦略に対する最適反応戦略


x1  R1 x2   max a  c1  bx2  / 2b, 0
– 企業2の企業1の戦略に対する最適反応戦略


x2  R2 x1   max a  c2  bx1  / 2b, 0
寡占市場の均衡
x2
a  c1
b
D1
a  c2
2b
均衡点
x2
D2
x1 a  c1
2b
a  c2
b
x1
寡占市場の均衡
a  24, b  1, c1  3, c2  6, M1  M 2  30のとき
・反応曲線の交点 xは
x1  a  2c1  c2  / 3b  8
x2  a  2c2  c1  / 3b  5


x  x1 , x2  8, 5
・均衡利得 yは
y  64, 25
・財の価格 pは
p  11
クールノー/ナッシュ均衡点
寡占市場の均衡
• クールノー均衡点
– 企業が交互に自分の戦略を市場に提示し、相手
が提示した戦略に対する次々と最適反応戦略を
提示し、どちらも戦略を変えようとしない戦略の組
– 次々と戦略を提示する過程をプレイヤーが頭の
中で考え、それぞれの均衡した戦略をとると考え
ると、到達する均衡点はナッシュ均衡点
– クールノー型複占市場の均衡点は、結果的に
ナッシュ均衡点に一致する。
内容
1. ナッシュ均衡点
2. ミニマックス均衡点
3. 寡占市場の均衡
4. 混合戦略による均衡点
•
•
混合戦略
混合戦略による均衡点
5. 非協力n人ゲーム
6. 非協力ゲーム理論の性格
1. ナッシュ均衡点の性格
2. ナッシュ均衡理論の性格
混合戦略
例4)2つの企業の販売戦略
• 利得行列
プレイヤー2
プレイヤー1
1
2
1
2
8, 0
0, 4
0, 6
6, 0
• プレイヤー1の最適反応戦略
D1 
 1, 1,
2, 2 
• プレイヤー2の最適反応戦略
D2 
 1, 2, 2, 1 
最適反応戦略の共通部分がない
混合戦略
• くじ引きで確率的に決断する。
• プレイヤー1が戦略1をとる確率 : p1
戦略2をとる確率 : p2
• プレイヤー1の混合戦略 : p=(p1, p2)
• 本来の戦略1、2を混合戦略と区別して純戦略
と呼ぶ
混合戦略
• プレーヤー1の期待値E1
– プレイヤー1が混合戦略p(p1,p2) 、
プレイヤー2が純戦略1か2のとき
E1  p,1  8  p1  0  p2  8 p1
E1  p,2  0  p1  6  p2  6 p2  61  p1 
– プレイヤー1が混合戦略p(p1,p2)、
プレイヤー2も混合戦略q(q1,q2)のとき
E1  p, q  E1  p,1q1  E1  p,2q2
混合戦略
• プレーヤー2の期待値E2
– プレイヤー2が混合戦略q(q1,q2) 、
プレイヤー1が純戦略1か2のとき
E2 1, q  0  q1  6  q2  61  q1 
E2 2, q  4  q1  0  q2  4q1
– プレイヤー2が混合戦略q(q1,q2) 、
プレイヤー1も混合戦略p(p1,p2)のとき
E2  p, q  E2 1, q p1  E2 2, q p2
混合戦略
• 利得関数E1(p,q)、E2(p,q)をもつ新ゲームと定義
⇒前のゲームの混合拡大ゲーム
• 混合戦略を考慮した混合拡大ゲームの利得行列
q1
p1
1
4/7
3/7
2/7
0
1
8.0 , 0.0 4.6 , 2.6 3.4 , 3.4 2.3 , 4.3 0.0 , 6.0
3/5
4.8 , 1.6 3.8 , 2.5 3.4 , 2.7 3.1 , 3.0 2.4 , 3.6
2/5
3.2 , 2.4 3.4 , 2.4 3.4 , 2.4 3.5 , 2.4 3.6 , 2.4
1/5
1.6 , 3.2 3.0 , 2.3 3.4 , 2.1 3.9 , 1.8 4.8 , 1.2
0
0.0 , 4.0 2.6 , 2.3 3.4 . 1.7 4.3 , 1.1 6.0 , 0.0
混合戦略
• 最適混合戦略の組
p   p1, p2   2 / 5 , 3 / 5
q  q1, q2   3 / 7 , 4 / 7
• 均衡利得
(3.4 , 2.4)
1
4/7
3/7
2/7
0
1
8.0 , 0.0
4.6 , 2.6
3.4 , 3.4
2.3 , 4.3
0.0 , 6.0
3/5
4.8 , 1.6
3.8 , 2.5
3.4 , 2.7
3.1 , 3.0
2.4 , 3.6
2/5
3.2 , 2.4
3.4 , 2.4
3.4 , 2.4
3.5 , 2.4
3.6 , 2.4
1/5
1.6 , 3.2
3.0 , 2.3
3.4 , 2.1
3.9 , 1.8
4.8 , 1.2
0
0.0 , 4.0
2.6 , 2.3
3.4 . 1.7
4.3 , 1.1
6.0 , 0.0
その後….
企業1の社長は、2/5の確率で純戦略1、3/5の確率で
純戦略2、が出るクジを引いて決断し、
企業2の社長は、3/7の確率で純戦略1、4/7の確率で
純戦略2、が出るクジを引いて決断した。
大事な決定をクジで決めることは、奇妙な方法にみえ
るかもしれないが、
これ以外のいかなる方法も、社長にとっても、スタッフ
にとっても十分に納得できなかったのである。
めでたし、めでたし
混合戦略による均衡点
1)プレイヤー2人:
1 ,2
2)プレイヤー 1,2の純戦略
i  1,, m, j  1,, n
3)利得行列は、双行 列G  ai j , bij で表される。


4)プレイヤー 1,2の混合戦略の集合をS1  p, S2  qとすると
p   p1,, pm , q  q1,, qn 
pi ≧0, i  1,, m, p1   pm  1
q j ≧0, j  1,, n, q1   qn  1
混合戦略の均衡点
5)混合戦略の組の集 合Sは
S  S1  S2  s  ( p, q) : p  S1 , q  S2 
6)プレイヤー iの利得関数は、混合戦略の関数として
x1  f1  p, q  pAqT
x2  f 2  p, q  pBqT
ただし、 A  aij , B  bij
 
 
7) s   p, q が以下の条件をみたすとき、
s をこのゲームのナッシ ュ均衡点という
f1  p, q   max f1  p, q , p  S1 
f 2  p, q   max f 2  p, q, p  S2 
内容
ナッシュ均衡点
ミニマックス均衡点
寡占市場の均衡
混合戦略による均衡点
1.
2.
3.
4.
•
•
混合戦略
混合戦略による均衡点
5. 非協力n人ゲーム
6. 非協力ゲーム理論の性格
1. ナッシュ均衡点の性格
2. ナッシュ均衡理論の性格
非協力n人ゲーム
•
無限の戦略をもつ非協力ゲーム
1)プレイヤーを i  1,2,, n nは有限の正の整数とする。
2)プレイヤー iのもつ純戦略の集合Sは
S  S1  S2  Sn  s  s1, s2 ,, sn 
3)プレイヤー iにとって、自分以外の プレイヤーがとる
戦略の組を si ,その集合をSiとする。
4)プレイヤー iのもつ利得関数をfi s とする。
4)ナッシュ均衡点 s は
fi s   max fi si , si  : si  Si 
非協力n人ゲーム
• 有限の戦略をもつ非協力ゲーム
1)プレイヤーを i  1,2,, n nは有限の正の整数とする。
2)プレイヤー iのもつ純戦略の集合Sは、
S  S1  S2  Sn  s  s1, s2 ,, sn 
3) hiを純戦略j,, kのときのプレイヤー iの利得とすると、
混合戦略pのときのプレイヤー iのもつ利得関数fi s は、
fi s    hi  j,, k p1 j  pnk
j 1
k 1
4)ミニマックス均衡
点( p, q)の成立条件は、
max min pAqT  min max pAqT
pS1 qS2
pS1 qS2
内容
ナッシュ均衡点
ミニマックス均衡点
寡占市場の均衡
混合戦略による均衡点
1.
2.
3.
4.
•
•
混合戦略
混合戦略による均衡点
5. 非協力n人ゲーム
6. 非協力ゲーム理論の性格
1. ナッシュ均衡点の性格
2. ナッシュ均衡理論の性格
ナッシュ均衡点の性質
• 例6)面会ゲーム
2人がとることのできる行動は、以下の2つです。
となる田舎まちに、仲の良いカップルがいました。
2人は、今すぐに会いたいです。
すると、突然の大地震が起こり、2人は離ればなれになってしまいました。
(a)相手が来るのをその場で待つ
通信網も途切れてしまい、連絡が取れません。
(b)こちらから相手のいるところに出掛ける
会いたいよ
ジョン!
会いたいよ
ステファニー!
ナッシュ均衡の性質
• このゲームの利得行列は、
a 待つ
b 出掛ける
a 待つ
0,0
10 , 6
b 出掛ける
6 , 10
ー6 , -6
ナッシュ均衡の性質
• このゲームの均衡点  p, q  は
 p, q   1, 0, 0, 1  a, b
 p, q   8 / 11, 3 / 11, 8 / 11, 3 / 11
 p, q   0, 1, 1, 0  b, a
ここで、(a,b)と(b,a)は、純戦略による均衡点である。
• それぞれの均衡利得は、
10, 6
30 /11, 30 /11
6, 10
a 待つ
b 出掛ける
a 待つ
0,0
10 , 6
b 出掛ける
6 , 10
-6 , -6
ナッシュ均衡の性質
1. 最適反応戦略とにミニマックス戦略の関係
1. ミニマックス戦略
• 純戦略のみの場合
•
•
•
2人とも、その場で待つ、を選択する
そのときの利得の組 : (0, 0)
混合戦略の場合
•
•
ミニマックス戦略 : p=q=(6/11, 5/11)
そのときの利得の組 : (30/11, 30/11)
• 3つの均衡利得は、いずれも2人がともにミニマックス原理
に従って行動したときに得られる利得の30/11以上
• 一般に、マックスミニ利得は均衡利得の下限になる。
ナッシュ均衡の性格
2. 戦略の交換性と最適性の不成立
– 均衡戦略の交換可能
•
•
2つの均衡戦略を交換してできる戦略の組も、同じく
均衡点になるもの
非ゼロ和2人ゲームでは、複数個の均衡点の均衡戦
略は必ずしも交換可能ではないが、ゼロ和2人ゲーム
では、常に均衡戦略は交換可能である。
ナッシュ均衡点の性格
3. 複数のナッシュ均衡点の意味
1. 起こりうる可能性
•
純戦略で表現される状態と混合戦略で表現される状態が存在
2. 予備知識がある場合
•
•
「彼は、いつも行動的な人である」などの、経験の積み重ねによる
情報の累積によって、均衡点が限定される。
ゲームで表現できるのは現実の一部であり、他の情報を補うべき。
3. 通報可能な場合
•
•
彼が戦略を通報することができれば、彼女の戦略は決定する
均衡点は、外からの強制力なしで自立的な安定性をもっている。
4. 予備知識もなく、通報の可能性もない場合
•
ゲームとして表現された情報のみでは、確定的な行動ができない
ため、混合戦略を基に行動の指針を決定する。
ナッシュ均衡点の性格
4. 状況のより深い理解を与えるための均衡点
–
それぞれの均衡点の意味を考えることによって、ゲー
ムとして表現することのできなかった背後にある状況に
対して深い理解をもつことが可能となる。
ナッシュ均衡理論の性格
例7)友情原理
A
B
A
8,8
4,8
B
8,4
4,4
• プレイヤー1、2にとって、戦略A、Bは同等の戦略
• しかし、得られる利得は異なる
均衡点(A , A) : 利得(8 , 8)
均衡点(B , B) : 利得(4 , 4)
ナッシュ均衡理論の性格
• 友情ルール
– ある与えられた相手の戦略に対して、自分の利得が同じ
になる戦略が複数個あるときには、相手の利得が大きく
なる戦略を選択する。
• 例7)において、友情ルールが成立すると利得は
(8 , 8)になる。
• 社会がある程度成熟してくると、特別な会話なくとも
友情ルールのような“慣習”が成り立ってくる。
らしい…...
ほんとかよー!?
ナッシュ均衡論の性格
• 筆者の熱き思い
– ゲーム理論を学ぶ意義とは、
• ある状況のもとでのプレイヤー相互依存関係を明確に
認識し、起こりうる事態を明らかにすることによって、よ
り深く社会を認識することである。
• そして、個々のプレイヤーにとっては、いかに行動する
かを学びとることであり、政策立案者にとっては、いか
なるルールを設計すべきかを学びとることである。