人非協力非零和ゲーム

(1)

意思決定科学：ゲーム理論２

情報学部堀田敬介

2012/11/19,Mon. ～

(2)

2 人非協力非零和ゲーム

A

＼

B s_B1 s_B2 s_A1 (2, 3) (-1,-2) s_A2 (-2,-1) (1,1)

A

，

B

の利得表

N={A, B}

S_i={s_i1, s_i2}, (i=A,B)

f_i : S_A×S_B→ R, (i=A,B)

f_A (s_A1, s_B1) = 2 + f_A (s_A1, s_B2) = -1 + f_A (s_A2, s_B1) = -2 + f_A (s_A2, s_B2) = 1 +

f_B (s_A1, s_B1) = 3 ≠0 f_B (s_A1, s_B2) = -2 ≠0 f_B (s_A2, s_B1) = -1 ≠0 f_B (s_A2, s_B2) = 1 ≠0

S_A={s_A1, s_A2}, S_B ={s_B1, s_B2},

(4)

2 人非協力非零和ゲーム



双行列ゲーム



利得関数



利得行列

) , ( : )

, (

) ,

( )

, (

) ,

( )

, (

) ,

(

) ,

( )

, (

) ,

(

2 2

1 1

2 2

22 22

21 21

1 1

12 12

11 11

B A b

a b

a

b a

mn mn

m m

n n

























ij B

A B ij

B A

A s s a f s s b

f j

i i j  i j 

 , , ( , ) , ( , ) ]

[

],

[a_ij  b_ij

 B

A

プレイヤーBの戦略（n個）の利得（右側）

プレイヤーA の戦略（m個）

の利得（左側）

双行列和が零（一定）という条件はない（非零和）

(5)

2 人非協力非零和ゲーム



例１：恋人達のジレンマ

battle of sexes



ある一組のカップルがデートをしたいと思っている



男性は野球観戦を希望し，女性は映画鑑賞がしたい



各々が好きなものを見るより一緒にいることの方が大事

男

＼

女野球映画

野球

(2,1) (-1,-1)

映画

(-1,-1) (1,2)

性の戦い，男女の戦い，

逢引きのジレンマ，…

互いに支配戦略は持たない

ミニマックス原理に従うと，互いにどちらの戦略でも良い？

（または各戦略のマックスが大きくなる方を選ぶ！？）

1 min

max _ij  

j

i a

1 min

max _ij  

j

i b

(6)

2 人非協力非零和ゲーム



例１：恋人達のジレンマ

battle of sexes

 零和ゲームの時と同じ方法で，混合戦略で期待利得最大化すると…

男＼女野球映画野球 (2,1) (-1,-1) 映画 (-1,-1) (1,2)

p₁ p₂

q₁ q₂







   



2 2 1

2 2

1 1

1

2 2 1

2 2

1 1

1 2

) ,

( , ) 2 (

q p q

p q

p E

q p q

p q

p E

B

A p q

q p



   

1 2

)) 1 , 0 ( ,

( ,(1,0)) 3 1 (

1 1p E

p E

A

A p

p



   

2 3

) ), 1 , 0

((1,0), ) 2 1 ((

1 1q E

q E

B

B q

q

5 ) 1 , ˆ ( ˆ 5, ) 1 , ˆ ( ˆ , 5) , 2 5 (3 5), , 3 5 (2 ˆ)

ˆ,

(   



 



  p q p q

q

p E_A E_B

ところが…

5 ) 1

, ˆ

(  p₁  E_A p q

5 ) 4

ˆ,

(  q₁  E_B p q

BがをとるならAはではなく(1,0)にする方が期待利得が高くなる！

qˆ pˆ _AがをとるならBは

ではなく(0,1)にする方が

期待利得が高くなる！

qˆ pˆ

均衡しない

つまり，相手が純粋戦略を取ってきたときだけの自分の混合戦略を考えて期待利得を求めるやり方では，均衡解を求められない

(7)



最適応答対応

best response correspondence

• Ｂの戦略に対するＡの最適応答の集合

を，プレイヤーＡの最適応答対応とよび，

を，プレイヤーＡの最適応答集合とよぶ

 Definition

最適応答と最適応答対応



最適応答

best response

• プレイヤーＡの戦略が，プレイヤーＢの戦略に対する最適応答であるとは，以下が成り立つこと

2 人非協力非零和ゲーム

A

A S

s  s_B S_B

) , ( max

) ,

( p q p q

p A

A E

E 

) ,

( max

) ,

( _A _A _B

S B s

A

A s s f s s

f

A A

 ^{純粋戦略の場合}

混合戦略の場合

B

B S

s 

} {

⁽ ^, ⁾ ^max ⁽ ^, ⁾

)

( _A _A _B

S B s

A A A A

B

A s s S f s s f s s

R

A A







} {

⁽ _A^, _B⁾ _A _A⁽ _B^), _B _B

A s s s R s s S

D   

} {

⁽ ^, ⁾ ^max ⁽ ^, ⁾

)

(q p p q p q

p A

A

A E E

R  

純粋戦略の場合混合戦略

の場合

2人零和ゲームでは，

ミニマックス原理は最適応答原理に帰着

最適応答原理

(8)

プレイヤーＡの（純戦略での）最適応答 s_B1 → max{7,8,4} = 8

s_B2→ max{0,6,3} = 6 s_B3 → max{5,2,6} = 6



最適応答と最適応答対応

• プレイヤーＡ，Ｂが各々最適応答をとる場合，その組の集合はとなる

2 人非協力非零和ゲーム

B

A D

D

D : 

Ａ＼Ｂ s_B1 s_B2 s_B3 s_A1 ^(7,7) ^(0,8) ^(5,5) s_A2 ^(8,0) ^(6,6) ^(2,7) s_A3 ^(4,5) ^(3,1) ^(6,2)



例：

} { ) (

3 3

2 2

2 1

A B

A

A B

A

A B

A

s s

R

s s

R

s s

R





} {⁽ _A₂ ^, _B₁ ^),⁽ _A₂ ^, _B₂ ^),⁽ _A₃^, _B₃ ⁾

A s s s s s s

D 

プレイヤーＢの（純戦略での）最適応答 s_A1→ max{7,8,5} = 8

s_A2→ max{0,6,7} = 7

s_A3→ max{5,1,2} = 5 ( ) { } } { ) (

} { ) (

1 3

3 2

2 1

B A

B

B A

B

B A

B

s s

R

s s

R

s s

R





} {⁽ _A₂ ^, _B₃ ^),⁽ _A₁^, _B₂ ^),⁽ _A₃ ^, _B₁⁾

B s s s s s s

D 

互いに最適応答なら均衡する

（ D  なら均衡）

より，

純粋戦略のみでは均衡しない



 D

(9)

2 人非協力非零和ゲーム

 Definition Nash

均衡点

Nash equilibrium point



（混合）戦略の組が次の条件を満たすとき，

を

Nash

均衡点とよぶ

*)

*, ( p q

q q

p q

p

p q

p  

)

*, (

*)

*,

( *, *) ( , *) (

B B

A

A E

E

E E

 Theorem 1



（混合）戦略の組が互いに最適応答であるならば

Nash

均衡点であり，逆も成り立つ．即ち，

Nash

均衡点の集合を

E

とすると，

B

A D

D

E  

ˆ) ˆ, (p q

Nash均衡点は，零和ゲームの均衡点（鞍点）を含む

一般的な概念

*)

*, ( p q

 Theorem 2



（混合）戦略の組が

Nash

均衡点であるための必要十分条件は

*)

*, ( p q

n j

s E

E

m i

s E

E

j i

B B

B

A A

A( *, *) ( *, ) 1, , , ,

1

*) ,

(

*)

*, (







  



p q

p

q q

p

Bがq*をとるならAはp*がベスト Aがp*をとるならBはq*がベスト

(10)

2 人非協力非零和ゲーム

 2

人非協力非零和ゲームの

Nash

均衡点

^A, ^B

) ,

( ) ,

(

) ,

( )

, (

22 22

21 21

12 12

11

11  



 





b a

b p₁ a

p₂

q₁ q₂









   

1 ,

0 ,

00, 0, 1

2 1

2

1 q q q

q

p p

22 1

1 1

1

22 1

22 21

1 12 22

1 1 12

22 21

11

22 1

1 1

1

22 1

22 21

1 12 22

1 1 12

22 21

11

ˆ ~ ˆ)

( ) ( )} ( ) ( )

) {(

, (

ˆ ~ ˆ)

( ) ( )} ( ) ( )

) {(

, (

b q

c p

c q

p c c

b q

b b

p b

b q

p b

b b

b E

a q

r p

r q

p r r

a q

a a

p a

a q

p a

a a

a E

T B

T A







        

    

        



Bq p

q p

Aq p

q p

プレイヤーＡ，Ｂが混合戦略をとった際の期待利得









)) 1 , 0 ( , ( )

,

( , ) ( ,(1,0)) (

) ), 1 , 0 ((

) ,

( , ) ((1,0), ) (

p q

p

p q

p

q q

p

q q

p

B B

A A

E E

E

Theorem 2 より， E

Nash均衡点

(11)

2 人非協力非零和ゲーム

 2

人非協力非零和ゲームの

Nash

均衡点



プレイヤーＡの最適応答について







   

 











        

 





0 ˆ}

ˆ)

{( ˆ) ˆ}(1 ) 0 {(

~ ˆ ~

ˆ) (

ˆ ~ ˆ)

~ ( ) ˆ

( ˆ

) ), 1 , 0 ((

) ,

( , ) ((1,0), ) (

1 1

22 1

1 1

1

22 1

1 22

1 1

p r q

r r

p r

q r r

a q

r a

q r p

r q

p r r

a q

r r q

r r

a q

r p

r q

p r r

E E

A A

A

A p q q

q q

p

1

1 ˆ 0

ˆ)

(r  r q  r 

となる

q



 

 0 0 1

1

p 1

p

1

1 ˆ 0

ˆ)

(r  r q  r 

となる

q

1

1 ˆ 0

ˆ)

(r  r q  r 

となる

q

 

任意任意

: : 1

1

p 1

p



 

 0 0 1

1

p 1

p

故に，pR_A(q) となるためには，

1 1 p

: 任意

p1 1  0 p

(12)

2 人非協力非零和ゲーム

 2

人非協力非零和ゲームの

Nash

均衡点



プレイヤーＢの最適応答について







   

 













        

 





0

~} ˆ)

{( ˆ) ~}(1 ) 0 {(

~ ˆ ) ˆ

( ˆ

ˆ ~ ˆ)

~ ( ) ˆ

( ˆ

)) 1 , 0 ( , ( )

,

( , ) ( ,(1,0)) (

1 1

22 1

1 1

1

22 1

1 22

1 1

q c p

c c

q c

p c c

b p

c b

q c p

c q

p c c

b c

p c p

c c

b q

c p

c q

p c c

E E

B B

B

B p q p

p q

p

1

1 ~ 0

ˆ)

(c  c p  c 

となる

p



 

 0 0 1

1

q 1

q

 

任意任意

: : 1

1

q 1

q



 

 0 0 1

1

q 1

q

故に，q R_B( p) となるためには，

1 1 q

: 任意

q1 1  0 q

1

1 ~ 0

ˆ)

(c  c p  c 

となる

p

1

1 ~ 0

ˆ)

(c  c p  c 

となる

p

(13)

2 人非協力非零和ゲーム

 2

人非協力非零和ゲームの

Nash

均衡点



例：

Ａ＼Ｂ s_B1 s_B2 s_A1 ^(6,5) ^(2,7) s_A2 ^(3,4) ^(6,1)

4 ˆ 7

ˆ)

(r  r q₁  r  q₁  p₁

p₂

q₁ q₂















     

    

















    

    

3 1

~ˆ 154 74 16 3 6

~ˆ 663 32 34

22 21

12 22

21 11

22 21

12 22

21 11

b b

c

b b

c

b b

c

a a

r

a a

r

a a

r





















0 7 :

4 7 : 4

1 7 :

4

1 1

p q

任意























0 5 :

3 5 : 3

1 5 :

3

1 1

q p

任意

3

~ 5 ˆ)

(c  c p₁  c   p₁ 

p₁ q₁

0 1

1

4/7

3/5

プレイヤーＡの最適応答プレイヤーＢ

の最適応答 Nash均衡点

(14)

2 人非協力非零和ゲーム

^Ａ^＼^Ｂ ^s^B1 ^s^B2

s_A1 ^(6,5) ^(2,7) s_A2 ^(3,4) ^(6,1)

0

0.25

0.5

0.75

1 player A

0

0.25 0.5

0.75 1

player B 2

3 4 5 6 Exp

0

0.25

0.5 player A 0.75

E_A(p,q)

0

0.25

0.5

0.75

1 player A

0

0.25 0.5

0.75 1

player B 0

2 4 6 Exp

0

0.25

0.5 player A 0.75

E_B(p,q)

E_A(p,(4/7,3/7))=30/7 E_B((3/5,2/5), q)=23/5

p₁ q₁

0 1

1

4/7

3/5

(15)

2 人非協力非零和ゲーム

 Theorem 3



（混合戦略まで拡大すると，）双行列ゲームには，少なくとも

1

つ

Nash

均衡点が存在する

 Theorem 4

（

cf. Theorem 2

）



（混合）戦略の組が

Nash

均衡点であるための必要十分条件は，が写像の不動点であること．即ち，

*)

*, (p q

*) (

*

* q q p

p   R_A  R_B

*)

*, ( p q

戦略の組が均衡点であるための必要十分性（Theorem 2, 4など）

の証明は，「Brouwerの不動点定理」「角谷の不動点定理」などから

) ( )

(q _B p

A R

R 

(16)

演習１：



次の双行列ゲームの

Nash

均衡点を求めよ

Ａ

＼

Ｂ s

_B1

s

_B2

s

_A1 ^{(-2 , 1)} ^{( 4 , 6)}

s

_A2 ^{( 6 , -8)} ^{(-2 , 2)}

(17)

Coffee Brake!

 John F. Nash (1928- )



紹介サイトの情報

 A Beautiful Mind

いずれも2004年11月9日（火）取得の情報 Non-Cooperative Games Nash [pdf]

(18)

補足： 2 人非協力零和ゲーム

 2

人非協力零和ゲームの

Nash

均衡点

 例：プレイヤーAの利得表

Ａ＼Ｂ s_B1 s_B2 s_A1 ³ ^-2 s_A2 ^-1 ⁴

6 ˆ 10

ˆ)

(r r q₁ r  q₁

p₁ p₂

q₁ q₂















      

      

















     

     

5 ) 4 (

~ˆ ((1 34)) 12 46 5 4

) 1

~ˆ 34( (( 12)) 46

22 21

12 22

21 11

22 21

12 22

21 11

b b

c

b b

c

b b

c

a a

r

a a

r

a a

r























0 5 :

3 5 : 3

1 5 :

3

1 1

p q

任意





















0 2 :

1 2 : 1

1 2 :

1

1 1

q p

任意

5

~ 10 ˆ)

(c c p₁ c  p₁ 

p₁ q₁

0 1

1

3/5

1/2

プレイヤーＡの最適応答

Nash均衡点プレイヤーＢ

の最適応答 4

5 6

10 )

,

(  p₁q₁  p₁  q₁  E p q







 









 

 6 4, ((((10,,01),), )) 55 2 4 ))

1 , 0 ( ,

( ,(1,0)) 4 1 (

1 1 1

1 E p

q E

p E

q q p

p

p₁ E

1 0 1/2

1 E

1

0 3/5 q₁

零和ゲームの場合は

最適応答戦略

ミニマックス戦略いずれの考え方でも均衡解を求められるよ

(19)

2 人非協力非零和ゲーム



例２：囚人のジレンマ

prisoner’s dilemma



２人の凶悪犯が別個に取り調べを受けている



現状では証拠不十分で軽い罪でしか起訴できないため，２人とも

3

年



各囚人は司法取引を持ちかけられ，応じた方は

1

年，応じない方は

10

年，ただし，２人ともが応じた場合は２人とも

8

年

A^＼B

黙秘自白

黙秘

(3,3) (10,1)

自白

(1,10) (8,8)

※司法取引：被告が自分の罪を認める代わりに罪を軽くしてもらうこと注意：値が小さい

方が嬉しい！

(20)

最適応答原理に従ってまじめに計算しても…

2 人非協力非零和ゲーム



例２：囚人のジレンマ

prisoner’s dilemma

A^＼B

黙秘自白

黙秘

(3,3) (10,1)

自白

(1,10) (8,8)

注意：値が小さい方が嬉しい！

各プレイヤーとも，「自白」が支配戦略！結果として，

（自白，自白）がNash均衡点であり，ゲームは支配可解

} {⁽⁽⁰^,¹^),^q⁾⁰ ^ ^q ^ ¹

A  D

最適応答原理に従って考えても…，

} {⁽ ^p^,⁽⁰^,¹⁾⁾⁰ ^ ^p ^ ¹

B  D

p₁ p₂

q₁ q₂

 

}

{

⁽⁰^,¹^),⁽⁰^,¹⁾

: D_A  D_B  D

p₁ q₁

0 1

1











    

 ˆ) ~ 0 2 0

( ˆ) ˆ 0 2 0

(

1 1

1

1 c p

p c c

q r

q r r



 00

1

q1

p

注意：±逆で計算

明らかにもっと良い解がある Pareto最適でない！

(21)

2 人非協力非零和ゲーム

 Nash

均衡点が最適戦略か？

 2

人零和ゲーム

• ミニマックス戦略が最適戦略！

 2

人非零和ゲーム

• Nash均衡点が最適戦略を与えるわけではない！

• ゲームの値が異なる複数の均衡点が存在する場合がある！

• Nash均衡点は，必ずしもPareto最適ではない！

行動の指針を与えてくれる

最適応答原理は不十分かも…！？

（しかし他に適切なものがあるか？）

•得られる解の状態を示すことで，何らかの均衡戦略をとるべきことを教える

•均衡状態が複数あることを示すことで，戦略決定判断が困難であることも教える

非協力ゲーム

Nash均衡点の精緻化協力ゲームへの転換

人非協力非零和ゲーム

意思決定科学： ゲーム理論２

情報学部 堀田敬介

Contents

人非協力非零和ゲーム

定義：ゲームのルール，双行列

例：囚人のジレンマ，面会ゲーム，恋人達のジレンマ，

最適応答，

均衡点

均衡点と線形相補性問題（

）

戦略形ゲームの社会・経済問題への応用例

：

プレイヤーは

と

の

人

各プレイヤーは，独立に自分の戦略を決定

（非協力）

プレイヤーの利得の和は一定とは限らない

（非零和）

純粋戦略の数は有限

2 人非協力非零和ゲーム

＼

，

の利得表

2 人非協力非零和ゲーム

双行列ゲーム

利得関数

利得行列

2 人非協力非零和ゲーム

例１：恋人達のジレンマ

ある一組のカップルがデートをしたいと思っている

男性は野球観戦を希望し，女性は映画鑑賞がしたい

各々が好きなものを見るより一緒にいることの方が大事

男

女 野球 映画

野球

映画

2 人非協力非零和ゲーム

例１：恋人達のジレンマ

最適応答対応

最適応答と最適応答対応

最適応答

2 人非協力非零和ゲーム

} {

} {

} {

最適応答と最適応答対応

2 人非協力非零和ゲーム

例：

2 人非協力非零和ゲーム

均衡点

（混合）戦略の組 が次の条件を満たすとき，

を

均衡点とよぶ

（混合）戦略の組 が互いに最適応答であるならば

均衡点であり，逆も成り立つ．即ち，

均衡点の集 合を

とすると，

（混合）戦略の組 が

均衡点であるた めの必要十分条件は

2 人非協力非零和ゲーム

人非協力非零和ゲームの

均衡点

2 人非協力非零和ゲーム

人非協力非零和ゲームの

均衡点

プレイヤーＡの最適応答について

となる

となる

となる

2 人非協力非零和ゲーム

人非協力非零和ゲームの

均衡点

プレイヤーＢの最適応答について

となる

となる

となる

2 人非協力非零和ゲーム

意思決定科学：ゲーム理論２

情報学部堀田敬介

女野球映画

（混合）戦略の組が次の条件を満たすとき，

（混合）戦略の組が互いに最適応答であるならば

均衡点の集合を

（混合）戦略の組が

均衡点であるための必要十分条件は

（混合戦略まで拡大すると，）双行列ゲームには，少なくとも

（混合）戦略の組が

均衡点であるための必要十分条件は，が写像の不動点であること．即ち，

現状では証拠不十分で軽い罪でしか起訴できないため，２人とも

年，応じない方は

黙秘自白

黙秘自白