ゲーム理論とは何か？

(1)

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

情報学部堀田敬介

2007/11/9,Fri.^～

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

(3)

ゲーム理論とは何か？

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

ゲーム理論とは何か？

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.

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

拘束的合意が成立しない

拘束的合意が成立

非協力ゲーム

協力ゲーム

ゲームのルール

•

プレイヤーの数は

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 m

s s s S

LL

(4)

利得行列

payoff matrix

•

零和ゲーム，即ち，

なので，

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

A

で表せる

2 人非協力零和ゲーム

0 ) , ( ) , ( , ) ,

(₁ ₂ ∈ ₁× ₂ ₁ ₁ ₂ + ₂ ₁ ₂ =

∀s s S S f s s f s s )

, ( ) ,

( 2

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）ゲームの値

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^を取る）

min(2, 2, 1) = 1 （プレイヤーBが戦略s_B3^を取る）

min(4, -3, 0) = -3（プレイヤーBが戦略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を得られ，

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

ミニマックス原理

• 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₁=maxmin

i ij

j a

v₂=minmax

マキシミン原理 maximin principle

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

ミニマックス原理 minimax principle

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

(5)

均衡点とゲームの値

• 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

-3 2 4

1 2

s_A2

0 4

s_A3

-1 -2

s_A1

演習１：

プレイヤー

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

（２）

純粋戦略と混合戦略

• 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 maxmin 1= ₁=

i ij

j a

v minmax

2= ₂= ≠

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

マキシミン戦略

ミニマックス戦略

純粋戦略と混合戦略

• Proposition1

：利得行列

A=[a_ij]

が与えられた時，

2 人非協力零和ゲーム

i ij ij j

j

i mina minmaxa

max ≤

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

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

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

純粋戦略と混合戦略

•

鞍点

saddle point

•

行列A=[a

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

が成り立つとき，（

i0, j0

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

a_i0j0

を鞍点値という．

2 人非協力零和ゲーム

j i j i

ij a a

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

a00≤ 0

(6)

純粋戦略と混合戦略

• 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

*

純粋戦略と混合戦略

• 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

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

) ( ) ( : )

(p,q E₁ p,q E₂ p,q

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

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

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

支配戦略

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

支配戦略

戦略の支配

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

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

任意のに対して，

が成立すること．

i

i S

s₋∈ ₋ ) , ( ) ,

(s h f s k

f_i ₋_i > _i ₋_i

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

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

•＝だと「同等同等」

•≧かつ≠

だと「弱支配弱支配」

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

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

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

(7)

最適混合戦略

• Example3

：

2 人非協力零和ゲーム

-3 3 s_B2

1 s_A2

2 s_A3

s_B3 A＼B p₂ p₃

( ) _⎥

⎦

⎢ ⎤

⎣

⎡ ⎟⎟⎠=−

⎜⎜ ⎞

⎝

⎛

⎟⎟ −

⎠

⎜⎜ ⎞

⎝

⎛

− −

=

−

− + +

−

= − + +

= +

=

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

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

) 1 ))(

1 ( 2 (

)) 1 ( 3 3 (

) (

2 2 2

2 2

2 p q

p

q p p 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.250.50.7501 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

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

player B player B

5/75/7 1/7 1/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

*

2q +pq =

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_A3

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_A3

4 3

s_A1

s_B3 s_B1

A

＼

B

（３）（４）

ミニマックス定理

•

プレイヤー

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

SA= 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₁Lq_n

= q

利得関数

∑∑

= =

=

= ^m

i n

j j i ijpq a E

1 1

) ,

(pq p^TAq

) 0 , , 1 , , 0

( L L

i= sA

) 0 , , 1 , , 0

( L L

j = sB

ゲーム理論とは何か？

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

情報学部 堀田敬介

Contents

ケーキを仲良く！

ゲーム理論とは何か？

2 人非協力零和ゲーム

ケーキを仲良く

と

にケーキ （丸々

個！） を買ってきた．

人に均等に与えたいのだが，

人は自分の分が 相手より小さいと不満を言い，けんかになる．

どうしたら いいだろう

仮定：

ケーキを仲良く

You Cut, I Choose !

にケーキを切らせ，

にケーキを選ばせる

解は …

ケーキを仲良く

解の持つ 2 つの性質

ケーキを仲良く

人の戦略

：「均等に切る」「不均等に切る」

：「大きいほうを選ぶ｣「小さいほうを選ぶ｣

人の利得表

の利得表

人 非協力 非協力 零和ゲーム 零和

不均等に切る

均等に切る

小

とる 大

とる

＼

ケーキを仲良く

ミニマックス原理

の利得表（

の損失表）

1/2以上 1/2以下 Min Max

不均等 小 大 小

均等 1/2 1/2 1/2 Max 1/2 大

Min

1/2

1/2

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

The Steinhaus’ lone-divider procedure

がケーキを

（と

が思う通り）に切る

が

とそうでないものを指摘

も

と同様のことを行う．

が

個以上

がある

とも

が高々

個

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

The Steinhaus’ loan-divider procedure

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

ではない

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

Kuhn が The Steinhaus’ loan-divider procedure

を n 人版に拡張

（

の

に基づくアル ゴリズム）

（

人版は

も気づいていたらしい）

The Banach-Knaster last-diminisher procedure

（

が

年に

人

のアイデ アを論文の形で発表）

……

情報学部堀田敬介

にケーキ（丸々

個！）を買ってきた．

人は自分の分が相手より小さいと不満を言い，けんかになる．

どうしたらいいだろう

人非協力非協力零和ゲーム零和

とる大

不均等小大小

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

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

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

に基づくアルゴリズム）

のアイデアを論文の形で発表）

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

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

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

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

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

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

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