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

(1)

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

情報学部堀田敬介

2010/11/9,Sat. ^～

case2 ： Carol, Ted は誰も妬まないが， Bob は Carol か Ted のいずれかを妬む可能性がある．（ Carol と Ted の [divide-and-choose] の結果が Bob から見て 50-50 に思えない場合， 2 人のいずれかが 1/3 以上（と Bob が思う） cake を得るので）

ケーキを仲良く（ｎ人いたら？）

Kuhn が The Steinhaus’ loan-divider procedure ⁽³

playes) を n 人版に拡張

（ Frobenius & Konig の combinatorial theorem に基づくアルゴリズム）

（ 4 人版は Steinhaus も気づいていたらしい）

The Banach-Knaster last-diminisher procedure

（ Steinhaus が 1948 年に 2 人（彼の学生，ポーランド人）のアイデアを論文の形で発表）

……

H.W. Kuhn, 1967

S. Banach-B. Knaster, mid-1940

‥

(5)

ケーキを仲良く

The Banach-Knaster last-diminisher procedure (n players)

• 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 を妬む．

(6)

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

N={1, 2, …, n}

S_i={s_i1, s_i2, …, s_im} (i∈N)

f_i: S₁×S₂…×S_n→ R (i∈N) プレイヤーの集合

プレイヤーi の戦略集合

プレイヤーi の利得関数

) } { , } { ,

( N S

_i _i _N

f

_i _i _N

G =

_∈ _∈

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

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

ゲームの定義

(7)

ゲームの表現形式

• 展開形 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

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

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

ゲーム理論とは何か？

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

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

拘束的合意が成立しない

拘束的合意が成立

非協力ゲーム

協力ゲーム

(8)

Example1 ：

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

をしている

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

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

異なるならBさんの勝ち

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

2 A ＼ B 表裏

表 2 -1 裏 -2 1

A 君の利得表

N={1, 2}

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

f_i:S₁×S₂→ R, (i∈N) f₁(表, 表) = 2

f₁(表, 裏) = -1 f₁(裏, 表) = -2 f₁(裏, 裏) = 1

f₂(表, 表) = -2 f₂(表, 裏) = 1 f₂(裏, 表) = 2 f₂(裏, 裏) = -1 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

(9)

ミニマックス原理 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 以下になる．

(10)

ミニマックス原理

• Example2 ：

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

均衡点とゲームの値

• 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

s_A1 -2 4 -1

s_A2 2 2 1

s_A3 4 -3 0

(11)

演習１：

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

(12)

純粋戦略と混合戦略

• Example3 ：

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 =

₂

=

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

マキシミン戦略

ミニマックス戦略

純粋戦略と混合戦略

• Proposition1

利得行列A=[a

_ij

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

2 人非協力零和ゲーム

i ij ij j

i

min

j

a min max a

max ≤

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

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

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

(13)

純粋戦略と混合戦略

• 鞍点 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

⎥ ⎥

⎥

⎦

⎤

⎢ ⎢

⎢

⎣

⎡

=

L M M

L L

M L

M M

L M

L

0

0 0

0

1 1

11

]

[

0 0

0 i j

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 の最適戦略

(14)

純粋戦略と混合戦略

• Theorem2

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

₀

, j

₀

) が均衡点ならば， (i*, j

₀

), (i

₀

, j*) も均衡点である．

均衡戦略は交換可能

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

完全予見は不可能！

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

主体的な賭，

最適な賭の確率

期待効用原理

(15)

純粋戦略と混合戦略

• 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

⎪⎩

⎪ ⎨

⎧

+

= + −

= − + +

=

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

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

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 ) , (

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

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

) , ( )

, ( )

, ( ) , (

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

p

p p

p q

p

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

) ( ) ( : )

( p, q E

₁

p, q E

₂

p, q

E = =

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

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

純粋戦略 pure strategy 混合戦略

mixed strategy

(16)

支配戦略

• Example3 ：

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 被支配戦略

支配戦略

任意のに対して，

が成立すること．

i

S

s

₋

∈

₋

) , ( ) ,

( s h f s k

f

_i ₋_i

>

_i ₋_i

被支配戦略除去の原理

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

•＝だと「同等」

•≧かつ≠ だと「弱支配」

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

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

→ ゲームは支配可解dominance solvable

最適混合戦略

• 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 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

q p p q p p

q s E q s E

E

_B _B

⎩⎨

⎧ = = − − +

2 ))

1 , 0 (

( ( 1 , 0 )) 6 3 (

2

p

2

E

p E

p, p,

⎩⎨ ⎧

+

−

= +

= 5 2

) ) 1 , 0

(( 1 , 0 ) ) 2 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)** ：均衡解

(17)

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

^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

q p

p

q p p

E

−

− +

+ − −

= p, q

player B player A

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

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 playerA 0.75

player A

player B

5/7

1/7

最適混合戦略

• Example3 ：

(18)

混合戦略の意味

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

s_A3 -3 2

p₃

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

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

（３）（４）

(19)

ミニマックス定理

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

• プレイヤー A の利得行列（ B の損失行列）

2 人非協力零和ゲーム

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

] A [

} , , 1

| { }, , , 1

|

{ s i m S s j n

S

A

=

Ai

= L

B

=

Bj

= L

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

, , ( p

₁

L p

_m

= p

⎩⎨ ⎧

≥ = + + , 0 ,

, 1

1 1

m

p

m

p

p p L L

⎩⎨

⎧ + + ≥ = 0 ,

, 1

1 1

n

q

n

q

q 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

(20)

ミニマックス定理

• Theorem3

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

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

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

ミニマックス定理

• Theorem5

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

が成立すること．

2 人非協力零和ゲーム

)

*, (

*)

*, (

*) , ( ,

, j E s

Ai

E E s

Bj

i q ≤ p q ≤ p

∀

*)

*, (

, , ,

1

ⁿ

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

(21)

ミニマックス定理

• 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

1 2

1

1 2

1

1 2

1

3 ) , (

1 4 3

) , (

4 2 4

2 ) , (

2 3 2

) ,

( , ) 2 5 7 5

(

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

p₁ E₁

1 0

p₂

0 1

4/7

) 0 7 , , 3 7 ( 4

* = p

ミニマックス定理

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

2 人非協力零和ゲーム

A ＼ B s

_B1

s

_B2

s

_A1

^a

11

a

₁₂

s

_A2

^a

21

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

p

(22)

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

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

u p a p

a

u p a p

a

u p a p

a t s

u

L L K L L L

a a

a

a a

a

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 mn n

n B

m m B

p a p

a p a s E

p a p

a p a s E

p a p

a p a s E

n

L

M L L

2 2 1 1

2 2

22 1 12

1 2

21 1 11

) , (

2 1

p p p

まとめると…

{ ⁽ ^, ^), ⁽ ^, ^), ^, ⁽ ^, ⁾ }

min

max E p s

B1

E p s

B2

E p s

Bn

p

L

(23)

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

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

2 人非協力零和ゲーム

a a

a

a a

a

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

⎪ ⎩

⎪ ⎨

⎧

+ + +

=

+ + +

= + + +

=

n mn m

m A

n n A

q a q

a q a s

E

q a q

a q a s

E

q a q

a q a s

E

m

L

M L L

2 2 1 1

2 2

22 1 21

1 2

12 1 11

) , (

) , ( , ) (

2 1

q q q

まとめると…

{

⁽ ^, ^), ⁽ ^, ^), ^, ⁽ ^, ⁾

}

max

min 1 q 2 q q

q E sA E sA L E sA^m

0 , ,

1 . . . min

1 1 1 1

2 1

21

1 1

11

≥ = +

+ + ≤

+

≤ +

+ + ≤

+

n n

n mn m

n n

q q

w q a q

a

w q a q

a

w q a q

a t s

w

L L L K L L

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

u p a p

a

u p a p

a

u p a p

a t s

u

L L K L L L

0 , ,

1 . . . min

1 1 1 1

2 1

21

1 1

11

≥ = +

+ + ≤

+

≤ +

+ + ≤

+

n n

n mn m

n n

q q

w q a q

a

w q a q

a

w q a q

a t s

w

L L L K L L

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

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

(24)

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

• Example6 ：じゃんけん 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 =

₂

=

マキシミン戦略

ミニマックス戦略

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

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

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

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 7 4 2 4 . . . 2 7 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

₁

*, 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

₃

(25)

演習４：

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 ）

今井春雄・岡田章

編著

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