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

(1)

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

堀田敬介

2014/11/14,Fri.

^～

2 人非協力零和ゲーム

(5)



Example1 ：

• 2人のプレイヤーA君とBさんが「コインあわせゲーム」

をしている

• プレイヤーは同時にコインの表か裏を見せ合う

• 2人のプレイヤーの見せた面が同じならA君の勝ち，

異なるならBさんの勝ち

• 表を出して勝ったら相手から2円貰い，裏を出して勝ったら相手から1円貰う

2人非協力零和ゲーム

A ＼ B 表裏

表 2 -1 裏 -2 1

A

君の利得表

N={1, 2}

Si={s_i1, s_i2}, (i∈N)

fi:S₁×S₂→ R, (i∈N) f1(表, 表) = 2 +

f1(表, 裏) = -1 + f1(裏, 表) = -2 + f1(裏, 裏) = 1 +

f2(表, 表) = -2 =0 f2(表, 裏) = 1 =0 f2(裏, 表) = 2 =0 f2(裏, 裏) = -1 =0 S₁={表, 裏}, S₂={表, 裏}

A ＼ B 表裏

表 -2 1 裏 2 -1

B

さんの利得表



Example2 ：

• A君とBさんがゲームをしている．それぞれ3つずつの戦略があり，A君の利得

表は以下の通りである．2人は，各々どんな戦略をとるべきか？

2 人非協力零和ゲーム

A ＼ B s

_B1

s

_B2

s

_B3

s

_A1

-2 4 -1

s

_A2

2 2 1

s

_A3

4 -3 0



ミニマックス原理 minimax principle

• Example2

でプレイヤー

A

の思考

•

戦略

s_A1

を取ったときの最悪の事態は

min(-2, 4, -1) = -2

（プレイヤー

B

が戦略

s_B1

^を取る）

•

戦略

s_A2

を取ったときの最悪の事態は

min(2, 2, 1) = 1

（プレイヤー

B

が戦略

s_B3

^を取る）

•

戦略

s_A3

を取ったときの最悪の事態は

min(4, -3, 0) = -3

（プレイヤー

B

が戦略

s_B2

^を取る）

2人非協力零和ゲーム

A＼B s_B1 s_B2 s_B3

s_A1 -2 4 -1

s_A2 2 2 1

s_A3 4 -3 0

最大化プレイヤー

戦略 s

_A2

を取る（最悪でも利得

1

が保証される）

もっと良い利得を得ることができるのか？



ミニマックス原理 minimax principle

• Example2

でプレイヤー

A

が

B

の立場で思考

• B

が戦略

s_B1

^{を取ったとき，}

A

である自分は戦略

s_A3

^を取る

max(-2, 2, 4) = 4

• B

が戦略

s_B2

^{を取ったとき，}

A

である自分は戦略

s_A1

^を取る

max(4, 2, -3) = 4

• B

が戦略

s_B3

^{を取ったとき，}

A

である自分は戦略

s_A2

^を取る

max(-1, 1, 0) = 1

2人非協力零和ゲーム

s_A1 -2 4 -1

s_A2 2 2 1

s_A3 4 -3 0

戦略 s

_B3

を取る（最悪でも損失

1

で済む）

A

は戦略 s

_A2

^{を取るとき，利得}

¹

^{を得られ，}

それ以外の戦略を取ると利得が

1

以下になる．

(6)



ミニマックス原理

• Example2

：

2 人非協力零和ゲーム

A ＼ B s

_B1

s

_B2

s

_B3

min max

s

_A1

-2 4 -1 -2

1 s

_A2

2 2 1 1

s

_A3

4 -3 0 -3

max 4 4 1

min 1

保証水準security level

保証水準 security level

マキシミン値 maximin value

ミニマックス値 minimax value

j ij

i a

v₁maxmin

i ij

j a

v₂minmax

マキシミン原理 maximin principle

〔最大化プレイヤーの行動原理〕

ミニマックス原理 minimax principle

〔最小化プレイヤーの行動原理〕

v

1

 v

2



均衡点とゲームの値

• 2

人のプレイヤーがともにミニマックス原理に基づいて行動すると，どうなるのか？

2 人非協力零和ゲーム

1 min max max

min  _ij

j ij i

i

j a a

2

人共に勝つことはあり得ない！

何らかの意味での均衡に到達

しかたない…

やむをえない…

2

人零和ゲームが

「厳密に決定される

strictly determined

」

「厳密に確定的である」

（ s

_A2*,

s

_B3*

）：ゲームの均衡点

equilibrium point

s_A1 -2 4 -1

s_A2 2 2 1

s_A3 4 -3 0

演習１：



プレイヤー

A

の利得表が以下の表で与えられるゲームを考える．

プレイヤー

A

，

B

がそれぞれミニマックス原理に基づいて戦略決定をすると，ゲームの解はどうなるか？（１），（２）それぞれのゲームについて考えよ

A ＼ B s

_B1

s

_B2

s

_B3

s

_A1

3 1 -1

s

_A2

-1 0 2

s

_A3

5 2 3

（１）

A ＼ B s

_B1

s

_B2

s

_B3

s

_A1

5 6 4

s

_A2

1 8 2

s

_A3

7 2 3

（２）



純粋戦略と混合戦略

•

Example3 ：

• A君とBさんがゲームをしている．それぞれ3つずつの戦略があり，A君の

利得表は以下の通りである．2人は，各々どんな戦略をとるべきか？

2 人非協力零和ゲーム

A ＼ B s

_B1

s

_B2

s

_B3

s

_A1

-4 2 0

s

_A2

4 3 1

s

_A3

1 -3 2

(7)



純粋戦略と混合戦略

•

Example3 ：

2 人非協力零和ゲーム

A

＼

B

s

_B1

s

_B2

s

_B3

min max

s

_A1

-4 2 0 -4

1 s

_A2

4 3 1 1

s

_A3

1 -3 2 -3

max 4 3 2

min 2

j ij

i a

v maxmin 1 ₁

i ij

j a

v minmax 2 ₂

ミニマックス均衡点が存在しない！？

マキシミン戦略

ミニマックス戦略



純粋戦略と混合戦略

• Proposition1

利得行列

A=[a_ij]

が与えられた時，以下が成り立つ

2 人非協力零和ゲーム

i ij ij j

i minj a minmaxa

max 

ゲームは常に厳密に決定されるとは限らない！

いかなる場合に均衡点が存在し，

ゲームが厳密に確定的であるか？



純粋戦略と混合戦略

•

鞍点 saddle point

•

行列A=[a

_ij]において，任意のi, j に対し，

が成り立つとき，（i

₀, j₀

）をこの行列の鞍点といい，a

_i₀_j₀

を鞍点値という．

2 人非協力零和ゲーム

j i j i

ij

a a

a

₀



₀ ₀



₀

a a

a

a A

mn mj

n i j

i

m i

n j

ij





































0

0 0

0

1 1

11

]

[

0 0

0 ij

ij a

a 

j i j

i a

a₀₀ ₀

鞍点

maximin player の視点

minimax player の視点

0 0j

ai



純粋戦略と混合戦略

• Theorem1

•

（行列）ゲームが厳密に確定的であるための必要十分条件は，その利得行列Aに少なくとも1つの鞍点が存在すること．またこのとき，鞍点が均衡点．

2 人非協力零和ゲーム

•

最適戦略 optimal strategy

•

均衡点（

i*,j*

）は鞍点なので，プレイヤー

A

が戦略

i*

を用いると，プレイヤー

B

がいかなる戦略をとっても少なくとも

v(A)

を得ることができ，また，

B

が戦略

j*

を取る限り，

A

は戦略を変えても利得を増加させることはできない．

戦略

i*

^が

A

の最適戦略

(8)



純粋戦略と混合戦略

• Theorem2

•

厳密に確定的な零和ゲームにおいて，均衡点が複数ある場合，各均衡点の値は等しい．また，(i, j), (i

₀, j₀) が

均衡点ならば，

(i*, j₀), (i₀, j*)

も均衡点である．

2 人非協力零和ゲーム

均衡戦略は交換可能

a a

a a i

i

j j

j i j i

 





 





*

* 0

0

0 0 0 0

*



純粋戦略と混合戦略

•

Example3 ：

2 人非協力零和ゲーム

A ＼ B s

_B1

s

_B2

s

_B3

s

_A1

-4 2 0

s

_A2

4 3 1

s

_A3

1 -3 2

完全予見は不可能！

決断は下さねばならない！

主体的な賭，

最適な賭の確率

期待効用原理



純粋戦略と混合戦略

• Example3

：

2 人非協力零和ゲーム

A

＼

B s_B1 s_B2 s_B3

s_A1 -4 2 0

s_A2 4 3 1

s_A3 1 -3 2

p₁ p₂ p₃

q₁ q₂ q₃

1 ) 3 , 2 , 1 ( , 0

3 2 1  

p p p

i p_i

1 ) 3 , 2 , 1 ( , 0

3 2

1  



 q q q

j q_j

純粋戦略

pure strategy

混合戦略

mixed strategy

s_A1 -4 2 0

s_A2 4 3 1

s_A3 1 -3 2



純粋戦略と混合戦略

• Example3

：

• player Aの期待効用（player A = 期待効用最大化プレイヤー= maximin player）

← player B が戦略s_B1の時の期待効用

• player Bの期待損失（player B = 期待損失最小化プレイヤー= minimax player）

← player A が戦略s_A1の時の期待損失

2 人非協力零和ゲーム

p₁ p2

p₃

q₁ q₂ q₃









  

  



3 2 1

3 2 1 1

2 ) (

3 3 2 ) (

4 4 ) (

3 2 1

p p s

E

p p p s E

B B B

p, p, p,











  



3 2 1 2

2 1 2

2 3 ) , (

3 4 ) , (

2 4 ) , (

3 2 1

q q q s

E

q q q s

E

q q s

E

A A A

q q q

補足：A, Bが各々混合戦略(p₁,p₂,p₃), (q₁,q₂,q₃)のとき



   

3 2

1 2

3 2

1

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

) , ( ) , ( ) , ( ) , (

3 2

1

3 2

1

p s E p s E p s E E

q s E q s E q s E E

A A

A

B B

B

q q

q q p

p p

p q p

) ( ) ( : )

(p,q E1 p,q E2 p,q

E  

(9)



戦略の支配

• Example3

：

2 人非協力零和ゲーム

A ＼ B s

_B1

s

_B2

s

_B3

s

_A1

-4 2 0

s

_A2

4 3 1

s

_A3

1 -3 2

> > >

A ＼ B s

_B1

s

_B2

s

_B3

s

_A2

4 3 1

s

_A3

1 -3 2

>

A ＼ B s

_B2

s

_B3

s

_A2

3 1

s

_A3

-3 2

支配する dominate 被支配戦略

支配戦略

戦略の支配domination of strategies プレイヤーi の戦略h, k について，

戦略h が戦略k を支配するとは，

任意のに対して，

が成立すること．

i

i S

s_  _ ) , ( ) ,

(s h f s k

f_i __i  _i __i

被支配戦略除去の原理

「支配される戦略は用いない」

•＝だと「同等」

•≧かつ≠

だと「弱支配」

補足）通常は，被弱支配戦略は除去しない→共有地の悲劇

補足：被支配戦略除去の原理による均衡点が存在

→ ゲームは支配可解dominance solvable



最適混合戦略

• Example3

：

• player A =

期待効用最大化プレイヤー

= maximin player

← player B

が戦略

s_B2

の時の期待効用

← player B

が戦略

s_B3

の時の期待効用

• player B =

期待損失最小化プレイヤー

= minimax player

← player A

が戦略

s_A2

の時の期待損失

← player A

が戦略

s_A3

の時の期待損失

2 人非協力零和ゲーム

^A

^＼

^{B s}B2 s_B3

s_A2 3 1

s_A3 -3 2 p₂

p₃

q₂ q₃



   2 ))

1 , 0 (

( (1,0)) 6 3 (

2

p2

E

p E

p, p,



  

2 5 ) ) 1 , 0

((1,0) ) 2 1 ((

2 2q E

q E

q ,

p2

E₁

1

0 5/7 q2

E₁

1 0 1/7 9/7 一致 2

1 v

v 

Aの最適戦略 p*=(0, 5/7, 2/7)

Bの最適戦略 q*=( 0, 1/7, 6/7)

(p*,q*)：均衡解

0 0.25

0.5

0.75

1 player A

0 0.25

0.5 0.75

1

player B -2

0 2 Exp

0 0.25

0.5 player A 0.75



最適混合戦略

• Example3

：

2 人非協力零和ゲーム

player B player A

  



 



 

 





 



 





 









   

 



) 1 (

2 3

1 1 3

) 1 ))(

1 ( 2 ( )) 1 ( 3 3

(3 3 ) ( 2 )

(( ) ( )

) (

2 2 2 2

2

2 2 2 2 2 2

3 3 2 2 3 2

3

2 3

2

q p, p,

p, q p,

q E p q

p

q p p q p p

q s E q s E

E B B

0 0.25 0.5 0.75 1

player A

0.250.50 0.751 player B

-2 0 2

Exp

0.250.750.501 player A

0 0.25 0.5 0.75 1

player B

-2 0 2

Exp

2 人非協力零和ゲーム

^A＼B ^s^B2 ^s^B3

s_A2 3 1

s_A3 -3 2

p2

p₃

q₂ q₃

0 0.25

0.5 0.75

1 playerA

0 0.25

0.5 0.75

1

playerB -2

0 2 Exp

0 0.25

0.5 0.75 playerA

player A maximin player

player B minimax player

5/7

1/7



最適混合戦略

• Example3

：

(10)



混合戦略の意味

• p*,q*

の確率のくじをつくって，引いていずれかに決する方法が，なぜ合理的な決定方法なのか？

2 人非協力零和ゲーム

^A＼B ^s^B2 ^s^B3

s_A2 3 1

s_A3 -3 2

p2

p3

q₂ q₃

Aの最適戦略p*=(0, 5/7,2/7) Bの最適戦略q*=( 0, 1/7,6/7)

• player A

は

S_A2

なら

3

，

S_A3

なら

2

が望ましいが，

の確率で望ましくない結果になる．

49

* 32

2

* 3

*

2q pq 

p

しまった！

•

このような状況も全て考慮に入れた上で，最適戦略が決定された！

しかし，これは事後的

演習２：



プレイヤー

A

の利得表が以下の表で与えられるゲームを考える．

プレイヤー

A

，

B

がそれぞれ期待効用原理に基づいて戦略決定をすると，ゲームの解はどうなるか？

A ＼ B s

_B1

s

_B2

s

_A1

4 -2 s

_A2

-3 3

（１）

A ＼ B s

_B1

s

_B2

s

_B3

s

_B4

s

_A1

3 1 3 4

s

_A2

4 4 2 3

s

_A3

2 3 1 2

（２） A ＼ B s

_B1

s

_B2

s

_A1

3 1

s

_A2

-1 5 A ＼ B s

_B1

s

_B2

s

_B3

s

_A1

3 2 4

s

_A2

-1 3 0

s

_A3

2 1 -2

（３）（４）



ミニマックス定理

•

プレイヤー

A, B

の純粋戦略

•

プレイヤー

A

の利得行列（

B

の損失行列）

2 人非協力零和ゲーム

a a a

a a a a

mn m m

n n

ij

























2 1

2 22 21

1 12 11

] [ A

} , , 1

| { }, , , 1

|

{s i m S s j n

SA Ai   B Bj  

•

プレイヤー

A, B

の混合戦略

)

, , (p₁ p_m

 p



     , 0 ,

, 1

1 1

m

p m

p p p 



   0 ,

, 1

1 1

n n

q q

, ) , (q₁q_n

 q

利得関数



 



 ^m

i n

j j i ijpq a E

1 1

) ,

(pq p^TAq

) 0 , , 1 , , 0

(  

i sA

) 0 , , 1 , , 0

(  

j  sB



ミニマックス定理

•

プレイヤー

A

の保証水準

•

プレイヤー

B

の保証水準

2 人非協力零和ゲーム

) , ( min p q

q E

) , (

max p q

p

E

) , ( min

1 max p q

q

p E

v 

) , ( max

2 min p q

p

q E

v 

p を操作して期待利得最大

q を操作して期待損失最小

) , ( max min )

, ( min

max p q p q

q p

p q

E  E

• Proposition2

(11)



ミニマックス定理

• Theorem3

また，これを成立させる戦略の組（p, q）を均衡点といい，

均衡点における利得

v(A) をゲームの値という．

2 人非協力零和ゲーム

) , ( max min )

, ( min

max p q p q

q p

p q

E  E

J. von Neumann, 1928



 



 ^m

i n

j

j i ij

T a p q

v

1 1

*

* *

* : )

(A p Aq

• Theorem4

戦略の組（p, q）が均衡点であるための必要十分条件は，

（p, q）が関数

E(p, q) の鞍点であること．即ち，

が成立すること．

)

*, (

*)

*, (

*) , ( ,

,q p q p q p q

p E E E



均衡点における戦略が最適戦略

Aがp*の時，Bはq*にするのが損失最小 Bがq*の時，Aはp*にするのが利得最大



ミニマックス定理

• Theorem5

v(A)

がゲームの値，（

p*, q*

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

が成立すること．

2 人非協力零和ゲーム

)

*, (

*)

*, (

*) , ( ,

,j E sAi E E sBj

i q  p q  p



*)

*, (

, , ,

1 ⁿ

1 j

* E p q

q a m

i _ij _j 





 









 ^m

1 i

*) *

*, ( , , ,

1 n E a_ijp_i

j  p q



ミニマックス定理

•

Example4

2 人非協力零和ゲーム

A ＼ B s

_B1

s

_B2

s

_B3

s

_B4

s

_B5

s

_A1

-2 -1 2 3 3

s

_A2

5 2 4 -1 0

s

_A3

4

^<

1

^<

3

^<

-2

^<

-1

^<

<

≦ p₁ ≦

p₂

q₃

q₂ q₄ q₅

q₁

1

1 2 1

3 ) , (

1 4 3

) , (

4 2 4 2 ) , (

2 3 2 )

, (

5 7 5 2 ) , (

5 4 3 2 1

p s E

p p p s

E

p p p s

E

p p p s

E

p p p s

E

B B B B B

   

   

   



p p p p p

p1

E1

1 0

p2

0 1

4/7

) 0 7, ,3 7 (4

* p



ミニマックス定理

•

Example5 ^：一般の

2

×

2

ゲーム

2 人非協力零和ゲーム

A

＼

B

s

_B1

s

_B2

s

_A1 ^a11 a₁₂

s

_A2 a₂₁ a₂₂ p₁

p₂

q₂ q₁

鞍点が存在すればそれが均衡点．

なければ，混合戦略を考えるが，

このとき，必ずE(p,s_B1)とE(p,s_B2)及びE(s_A1,q)とE(s_A2,q)は交点を持つ．

均衡点



 















 

12 22 21 11

12 11 12 22 21 11

21

* 22 2

*

1, ) ,

( a a a a

a a a a a a

a p a

p



 















 

21 22 12 11

21 11 21 22 12 11

12

* 22 2

*

1, ) ,

( a a a a

a a a a a a

a q a

q



  



  

2 22 1 21

2 12 1 11

2 22 1 12

2 21 1 11

) (

) , (

2 1

q a q a s E

p a p a s E

A A

B B

q q p p

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