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

(1)

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

情報学部堀田敬介

2009/11/14,Sat.

^～

• The partners being ranged A,B,C,…,N. A cuts from the cake an arbitrary part. B has now the right, but is not obliged, to diminish the slice cut off. Whatever he does, C has the right (without obligation) to diminish still the already diminished (or not diminished) slice, and so on up to N. The rule obliges the ``last-diminisher’’ to take as his part the slice he was the last to touch. This partner thus disposed of , the remaining n- 1 persons start the same game with the remainder of the cake.

After the number of participants has been reduced to two, they apply the classical [divide-and-choose] rule for halving the remainder.

(from ``Fair Division’’, p.35 [Steinhaus’ description 1948 p.102])

S. Banach-B. Knaster, mid-1940

ケーキを仲良く

 The last-dimisher procedure

• proportional division を保証する各プレイヤーの戦略

•

切るプレイヤーがちょうど1/nと考えるpiece に切ること

• envy-free ではない

•

理由：例えば，ゲームを先に抜けたプレイヤーAが，ある段階で切られたケーキが1/nより大きい（とAが思う）ときでもそれを阻止できない．結果として1/nより大きいケーキが誰か（B）に行く（とAが思う）ので，AはBを妬む．

(4)

ゲーム理論とは何か？

 ゲーム的状況 game situations

• 複数の意思決定主体（プレイヤー）が存在し，各々目的を持ち，その実現を目指して相互に依存しあっている状況



ゲーム理論 game theory

• ゲーム的状況を数理モデルを用いて定式化し，プレイヤー間の利害の対立と協力を分析する理論

J. von Neumann & O. Morgenstern

「ゲーム理論と経済行動」（1944）

John von Neumann (1903-1957)

2004年11月9日（火）取得の情報

ゲーム理論とは何か？



プレイヤー player

•

意思決定し，行動する主体．（2人，3人，…，n人，…，∞）

• 例：個人，複数の個人から成る組織，政党，国家，…



戦略 strategy

•

プレイヤーが取りうる行動．（有限，無限）



利得と利得関数 payoff

•

各プレイヤーの戦略決定後，ゲームは終了し，結果が出る．結果に対する各プレイヤーの何らかの評価値．利得

payoff，効用 utility．



協力の可能性

•

各プレイヤーは自由に自己の判断で行動．

• 協力ゲーム：十分にコミュニケーション可能で，合意の上で戦略を決定．

• 非協力ゲーム：各自の独立な判断により，戦略を決定．



ゲームの表現形式

• 展開形 extensive form

• 戦略形 strategic form ，標準形 normal form

ゲーム理論とは何か？

A ＼ B S _B1 S _B2

S _A1 3 1

S _A2 -4 6

A B

(3,-3) (-1,4) (2,-6) (-2,1) S

_A1

S

_A2

S

_B1

S

_B1

S

_B2

S

_B2



ゲームの定義（戦略形 n 人ゲーム）

ゲーム理論とは何か？

) } { , } { ,

( N S _i _i _N f _i _i _N

G  _ _



 







 



R S S

f s s s

S N n

n i

im i

i

i   

1 2

: { { 1 , 1 2 , , , , } , } ^{：プレイヤーの集合}

：プレイヤー i の戦略集合

：プレイヤー i の利得関数

各プレイヤーは自己の利得最大化を目指し，

G は全てのプレイヤーの共有知識とする．

(5)



非協力ゲームと協力ゲーム

• 各プレイヤーの戦略決定における前提

ゲーム理論とは何か？

) ( } , , ,

{ s ₁ s ₂ s i N

S _i  _i _i  _im 

1. プレイヤー間には，各プレイヤーがとるべき戦略について，強制力のある取り決めは存在しない．

2. 全てのプレイヤー間に，とるべき戦略についての合意が成り立ち，それに基づいて戦略決定する．

拘束的合意が成立しない

拘束的合意が成立

非協力ゲーム

協力ゲーム



ゲームのルール

• プレイヤーの数は2人

• 各プレイヤーは，独立に戦略を決定（非協力）

• プレイヤーの利得の和は，常に零（零和）

• ゲームは 1 回限り

• 各プレイヤーは戦略決定時に，他のプレイヤーがどの戦略をとるかは知らない

• 各プレイヤーの取りうる戦略は有限

2 人非協力零和ゲーム

0 ) , ( ) ,

( , ) ,

(

2 1 2 2 1 1

2 1 2

1

   

 f s s s s S f s S s }

2 , 1

 { N



  

} , , ,

{ , , , }

{

2 22 21 2

1 12 11 1

n

s

m

s s

S s s s

S





利得行列 payoff matrix

• 零和ゲーム，即ち，

なので，

とおくと，取りうる戦略と利得の関係を行列 A で表せる

2 人非協力零和ゲーム

0 ) , ( ) , ( , ) ,

(

₁ ₂



₁



₂ ₁ ₁ ₂



₂ ₁ ₂



 s s S S f s s f s s )

, ( ) ,

(

₂

1 i j i j

ij

f s s f s s

a   

a a

a

a a

a

a a

a a A

mn m

m

n n

ij

 





 

















2 1

2 22

21

1 12

11

] [

利得行列



Example1 ：

•

A君とBさんがトランプで簡単なゲームをしている．双方とも予め2枚のカード

を持っており，1回だけ1枚のカードを出し，カードの目の差を利得としてもらえるというゲームである．さて，A君は「スペードの4」「ハートの7」の2枚，Bさん

「クラブの2」「ダイヤの10」の2枚のカードを持っていることが互いに分かっている時，2人はどのようにカードを出すべきか？

2 人非協力零和ゲーム

A ＼ B

^{クラブの2} ^{ダイヤの10}

スペードの4

2 -6

ハートの7

5 -3

A ＼ B

^{クラブの2} ^{ダイヤの10}

スペードの4

-2 6

ハートの7

-5 3

A君の利得表 Bさんの利得表

ゲームの解：（ハートの7，ダイヤの10）ゲームの値

(6)



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

min(2, 2, 1) = 1

s

_B3^を取る）

•

戦略

s

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

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を得られ，

それ以外の戦略を取ると利得が1以下になる．



ミニマックス原理

• 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

₁

 max min

i ij

j

a

v

₂

 min max

マキシミン原理

maximin principle

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

ミニマックス原理

minimax principle

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

v 1  v 2

(7)



均衡点とゲームの値

• 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

 純粋戦略と混合戦略

• 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 max min 1 

₁



i ij

j

a

v min max 2 

₂



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

マキシミン戦略

ミニマックス戦略

(8)

 純粋戦略と混合戦略

• Proposition1

利得行列A=[a

_ij

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

2 人非協力零和ゲーム

i ij ij j

j

i

min a min max a

max 

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

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

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

 純粋戦略と混合戦略

• 鞍点 saddle point

• 行列A=[a

_ij

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

が成り立つとき，（i

₀

, j

₀

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

_i0j0

を鞍点値という．

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 0

0

1 1

11

]

[

0 0

0 ij

ij

a

a 

j i j

i

a

00



0

 純粋戦略と混合戦略

• Theorem1

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

2 人非協力零和ゲーム

• 最適戦略 optimal strategy

• 均衡点（i, j）は鞍点なので，プレイヤー A が戦略 i* を用いると，プレイヤー B がいかなる戦略をとっても少なくとも v(A) を得ることができ，また， B が戦略 j を取る限り，* A は戦略を変えても利得を増加させることはできない．

戦略 i* がAの最適戦略

 純粋戦略と混合戦略

• 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

*

(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

完全予見は不可能！

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

主体的な賭，

最適な賭の確率

期待効用原理



純粋戦略と混合戦略

• 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

2

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



 





      



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 s p p p

E

B B B

p, p, p,

プレイヤーBが各戦略をとったときの，プレイヤーAの期待効用

よって，Bが各戦略を(q1

,q

2

,q

3

)の確率でとったときの，Aの期待効用

3 1 2 1 1 1

1

( ) E ( s

₁

) q E ( s

₂

) q E ( s

₃

) q E p, q  p,

B

 p,

B

 p,

B



純粋戦略と混合戦略

• Example3 ：

2 人非協力零和ゲーム

s_A1 -4 2 0

s_A2 4 3 1

s_A3 1 -3 2

p

₁

p

₂

p

₃

q

₁

q

₂

q

₃



 







  

  



3 2 1 2

2 1 2

2 3 ) ,

( , ) 4 3 (

2 4 ) , (

3 2 1

q q q s

E s q q q

E

q q s

E

A A A

q q q

プレイヤーAが各戦略をとったときの，プレイヤーBの期待効用

Aが各戦略を(p

1

,p

2

,p

3

)の確率でとったときの，Bの期待効用

3 2 2 2 1 2

2

( ) E ( s

₁

) p E ( s

₂

) p E ( s

₃

) p E p, q 

_A

, q 

_A

, q 

_A

, q

まとめると，プレイヤーA, Bがそれぞれ確率(p1

,p

2

,p

3

), (q

1

,q

2

,q

3

)で各戦略をとったとき，

各プレイヤーの期待効用は以下のようになる．

 

      

3 2

1 2

3 2

1

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

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

3 2

1

3 2

1

p E s p E s 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 E

1

p, q E

2

p, q

E  

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

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

純粋戦略

pure strategy

混合戦略

mixed strategy



支配戦略

• 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 strategiesdomination of strategies プレイヤー

i の戦略 h, k について，

戦略

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

任意のに対して，

が成立すること．

i

S

s

_



_

) , ( ) ,

( s h f s k

f

_i __i



_i __i

被支配戦略除去の原理被支配戦略除去の原理

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

•＝だと「同等同等」

•≧かつ≠

だと「弱支配弱支配」

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

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

→

ゲームは支配可解ゲームは支配可解dominance solvabledominance solvable

(10)



最適混合戦略

• Example3 ：

2 人非協力零和ゲーム

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

s_A2 3 1

s_A3 -3 2

p

₂

p

₃

q

₂

q

₃

  _



 



    

 





 



 





 









   

 



) 1 (

2 3

1 1 3

) 1 ))(

1 ( 2 ( )) 1 ( 3 3

( 3 3 ) ( 2 )

( ( ) ( )

) (

2 2 2 2

2

2 2 2

3 3 2 2 3 2

3

2 ₃

2

q p, p,

p, q p,

q E p q

p

q p p q p

p p q p p q

p s q E s q

E

B B



      2 ))

1 , 0 (

( ( 1 , 0 )) 6 3 (

2

p

2

E p

E p, p,



      2 5 ) ) 1 , 0

(( 1 , 0 ) ) 2 1 ((

2 2

q

E q

E , , q q

^p²

E1

1

0 5/7 q2

E1

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 0.75

1 player A



最適混合戦略

• Example3 ：

2 人非協力零和ゲーム

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

s_A2 3 1

s_A3 -3 2

p

₂

p

₃

q

₂

q

₃

) 1 ))(

1 ( 2 ( 3 3 ( 1 )) ( ( )

2 2 2

2 2

2

p q

p p p q

E





  

 p, q

player B player B player A

player A

0 0.25 0.5 0.75 1

player A

0.250.50 0.751 player B

-2 0 2

Exp

0 0.25 0.5 0.75 1

player A

0 0.250.750.51 player A

0 0.25 0.5 0.75 1

player B

-2 0 2

Exp

-2 0 2

Exp

2 人非協力零和ゲーム

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

s_A2 3 1

s_A3 -3 2

p

₂

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

1 playerA

player A player A

player B player B

5/7 5/7

1/7 1/7



最適混合戦略

• Example3 ：



混合戦略の意味

• **p,q の確率のくじをつくって，引いていずれかに決する**

方法が，なぜ合理的な決定方法なのか？

2 人非協力零和ゲーム

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

s_A2 3 1

s_A3 -3 2

p

₂

p

₃

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

*

2

q  p q  p

しまった！

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

しかし，これは事後的

(11)

演習２：



プレイヤー 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

S

A



A_i

 

B



B_j

 

• プレイヤー A, B の混合戦略 )

, , ( p

₁

 p

_m

p 



     , 0 ,

, 1

1 1

m

p

m

p p

p

 



     0 ,

, 1

1 1

n

q

n

q q

q

  , ) , ( q

₁

 q

_n

q 

利得関数利得関数



 



^m

i n j

j i ij

p q a E

1 1

) ,

( p q p

^T

Aq ) 0 , , 1 , , 0

(  

i

 s

A

) 0 , , 1 , , 0

(  

j

 s

B



ミニマックス定理

• プレイヤー A の保証水準

• プレイヤー B の保証水準

2 人非協力零和ゲーム

) , (

min p q

q

E

) , (

max p q

p

E

) , ( min

1

max p q

p q

E

v 

) , ( max

2

min p q

p

q

E

v 

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

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

) , ( max min ) , ( min

max p q p q

p q q

p E  E

• Proposition2



ミニマックス定理

• Theorem3

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

均衡点における利得 v(A) をゲームの値という．

2 人非協力零和ゲーム

) , ( max min ) , ( min

max p q p q

p q q

p 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*にするのが利得最大

(12)



ミニマックス定理

• Theorem5

v(A) がゲームの値，（p, q）が均衡点であるための必要十分条件は

が成立すること．

2 人非協力零和ゲーム

)

*, (

*)

*, (

*) , ( ,

, j E s

_A_i

E E s

_B_j

i q  p q  p



*)

*, (

, , ,

1

ⁿ

1 j

*

E p q

q a m

i 

ij j



 















^m

1 i

*)

*

*, ( , , ,

1 n E a

_ij

p

_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

) ,

( , ) 2 4 2 4

(

2 3 2 )

,

( , ) 2 5 7 5

(

5 4 3 2 1

p s E

p p p s

E s p p p

E

p p p s

E s p p p

E

B B B B B

        

           



p p p p p

p1

E1

1 0

p₂1 0

4/7 4/7

) 0 7 , , 3 7 ( 4

*  p



ミニマックス定理

• Example5 ^：一般の 2 × 2 ゲーム

2 人非協力零和ゲーム

A ＼ B s _B1 s _B2 s _A1 a

₁₁

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 2 1

q a q a s

E s a q a q E

p a p a s E

A A B B

q q p 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 _A1 3 1

s _A2 -1 5

(13)



2 人零和ゲームと線形計画法

• プレイヤー A の利得行列と混合戦略 p

2 人非協力零和ゲーム

0 , ,

1 . . . max

1 1 1 1

2 1

12

1 1

11

 



  







  



m m

m mn n

m m

p

p p

p a p u

p a

u p a p

a p a p u

a t

s u







a 

a a

a a a

p p p

mn m m

n n

m

 





 

















2 1

2 22 21

1 12 11 2 1

 

 









   



m mn n

n B

m m B

p a p a p a s E

n







2 2 1 1

2 2 22 1 12

1 2 21 1 11

) , (

2 1

p p p

まとめると…

 ⁽ ^, ^), ⁽ ^, ^), ^, ⁽ ^, ⁾ 

min

max E p s

_B₁

E p s

_B₂

E p s

_B_n

p





2 人零和ゲームと線形計画法

• プレイヤー B の損失行列（ A の利得行列）と混合戦略 q

2 人非協力零和ゲーム

a a a

a a

a q q

q

mn m

m

n n n m

 





 















2 1

2 22 21

1 12 11 1

 

 









   



n mn m

m A

n n A

q a q a q a s E

m







2 2 1 1

2 2 22 1 21

1 2 12 1 11

) , (

2 1

q q q

まとめると…

 ⁽ ^, ^), ⁽ ^, ^), ^, ⁽ ^, ⁾ 

max

min

₁

q

₂

q q

q

E s

A

E s

A

 E s

A^m

0 , ,

1 . . . min

1 1 1 1

2 1 21

1 1 11

 



  







  



n n

n mn m

n n

q

q q

q a q w

q a

w q a q

a q a q w

a t

s w

 









2 人零和ゲームと線形計画法

2 人非協力零和ゲーム

Theorem6

（Ｐ），（Ｄ）の最適解が（p*, u*），（q*,

w）のとき，（p, q）がゲームの*

均衡点であり，v:= u*= w*がゲームの値である

プレイヤーAの最適化問題

（LPの主問題：P）プレイヤーBの最適化問題

（LPの双対問題：D）

主・双対

0 , ,

1 . . . max

1 1 1 1

2 1

12

1 1

11

 



  







  



m m

m mn n

m m

p

p p

p a p u

p a

u p a p

a p a p u

a t

s u







0 , ,

1 . . . min

1 1 1 1

2 1 21

1 1 11

 



  







  



n n

n mn m

n n

q

q q

q a q w

q a

w q a q

a q a q w

a t

s w







注）（P）（D）ともに自明解（p=(1,0,…,0), q=(1,0,…,0)）があるので実行可能．

→双対定理より，最適解が存在し，最適値は一致する



2 人零和ゲームと線形計画法

• Example6 ：じゃんけん

2 人非協力零和ゲーム

A ＼ B

0 2 -7

-2 0 4

7 -4 0

min max -7 -2 -2 -4

max 7 2 4

min 2

j ij

i

a

v max min 2 

₁





i ij

j

a

v min max 2 

₂



マキシミン戦略

ミニマックス戦略

 両プレイヤーとも，支配戦略は存在しない．

 純粋戦略ではミニマックス均衡点は存在しない．

(14)



2 人零和ゲームと線形計画法

• Example6 ：じゃんけん

2 人非協力零和ゲーム ^A＼B

0 2 -7

-2 0 4

7 -4 0

0 , ,

1 7 4 2 4 . . . 2 7 max

3 2 1

2 1

3 1

3 2

 



 



      p p

p p p

p p u

p p p u

t

s u

0 , ,

1 7 4 2 4 . . . 2 7 min

3 2 1

2 1

3 1

3 2

 



 

  

  

q q

q q q

q q q q w w

q q q w

t

s w

自己双対線形計画問題 self-dual LP

( p

₁

* , p

₂

* , p

₃

* )=(0.538462, 0.153846, 0.307692), u=* 0 (q

₁

*, q

₂

*, q

₃

)=(0.538462, 0.153846, 0.307692), w=0

p

₁

p

₂

p

₃

q

₁

q

₂

q

₃

演習４：



LP による均衡解の求解

• ２人のプレイヤー A, B は，プレイヤー A の利得行列（ B の損失行列 ) が以下で与えられるゲームをする．各プレイヤーの問題を LP で表し，均衡解とゲームの値を求めよ．

A ＼ B s _B1 s _B2 s _B3

s _A1 1 5 -2

s _A2 4 1 3

s _A3 -2 3 6

参考文献



S.J. Brams & A.D. Taylor, ``Fair Division’’, Cambridge Univ. Press (1996)



鈴木光男「ゲーム理論入門」共立出版（ 1981,2003

^{（新装版）}

）



鈴木光男「新ゲーム理論」勁草書房（ 1994 ）



岡田章「ゲーム理論」有斐閣（ 1996 ）



渡辺隆裕「ゲーム理論入門」日本経済新聞社（ 2008 ）

 今野浩「線形計画法」日科技連（1987）

 中山幹夫・武藤滋夫・舟木由喜彦「ゲーム理論で解く」有斐閣（2000）

 武藤滋夫「ゲーム理論入門」日本経済新聞社（2001）

 逢沢明「ゲーム理論トレーニング」かんき出版（2003）

 今井春雄・岡田章編著「ゲーム理論の応用」勁草書房（2005）



R.アクセルロッド「つきあい方の科学」ミネルヴァ書房（1998）

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