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

(1)

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

情報学部堀田敬介

2006/10/28,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

(5)

ケーキを仲良く

The last-dimisher procedure

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

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

• envy-free ではない

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

ゲーム理論とは何か？

ゲーム的状況 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．

協力の可能性

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

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

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

(6)

ゲームの表現形式

• 展開形 extensive form

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

ゲーム理論とは何か？

6 -4 S

_A2

1 3 S

_A1

S

_B2

S

_B1

A ＼ B

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

L L L

1 2 1

:

} , , , {

} , , 2 , 1

{ ^{：プレイヤーの集合}

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

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

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

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

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

ゲーム理論とは何か？

) ( } , , ,

{ s

₁

s

₂

s i N

S

_i

=

_i _i

L

_im

∈

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

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

拘束的合意が成立しない

拘束的合意が成立

非協力ゲーム

協力ゲーム

(7)

ゲームのルール

• プレイヤーの数は 2 人

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

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

• ゲームは 1 回限り

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

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

2 人非協力零和ゲーム

0 ) , ( ) , (

, ) , (

2 1 2 2 1 1

2 1 2

1

∈ + × =

∀

s s f s s f

S S s s } 2 , 1

= { N

⎩⎨

⎧ = =

} , , , {

2 22 21 2

1 12 11 1

n

s

m

s s S

s s s S

L L

利得行列 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

⎥ ⎥

⎦

⎤

⎢ ⎢

⎣

⎡

=

L M O M M

L L

2 1

2 22

21

1 12

11

] [

利得行列

Example1 ：

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

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

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

2 人非協力零和ゲーム

-3 5

ハートの7

-6 2

スペードの4

ダイヤの10 クラブの2

A ＼ B

3 -5

ハートの7

6 -2

スペードの4

ダイヤの10 クラブの2

A ＼ B

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

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

(8)

Example2 ：

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

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

2 人非協力零和ゲーム

-3 2 4 s

_B2

1 2

s

_A2

0 4

s

_A3

-1 -2

s

_A1

s

_B3

s

_B1

A ＼ B

ミニマックス原理 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 人非協力零和ゲーム

-3 2 4 s_B2

1 2

s_A2

0 4

s_A3

-1 -2

s_A1

s_B3 s_B1

A＼B

最大化プレイヤー

戦略 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 人非協力零和ゲーム

-3 2 4 s_B2

1 2

s_A2

0 4

s_A3

-1 -2

s_A1

s_B3 s_B1

A＼B

戦略 s

_B3

を取る（最悪でも損失 1 で済む）

Aは戦略 s _A2

を取るとき，利得1を得られ，

(9)

ミニマックス原理

• Example2 ：

2 人非協力零和ゲーム

1 4 4 max

-3 0 -3 4 s

_A3

1 -2 min 1 -1 s

_B3

1 max 2

4 s

_B2

2 s

_A2

1 min

-2 s

_A1

s

_B1

A ＼ B

保証水準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

均衡点とゲームの値

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

2 人非協力零和ゲーム

1 min max max

min =

_ij

=

i j i ij

j

a a

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

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

しかたない…

やむをえない…

2 人零和ゲームが

「厳密に決定される strictly determined 」

「厳密に確定的である」

（ s

_A2

*, s

_B3

^{*）：ゲームの均衡点} equilibrium point

-3 2 4 s_B2

1 2

s_A2

0 4

s_A3

-1 -2

s_A1

s_B3 s_B1

A＼B

演習１：

プレイヤー A の利得表が以下の表で与えられるゲームを考える．

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

2 0 1 s

_B2

2 -1

s

_A2

3 5

s

_A3

-1 3

s

_A1

s

_B3

s

_B1

A ＼ B

（１）

2 8 6 s

_B2

2 1

s

_A2

3 7

s

_A3

4 5

s

_A1

s

_B3

s

_B1

A＼B

（２）

(10)

純粋戦略と混合戦略

• Example3 ：

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

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

2 人非協力零和ゲーム

-3 3 2 s

_B2

1 4

s

_A2

2 1

s

_A3

0 -4

s

_A1

s

_B3

s

_B1

A ＼ B

純粋戦略と混合戦略

• Example3 ：

2 人非協力零和ゲーム

-3 2 -3 1 s

_A3

2 3 4 max

1 0 s

_B3

1 -4 min 3

2 s

_B2

4 s

_A2

2 min

1 -4

s

_A1

max s

_B1

A ＼ B

j ij

i

a

v max min 1 =

₁

=

i ij

j

a

v min max

2 =

₂

= ≠

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

マキシミン戦略

ミニマックス戦略

純粋戦略と混合戦略

• Proposition1 ：利得行列 A=[a

_ij

] が与えられた時，

2 人非協力零和ゲーム

i ij ij j

j

i

min a min max a

max ≤

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

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

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

(11)

純粋戦略と混合戦略

• 鞍点 saddle point

• 行列A=[a

_ij

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

が成り立つとき，（i

₀

, j

₀

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

_i0j0

を鞍点値という．

2 人非協力零和ゲーム

j i j i

ij

a a

a

0

≤

00

≤

0

a a

a

a A

mn mj

n i j i

m i

n j

ij

⎥ ⎥

⎥

⎦

⎤

⎢ ⎢

⎢

⎣

⎡

=

L M M

L L

M L

M M

L M

L

0 0 0 0 0

0

1 1

11

]

[

0 0

0 ij

ij

a

a ≤

j i j

i

a

₀₀

≤

₀

純粋戦略と混合戦略

• 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

*

(12)

純粋戦略と混合戦略

• Example3 ：

2 人非協力零和ゲーム

-3 3 2 s

_B2

1 4

s

_A2

2 1

s

_A3

0 -4

s

_A1

s

_B3

s

_B1

A ＼ B

完全予見は不可能！

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

主体的な賭，

最適な賭の確率

期待効用原理

純粋戦略と混合戦略

• Example3 ：

2 人非協力零和ゲーム

-3 3 2 s

_B2

1 4

s

_A2

2 1

s

_A3

0 -4

s

_A1

s

_B3

s

_B1

A ＼ B

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

⎪⎩

⎪ ⎨

⎧

+

= = − + + − +

=

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,

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

よって，Bが各戦略を(q₁,q₂,q₃)の確率でとったときの，Aの期待効用

3 1 2 1 1 1

1

( ) ( ) ( ) ( )

3 2

1

q E s q E s q

s E

E p, q = p,

_B

+ p,

_B

+ p,

_B

純粋戦略と混合戦略

• Example3 ：

2 人非協力零和ゲーム

-3 3 2 s_B2

1 4

s_A2

2 1

s_A3

0 -4

s_A1

s_B3 s_B1

A＼B p₁ p₂ p₃

q₁ q₂ q₃

⎪⎩

⎪ ⎨

⎧

+

−

= = − + + +

=

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の期待効用

Aが各戦略を(p₁,p₂,p₃)の確率でとったときの，Bの期待効用

3 2 2 2 1 2

2

( ) ( ) ( ) ( )

3 2

1

p E s p E s p

s E

E p, q =

_A

, q +

_A

, q +

_A

, 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

p

p p

p q p

また，このとき明らかに，以下が成り立つ．

=

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

純粋戦略 pure strategy 混合戦略 mixed strategy

(13)

支配戦略

• Example3 ：

2 人非協力零和ゲーム

-3 3 2 s

_B2

1 4

s

_A2

2 1

s

_A3

0 -4

s

_A1

s

_B3

s

_B1

A ＼ B

> > >

-3 3 s

_B2

1 4

s

_A2

2 1

s

_A3

s

_B3

s

_B1

A ＼ B

>

> -3

3 s

_B2

1 s

_A2

2 s

_A3

s

_B3

A ＼ B

支配する dominate 被支配戦略

支配戦略

プレイヤーi の戦略h, k について，

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

任意のに対して，

が成立すること．

i

S

s

₋

∈

₋

) , ( ) ,

( s h f s k

f

_i ₋_i

>

_i ₋_i

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

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

•＝だと「同等同等」

•≧かつ≠

だと「弱支配弱支配」

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

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

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

最適混合戦略

• Example3 ：

2 人非協力零和ゲーム

-3 3 s_B2

1 s_A2

2 s_A3

s_B3 A＼B p₂ p₃

q₂ q₃

( ) ⎥

⎦

⎢ ⎤

⎣

⎡ ⎟⎟ ⎠ = −

⎜⎜ ⎞

⎝

⎛

⎟⎟ −

⎠

⎜⎜ ⎞

⎝

⎛

− −

=

−

− + +

−

= − + +

= +

=

) 1 (

2 3

1 1 3

) 1 ))(

1 ( 2 ( )) 1 ( 3 3 (

) 2 ( ) 3 3 (

) ( ) ( ) (

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

⎩⎨

⎧ = = − − +

2 )) 1 , 0 ( (

3 6 )) 0 , 1 ( (

2

p

2

E

p E

p, p,

⎩⎨

⎧ = = − + +

2 5 ) ) 1 , 0 ((

1 2 ) ) 0 , 1 ((

2 2

q E

q ,

q

,

^p²

E₁

1

0 5/7 q₂

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 人非協力零和ゲーム

-3 3 s_B2

1 s_A2

2 s_A3

q₂ q₃

) 1 ))(

1 ( 2 (

)) 1 ( 3 3 (

) (

2 2 2

q p p

q p p E

−

− +

+ − −

= p, q

player B player B player A

player A

(14)

0 0.25 0.5 0.75 1 player A

0.250.50 0.751 player B

-2 0 2

Exp

0 0.250.50.751 player A

0 0.25 0.5 0.75 1

player B

-2 0 2

Exp

2 人非協力零和ゲーム

-3 3 s_B2

1 s_A2

2 s_A3

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 player A

player B player B

5/7 5/7

1/71/7

最適混合戦略

• Example3 ：

混合戦略の意味

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

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

2 人非協力零和ゲーム

-3 3 s_B2

1 s_A2

2 s_A3

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

しまった！

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

しかし，これは事後的

演習２：

プレイヤー A の利得表が以下の表で与えられるゲームを考える．

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

3 -2 s

_B2

-3 s

_A2

4 s

_A1

s

_B1

A ＼ B

（１）

1 2 3 s

_B3

3 4 1 s

_B2

3 4

s

_A2

2 2

s

4 3

s

_A1

s

_B4

s

_B1

A ＼ B

（２）

5 1 s

_B2

-1 s

_A2

3 s

_A1

s

_B1

A ＼ B

1 3 2 s

_B2

0 -1

s

_A2

-2 2

s

4 3

s

_A1

s

_B3

s

_B1

A ＼ B

（３）（４）

(15)

ミニマックス定理

• プレイヤー A, B の純粋戦略

• プレイヤー A の利得行列

2 人非協力零和ゲーム

a a a

a a a a

mn m m

n n

ij

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

L M O M M

L L

2 1

2 22 21

1 12 11

] [ A

} , , 1

| { }, , , 1

|

{ s i m S s j n

S

A

=

Ai

= L

B

=

Bj

= L

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

, , ( p

₁

L p

_m

= p

⎩⎨

⎧ +≥ += = 1

) , , 1 ( , 0

1 m

i p

p

m i p

L L

⎩⎨

⎧ +≥ + == 1

) , , 1 ( , 0

1 n

j

q q

n j q

L

, , )

L

( q

₁

L q

_n

= q

利得関数利得関数

∑∑

= =

=

^m

i n

j j i ij

p q a E

1 1

) ,

( p q p

^T

Aq

) 0 , , 1 , , 0

( L L

i

= s

A

) 0 , , 1 , , 0

( L L

j

= s

B

ミニマックス定理

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

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

(16)

ミニマックス定理

• Theorem5

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

が成立すること．

2 人非協力零和ゲーム

)

*, (

*)

*, (

*) , ( ,

, j E s

Ai

E E s

Bj

i q ≤ p q ≤ p

∀

*)

*, (

, , , 1

n

1 j

*

E p q

q a m

i =

_ij _j

≤

∀ ∑

L

=

∑

=

≤

=

∀

^m

1 i

*)

*

*, ( , , ,

1 n E a

_ij

p

_i

j L p q

ミニマックス定理

• Example4

2 人非協力零和ゲーム

0 -1 4 2 5 s

_A2

-2 3 s

_B4

3 2 s

_B3

1 -1 s

_B2

3 -2

s

_A1

-1 4

s

_A3

s

_B5

s

_B1

A ＼ B

< < < < < <

<

≦

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

B B B B B

= − = −

= + = − +

= − + = − +

=

p p p p p

p₁ E₁

1 0

p₂

0 1

4/7 4/7

) 0 7 , , 3 7 ( 4

* = p

ミニマックス定理

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

2 人非協力零和ゲーム

a

₂₂

a

₂₁

s

_A2

a

₁₂

s

_B2

a

₁₁

s

_A1

s

_B1

A ＼ B 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

p a p a s E

A A B B

q q p p

(17)

演習３：

プレイヤー A の利得表が以下の表で与えられるゲームを考える．

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

3 -2 s

_B2

-3 s

_A2

4 s

_A1

s

_B1

A ＼ B

（１）（２）

5 1 s

_B2

-1 s

_A2

3 s

_A1

s

_B1

A ＼ B

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

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

2 人非協力零和ゲーム

) , , 1 ( 0

1 ) , , 1 (

. .

. max

m

1 i

m

1 i

m i p p

n j u p a t s

u

i i i ij

L L

=

≥

=

≥

∑

=

a a a

p p p

mn m m

n n

m

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

L M O M M

L L

M

2 1

2 22 21

1 12 11 2 1

⎪⎪

⎩

⎪⎪

⎨

⎧

=

∑

∑ ∑

=

m

i in i

B m

i i i

B m

i i i

B

p a s E

n 1

1 2 1 1

) , (

2 1

p p p M

≥u

まとめると…

u . max

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

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

2 人非協力零和ゲーム

a a a

q q q

mn m m

n n n m

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

L M O M M

L LL

2 1

2 22 21

1 12 11 1

⎪⎪

⎩

⎪⎪

⎨

⎧

=

∑

∑ ∑

=

m

j mj j

A n

j j j

A n

j j j

A

q a s

E

q a s

E

q a s

E

m 1

1 2 1 1

) , (

2 1

q q q

M

≤w

まとめると…

w . min

) , , 1 ( 0

1 ) , , 1 (

. .

. min

n

1 j

n

1 j

n j q q

m i w q a t s

w

j j j ij

L L

=

≥

=

≤

∑

=

(18)

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

2 人非協力零和ゲーム

) , , 1 ( 0

1 ) , , 1 (

. .

. min

n

1 j

n

1 j

n j q q

m i w q a t s

w

j j j ij

L L

=

≥

=

≤

∑

=

) , , 1 ( 0

1 ) , , 1 (

. .

. max

m

1 i

m

1 i

m i p p

n j u p a t s

u

i i i ij

L L

=

≥

=

≥

∑

=

• Theorem6

（Ｐ），（Ｄ）の最適解が（p, u），（q, w）のとき，（p, q）

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

プレイヤーAの問題（Ｐ）主・双対プレイヤーBの問題（D）

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

• Example6 ：じゃんけん

2 人非協力零和ゲーム

0 -4 7

4 -7 0 2 -2

0 A ＼ B

-4 -2 -2 -7

max min

2 min

4 2 7

max

ij

j

i

a

v max min 2 =

₁

=

−

i ij

j

a

v min max 2 = ≠

₂

=

マキシミン戦略

ミニマックス戦略

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

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

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

• Example6 ：じゃんけん

2 人非協力零和ゲーム

0 -4 7

4 -7 0 2 -2 0 A＼B

0 , ,

1 4 7

4 2

7 2 . .

. max

3 2 1

2 1

3 1

3 2

≥ = +

+ ≥

+

− − − + ≥ ≥ p p p

p p p

u p

p

u p p

u p p t

s u

0 , ,

1 4 7

4 2

7 2 . .

. min

3 2 1

2 1

3 1

3 2

≥ = +

+ ≤

− + ≤

− − ≤

q q q

w q

q

w q q

w q q t

s w

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

(p

1

*, p

2

*, p

3

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

1

*, q

2

*, q

3

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

p

₁

p

₂

p

₃

q

₁

q

₂

q

₃

(19)

演習４：

硬貨合せゲーム

プレイヤーA, Bが各々100円硬貨を投げて表・裏の出た組合せによって勝ち負けを決めるゲームを考える．両方とも表，あるいは両方とも裏がでたらA の勝ちとし，BはAに100円を支払う．逆に2枚の硬貨の出た面が違う場合はB の勝ちとし，AはBに100円を支払う．このゲームの値はどうなるか？期待効用原理の観点で考察せよ．

市場シェアゲーム

2大自動車メーカーA社とB社は，各々RV車を販売している．市場でシェア

争いにしのぎを削っていた．現状では，いずれも200万で販売しているが，今後の戦略として，それぞれ価格を「据え置く」か「10%引き」とするかがある．

• 両社とも「据え置く」場合の純利益が，Aが600億円で, Bが400億円，

• Aが据え置き，Bが10%引きだと，Aが300億円で，Bが700億円，

• Aが10%引き，Bが据え置くだと，Aが450億円で，Bが550億円，

• 両社とも10%引きで販売すると，Aが700億円で，Bが300億円が見込まれる．それぞれの最適戦略はどうなるか？

参考文献

S.J. Brams

^&

A.D. Taylor, ``Fair Division’’, Cambridge Univ. Press (1996)

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

^{（新装版）}

）

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

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

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

中山幹夫

・武藤滋夫・舟木由喜彦

「ゲーム理論で解く」

有斐閣（2000）

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

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

今井春雄・岡田章

編著

「ゲーム理論の応用」勁草書房（ 2005 ）

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

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