調和系工学 ゲーム理論編

知的都市基盤工学

5月30日(水)５限(16:30～18:10）

ゲーム理論 第三部

再掲：囚人のジレンマ

囚人のジレンマの利得行列

⎥

⎦

⎤

⎢

⎣

⎡

2

,

2

1

,

4

4

,

1

3

,

3

協調（

_C

ooperate）:

C

右がプレイヤー1の利得 左がプレイヤー2の利得

裏切（

_D

efect）:

D

プレイヤー1

C

D

プレイヤー2

ナッシュ均衡点

（協調＝黙秘、裏切＝自白）

プレイヤーの合理的な意思決定の結果

(C,C) はナッシュ均衡ではない

再掲：無限繰り返し囚人のジレンマ 12

all-C

all-D

all-C

all-D

プレイヤー1

プレイヤー2

しっぺ返し

しっぺ返し

3

,

3

δ

δ

+

− 1

2

,

4

δ

δ

,

4

2

1

+

−

3

,

3

3

,

3

3

,

3

2

,

2

1

,

4

4

,

1

δ

−

1

ただし、表中の値は全て 倍してある

である場合の最適反応戦略

δ

2

4

3

≥

−

(

δ

≥

1

/

2

)

２つの

ナッシュ

均衡

プレイヤー1のプレイヤー2に対する最適反応戦略 プレイヤー2のプレイヤー1に対する最適反応戦略

)

2

/

1

(

δ

=

の場合の最適反応戦略

フォークの定理

• 3つの戦略 all-C, all-D, しっぺ返し の中から1つを選択可能な場合

無限繰り返し囚人のジレンマ

δ

2

4

3

≥

−

(

δ

≥1/2)

δ

2

4

3

<

−

(

δ

<1/2) ナッシュ均衡 (all-D, all-D), ( しっぺ返し,しっぺ返し) (all-D, all-D)

{

1回限りのゲームのナッシュ均衡戦略に含まれない行動の組(C,C) の 系列が無限繰り返しゲームのナッシュ均衡に含まれるか？

フォークの定理

• 無限の戦略集合を仮定した場合 （一般的な場合に拡大）

1回限りのゲームのナッシュ均衡戦略に含まれない行動の組(C,C) の 系列が無限繰り返しゲームのナッシュ均衡に含まれる

ミニマックス行動 1

ミニマックス行動

戦略形ゲームG においてプレイヤー

i

に対する

ミニマックス行動

とは、

)

,

(

max

min

)

,

(

max

_{i i j} a a j i i a_i

f

a

m

≡

_{j i}

f

a

a

を満たすプレイヤー

_j

の行動

のことで、右辺の値をプレイヤー

_i

の

ミニマックス利得

という

j

m

定義 1

プレイヤー2のミニマックス行動 プレイヤー1が最適反応原理に基づいて選択した行動に対して プレイヤー1の利得を最小化するプレイヤー2の行動 プレイヤー1が最適反応原理に よって行動を選択した場合に 最低限獲得可能な利得 プレイヤー1のミニマックス利得 プレイヤー2がミニマックス行動を選択 した場合のプレイヤー1の利得 （ 保障水準 ）

ミニマックス行動 2

囚人のジレンマ

プレイヤー1のミニマックス利得とプレイヤー2のミニマックス行動

2

=

⎥

⎦

⎤

⎢

⎣

⎡

2

,

2

1

,

4

4

,

1

3

,

3

C

D

C

D

プレイヤー2 の ミニマックス行動 プレイヤー1 の ミニマックス利得 プレイヤー2 プレイヤー1 プレイヤー2がDを選択して プレイヤー1の利得を最小化

)]

2

,

1

max(

),

4

,

3

[max(

min

2 a

=

)

,

(

max

min

_{1 1 2} 1 2

a

a

f

a a

]

2

,

4

[

min

2 a

=

プレイヤー2がミニマックス行動D を選択 すれば、プレイヤー1はミニマックス利得 2以上の利得を獲得できない 同様に ミニマックス利得の組 （2, 2） ：D ：2 プレイヤー1 の ミニマックス行動 プレイヤー2 の ミニマックス利得 ：D ：2 プレイヤー2のC, Dに対する プレイヤー1の最適反応

個人合理的 1

プレイヤーの行動の組

が成立するとき、行動の組

)

,

(

a

₁

a

₂

=

a

プレイヤー1とプレイヤー2 のミニマックス利得

に対して

が成立するときをいう

1 1

(

)

v

f

a

≥

i

v

定義 2

)

,

(

a

₁

a

₂

個人合理的

=

a

が

個人合理的

であるとは、

は

強く個人合理的

であるという

2 2

(

)

v

f

a

≥

1 1

(

)

v

f

a

>

f

₂

(

a

)

>

v

₂

∧

∧

個人合理的 2

囚人のジレンマにおける個人合理的な行動の組

強く個人合理的な場合、 上の利得ベクトルは含まない 個人合理的な行動の組

(2,2)

(3,3)

(2,2)

(1,4)

(4,1)

(3,3)

プレイヤー1の利得

個人合理的利得

ベクトル集合

⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 2 , 2 1 , 4 4 , 1 3 , 3 C D C D プレイヤー2 プレイヤー1 ミニマックス利得 の組

_(2,2)

個人合理的な行動の組の 条件を満たす利得の組

(D,D)

(C,C)

強く個人合理的な行動の組

(2,2)

(3,3)

強く個人合理的な行動の組の 条件を満たす利得の組

(C,C)

ミニマックス利得の組

(2,2)

フォークの定理 1

成分ゲームGの強く個人合理的な任意の行動の組

i j i i b i j i i b

v

a

b

f

f

a

b

f

i i

−

−

≥

)

,

(

max

)

(

)

,

(

max

a

δ

∞

G

(

,

2*

)

* 1 *

s

s

=

s

に対して将来利得の割引因子δが

が成り立つ

存在して、

,...)

,

(

)

(

s

*

a

1

a

2

a

=

を満たせば、繰り返しゲーム

のナッシュ均衡点

2

,

1

,

i

=

定理

₁

)

,

(

a

₁

a

₂

フォークの定理

=

a

が

無限繰り返しゲームのナッシュ均衡の中の一つに

強く個人合理的な行動の組を毎回実現する均衡点が存在

フォークの定理 2

定理2 の証明 1

相手のプレイヤーだけが強く個人合理的な任意の行動の

上記の場合以外は強く個人合理的な任意の行動

をとる

* 2 * 1

, s

s

2 1

, m

m

2 1

, a

a

トリガー戦略

ミニマックス行動

に従う

規則 1

規則 2

)

,

(

a

₁

a

₂

=

a

の定義

組

から離脱すれば、以後相手に対する

• 一度相手がDを出せば、それ以降のゲームでは それ以降の相手の行動に関係なく、Dを出し続ける

繰り返し囚人のジレンマでのトリガー戦略

• 相手がDを出すまで、自分は常にCを出し続ける （初回はCを出す）

フォークの定理 2

定理2 の証明 1

が実現する

,...)

,

(

)

(

s

*

a

1

a

2

a

=

プレイヤー1、プレイヤー2がトリガー戦略を選択

Case 1

初回からお互いに強く個人合理的な行動を取り続け、

どちらもそこから離脱することがないので

お互いにトリガー戦略から変更しなかった場合のプレイヤー1 の

t 回目以降の割引利得和は、

)

(

1

1

1

a

f

δ

−

...

)

(

)

(

₁ 1

a

f

a

f

+

δ

+

=

である.

フォークの定理 3

定理2 の証明 2

プレイヤー1が戦略をトリガー戦略

から異なる戦略に変更

プレイヤー1は t 回目のゲームで と異なる行動 をとる. * 1

s

1

a

このとき、トリガー戦略の定義から、プレイヤー2 は t +1 回目以降のゲームで 1

b

プレイヤー1 に対するミニマックス行動をとり続ける.

Case 2

戦略を変更したプレイヤー1の t 回目以降の割引利得和は、

1 2 1 1 1 2 1 2 1 1

1

)

,

(

...

)

,

(

b

a

v

v

f

b

a

v

f

δ

δ

δ

δ

−

+

=

+

+

+

t 回目の利得 t+1 回目以降の_{割引利得和}

である.

フォークの定理 4

定理2 の証明 3

行動 に対して、 1 2 1 1 1

1

)

,

(

)

(

1

1

v

a

b

f

f

δ

δ

δ

≥

+

−

−

a

1

b

* 1

s

ならば、トリガー戦略 から他の戦略へ変更しても割引利得和を増やせない

)

(

1

1

:

f

₁

a

δ

−

Case 1 (変更しない) Case 2 (変更した)

:

f

1

(

b

1

,

a

2

)

₁

δ

v

1

δ

−

+

プレイヤー1の t 回目以降の割引利得和

トリガー戦略からの変更に関して…

プレイヤー1のトリガー戦略はプレイヤー2の

トリガー戦略に対する最適反応戦略

トリガー戦略がナッシュ均衡戦略

プレイヤー1とプレイヤー2の両方に対して成立

フォークの定理 5

定理2 の証明 4

i j i i i

f

b

a

v

f

δ

δ

δ

≥

+

−

−

(

)

(

,

)

1

1

1

a

i j i i b i j i i b

v

a

b

f

f

a

b

f

i i

−

−

≥

)

,

(

max

)

(

)

,

(

max

a

δ

)

(

)

,

(

max

)

)

,

(

max

(

_{i i j i}

a

b i j i i b_i

f

b

a

−

v

≥

_i

f

b

a

−

f

δ

i j i i b j i i b i

f

b

a

f

b

a

v

f

i i

δ

δ

+

−

≥

max

(

,

)

max

(

,

)

)

( a

i j i i b i f b a v f i

δ

δ

+ − ≥ (1 ) max ( , ) ) ( a i j i i b i

f

b

a

v

f

i

δ

δ

δ

≥

+

−

−

(

)

max

(

,

)

1

1

1

a

右辺を最大化する についても成り立つ

)

1

,

2

(

),

2

,

1

(

)

,

(

i

j

=

式変形 式変形 i

b

フォークの定理 6

ナッシュ均衡点の実現する行動の組の系列に

,....)

,...,

(

)

(

s

*

a

1

a

t

a

=

),...)

,

(

),...,

,

((

C

C

C

C

=

が含まれる

フォークの定理

強く個人合理的な行動の組

_(C,C)

i j i i b i j i i b v a b f f a b f i i − − ≥ ) , ( max ) ( ) , ( max a

δ

,

i

=

1

,

2

⎟ ⎠ ⎞ ⎜ ⎝ ⎛ = − − ≥ 2 1 2 4 3 4

δ

囚人のジレンマ

割引因子δの条件

＋

が成り立つ場合

(2,2)

(1,4)

(4,1)

(3,3)

プレイヤー1の利得

個人合理的利得

ベクトル集合

⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 2 , 2 1 , 4 4 , 1 3 , 3 C D C D プレイヤー2 プレイヤー1 ミニマックス利得 の組

_(2,2)

再掲：無限繰り返し囚人のジレンマ 13

δ

2

4

3

<

−

(

δ

<

1

/

2

)

の場合 しっぺ返しに対する しっぺ返しの割引利得和 しっぺ返しに対する all-Dの割引利得和

しっぺ返しを選択する

誘因がない

＞

(2,2)

(1,4)

(4,1)

(3,3)

プレイヤー1 の利得 プレイヤー2 の利得

)

1

,

2

4

(

−

δ

+

δ

)

2

4

,

1

(

+

δ

−

δ

δ

2

4

−

3

お互いしっぺ返しの 場合の割引利得和 プレイヤー1： all-D プレイヤー2： しっぺ返し の場合の割引利得和のとる範囲 プレイヤー1： しっぺ返し プレイヤー2： all-D の場合の割引利得和 のとる範囲 ナッシュ均衡

再掲：無限繰り返し囚人のジレンマ 14

δ

2

4

3

≥

−

(

δ

≥

1

/

2

)

の場合 しっぺ返しに対する しっぺ返しの割引利得和 しっぺ返しに対する all-Dの割引利得和

4

−

2

δ

3

(2,2)

(1,4)

(4,1)

(3,3)

プレイヤー1 の利得

)

2

4

,

1

(

+

δ

−

δ

お互いしっぺ返しの 場合の割引利得和 プレイヤー2 の利得

)

1

,

2

4

(

−

δ

+

δ

ナッシュ均衡 ナッシュ均衡 プレイヤー1： all-D プレイヤー2： しっぺ返し の場合の割引利得和のとる範囲 プレイヤー1： しっぺ返し プレイヤー2： all-D の場合の割引利得和 のとる範囲

しっぺ返しを選択する

誘因が発生

＞

フォークの定理 7

トリガー戦略以外でも強く個人合理的な行動の組（C,C ）の系列は

強く個人合理的な行動の組（C,C）からの離脱に 対してミニマックス行動Dを選択する戦略との対戦

ナッシュ均衡戦略により実現可能か？

割引因子δが十分に大きいと成立

ex.) しっぺ返し戦略 離脱により得られる利得 強い個人合理的な戦略の組から 離脱してミニマックス行動を選択 された場合の割引利得和

＋

強い個人合理的な戦略の組から 離脱しない場合の割引利得和

＞

強く個人合理的な戦略の組に留まる誘因発生の条件

強く個人合理的な行動の組（C,C）の系列が実現可能

有限繰り返しゲームのナッシュ均衡 1

割引因子δは導入しない

繰り返し回数が有限 = 未来に対する不確実がない

有限繰り返しゲーム

成分ゲームGが唯一のナッシュ均衡点

は、

)

,

(

e

₁

e

₂

e

=

T

G

s

*

=

(

s

₁*

,

s

₂*

)

もつとき、任意の 繰り返し回数

_T

に対して、

)

,...,

,

(

)

(

s

*

e

e

e

a

=

である

T回繰り返しゲーム

のナッシュ均衡点

定理 2

を

有限繰り返しゲームのナッシュ均衡 2

定理2 の証明 1

後ろ向き帰納法で証明

1回限りのゲームと同様であるので

繰り返しゲームのナッシュ均衡点は

成分ゲームのナッシュ均衡点と一致する

1

=

T

の場合

①

の場合、定理2は成立する

1

=

T

有限繰り返しゲームのナッシュ均衡 3

定理2 の証明 2

T回目のゲームでは既に行動が決定していて、 T-1回目のゲームはT回目のゲームに影響を与えない

2

≥

T

の場合

• T回目のゲーム （最後の一回のゲーム）

②

以降のゲームに影響を与えないので、 T-1回目までのゲームの 履歴にかかわらず1回限りのゲームと同様に扱うことができる

• T-1回目のゲーム

合理的な行動の結果は成分ゲームGのナッシュ均衡 合理的な行動の結果は成分ゲームGのナッシュ均衡 T-1回目までのゲームの履歴にかかわらずT-1回目の ゲームも1回限りのゲームと同様に扱うことができる

1回目のゲームも 1回限りのゲームと同様に扱うことができる

2

≥

T

の場合、

毎回のゲームにおけるナッシュ均衡点は

成分ゲームのナッシュ均衡点と一致する

• 1回目のゲーム

合理的な行動の結果は成分ゲームGのナッシュ均衡

2

≥

T

の場合

②

定理2 の証明 3

有限繰り返しゲームのナッシュ均衡 4

2回目のゲームでも既に行動が成分ゲームのナッシュ均衡戦略と 決定していて、 1回目のゲームは2回目のゲームに影響を与えない

したがって、

有限繰り返しゲームのナッシュ均衡 5

①

T

=

1

_,②

T

≥

2

_{において定理2が成立しているので}

が成立する

成分ゲームGが唯一のナッシュ均衡点

は、

)

,

(

e

₁

e

₂

e

=

T

G

s

*

=

(

s

₁*

,

s

*₂

)

もつとき、任意の 繰り返し回数

_T

に対して、

)

,...,

,

(

)

(

s

*

e

e

e

a

=

である

T回繰り返しゲーム

のナッシュ均衡点

定理 2

を

有限繰り返しゲームのナッシュ均衡 6

毎回成分ゲームの均衡点(D,D)が繰り返される

有限繰り返し囚人のジレンマ

定理2 の仮定…「成分ゲームのナッシュ均衡点が唯一」

)

,

(

D

D

定理2 の仮定を満たす

有限繰り返し囚人のジレンマのナッシュ均衡

))

,

(

),...,

,

((

)

,...,

(

)

(

s

*

=

a

1

a

t

=

D

D

D

D

a

一回限りの囚人のジレンマのナッシュ均衡点は

で唯一

繰り返し囚人のジレンマ コンテスト 1

前述の繰り返し囚人のジレンマの分析

• ゲーム全体を俯瞰する立場からの考察

• プレイヤー個人の立場からの考察

ex.) 複数のナッシュ均衡点、フォークの定理

繰り返し囚人のジレンマ コンテスト [Axelrod 1984]

複数の戦略プログラムの総当たり対戦

有限繰り返し囚人のジレンマ ナッシュ均衡戦略：all-D…高い利得を獲得できるか？ お互いにDを選択すれば、お互いCよりも低い利得

実際に繰り返し囚人のジレンマをおこなう場合、

どのような戦略を選択すればよいのだろうか？

繰り返し囚人のジレンマ コンテスト 2

ルール

_{総当り対戦…各対戦は200回繰り返しを5回おこなう}

評価…対戦で得られた利得の合計

⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 2 , 2 1 , 4 4 , 1 3 , 3 C D C D コンテストで用いられた 利得行列

結果

優勝

…

しっぺ返しの戦略

上位を占めた戦略の特徴

キングメーカーの存在

自分から裏切らない = 上品さ（nice） 相手が裏切っても再び協調し合える = 心の広さ（forgiveness）

プレイヤー

心理学、経済学、政治学、数学、社会学の分野に属する

14名に作成されたプログラム ＋ ランダム プログラム

第1回コンテストの概要

繰り返し囚人のジレンマ コンテスト 3

ルール

前回の分野 ＋コンピュータサイエンス、物理学等の分野に

属する62名に作成されたプログラム ＋ランダム プログラム

プレイヤー

前回のルール ＋ 繰り返し回数の確率的変動

結果

優勝… しっぺ返しの戦略 上位を占めた戦略の特徴 第1回コンテストの結果を踏まえた参加プログラムの２つの傾向 1．上品で心が広いプログラム （しっぺ返しの戦略の踏襲） 2. 1のようなプログラムから搾取を狙うプログラム → 1 同士では協調、2 同士で裏切り合い 上品で心が広い… 傾向1 → 前回と同様 非協調的な相手

（ex. all-D）

には裏切り

第2回コンテストの概要

繰り返し囚人のジレンマ コンテスト 4

ルール

各戦略毎に種

プレイヤー

前回のルール ＋ 繰り返し回数の確率的変動

結果

優性種の交代

最近の研究

高い利得を獲得した種が増加するfitness 関数