調和系工学 ゲーム理論編

ゲーム理論 第二部
知的都市基盤工学
5月23日(水)５限(16:30～18:10）
繰り返しゲーム
マルチエージェントシステム
複数のエージェントの連続的に繰り返される意思決定
どのような記述が適しているか？
「ある環境状況が繰り返し訪れる中での意思決定」と捉える
繰り返しゲーム…戦略形ゲームの繰り返しにおける意思決定
マルチエージェントシステム
＝ 終焉のない動的な環境
2人無限（有限）繰り返しゲーム
2人非ゼロ和ゲームを無限（有限）回繰り返しおこなう
無限繰り返しゲームの定式化 1
2人非ゼロ和ゲーム
１．プレイヤーの数は2人
２．利得の和はゼロとは限らない
３．各プレイヤーのとりうる戦略の数は有限
４．ゲームは一回限り
５．各プレイヤーは相手の戦略に関して情報を持たない
2人無限繰り返しゲーム
,
４ ．同一のゲームを無限に繰り返しおこなう
プレイヤーは過去のプレイの結果に依存して行動
無限繰り返しゲームの定式化 2
1. 成分ゲーム
成分ゲーム：戦略形ゲーム
G = (N , S, F )
• プレイヤー集合 N = {1, 2}
• 行動集合
A = A1 × A2
A1 ,A2 : プレイヤー1とプレイヤー2の行動の集合
• 利得関数
f = f1 × f 2
f1, f2 : プレイヤー1とプレイヤー2の利得関数
2. 繰り返し回数
成分ゲームG をt = 0 から t = T まで繰り返す
T ：有限な自然数
有限繰り返しゲーム
T ：無限大
無限繰り返しゲーム
GT
G∞
無限繰り返しゲームの定式化 3
3. 戦略
• 成分ゲームの純戦略
繰り返しゲームの 行動の決定
プレイヤー1とプレイヤー2の行動
a1 ∈ A1 , a 2 ∈ A2
• 繰り返しゲームの戦略
過去のプレイの結果に依存して毎回成分ゲームの行動を決定する指針
プレイヤー1とプレイヤー2の戦略
ex.) 囚人のジレンマ
s1 ∈ S1 , s 2 ∈ S 2
行動 ：C または D
戦略 ：しっぺ返しの戦略
• 行動の列
プレイヤーの戦略の組 s = (s1, s2 ) に対して、行動の列が定まる
a (s ) = (a1 ,..., a T ), a t = ( a1t , a 2t ) t = 1,2,...
無限繰り返しゲームの定式化 4
4. ゲームの履歴
成分ゲームGのk 回目のプレイの結果
繰り返しゲームの特徴的な要素
• その回のプレイヤーの利得の組
x = ( x1 , x 2 )
• その回の選択された純戦略の組
a = ( a1 , a 2 )
これらを用いて k 回目のプレイの結果をo
k
と表現すると
1回目から t 回目までの結果の系列を以下のように表す
h ( t ) = ( o 1 , o 2 ,..., o t )
この結果の系列をゲームの履歴という
無限繰り返しゲームの定式化 5
5. 利得
t=0 における将来にわたって得られる利得についての期待値
繰り返し期間が長い場合
割引因子
δ
一般的に近い将来に得られる利得に比べて
遠い将来の利得は割り引いて考える
の導入 ( 0 <
δ < 1)
t 回目のプレイヤー1の利得の現在価値（割引利得）：
δ t f 1 ( a 1t , a 2t )
プレイヤー1の割引利得の総和（割引利得和）：
∞
F1 ( s1 , s 2 ) = ∑ δ t f1 ( a1t , a 2t )
t =1
合理的なプレイヤーは割引利得和の最大化を目指す
無限繰り返しゲームの定式化 6
6. 共通認識
プレイヤーはこれらの要素に関して共通認識がある
• 成分ゲーム G
• 繰り返し回数 T
• ゲームの履歴 h(t)
7. ゲームの前提条件
合理的なプレイヤー
1) 利得の最大化を目指す
1‘) 割引利得和の最大化を目指す
2) 相手の行動を可能な限り推論
自分の選択した戦略に対して相手が割引利得和を最大
にするような最適な戦略を選択するとして戦略を選択
再掲：囚人のジレンマ
囚人のジレンマの利得行列
プレイヤー2
C
D
⎡3,3 1,4 ⎤
⎢
⎥
裏切（Defect）:D 4,1 2,2
⎣
⎦
協調（Cooperate）:C
プレイヤー1
（協調＝黙秘、裏切＝自白）
右がプレイヤー1の利得
左がプレイヤー2の利得
ナッシュ均衡点
プレイヤーの合理的な意思決定の結果
無限繰り返し囚人のジレンマ 1
一度きりの囚人のジレンマにおける合理的な行動は？
→ 裏切りの選択
無限繰り返し囚人のジレンマにおける合理的な行動選択は？
→ 全ての戦略を列挙することは不可能
戦略をパターン化して規定
繰り返し囚人のジレンマにおける代表的な戦略
1．all-D
過去のプレイの結果によらず常に D を出す
2．all-C
過去のプレイの結果によらず常に C を出す
3．しっぺ返し
( tit for tat )
最初はCを出す．2回目以降、相手が前回のゲームで
出した行動と同じ行動をとる
無限繰り返し囚人のジレンマ 2
all-D…過去の自分、相手の行動の履歴によらず、必ずDを選択する戦略
2人ともall-Dを選択した場合の毎回の行動と実現する利得ベクトル
1回目
2回目
行動
(
プレイヤー1 プレイヤー2
の行動 , の行動
) (D,D)
(D,D)
利得
(
プレイヤー1 プレイヤー2
の利得 , の利得
)
(2,2)
(2,2)
…
…
…
t 回目
(D,D)
(2,2)
∞
プレイヤー1とプレイヤー2のそれぞれの割引利得和は
利得ベクトルは
2 ⎞
⎛ 2
,
⎟
⎜
⎝1− δ 1− δ ⎠
に収束
…
…
…
2
2δ =
∑
1− δ
t =1
t
無限繰り返し囚人のジレンマ 3
all-C…過去の自分、相手の行動の履歴によらず、必ずCを選択する戦略
2人ともall-Cを選択した場合の毎回の行動と実現する利得ベクトル
1回目
2回目
行動
(
プレイヤー1 プレイヤー2
の行動 , の行動
)
(C,C)
(C,C)
利得
(
プレイヤー1 プレイヤー2
の利得 , の利得
)
(3,3)
(3,3)
…
…
…
t 回目
(C,C)
(3,3)
∞
プレイヤー1とプレイヤー2のそれぞれの割引利得和は
利得ベクトルは
3 ⎞
⎛ 3
,
⎟
⎜
⎝1− δ 1− δ ⎠
に収束
…
…
…
3
3δ =
∑
1− δ
t =0
t
無限繰り返し囚人のジレンマ 4
プレイヤー1が all-C、プレイヤー2が all-D の場合に
毎回の行動と実現する利得ベクトル
1回目
2回目
行動
(C,D)
(C,D)
利得
(1,4)
(1,4)
プレイヤー1の
割引利得和
∞
1
t
1
δ
=
∑
1− δ
t =0
利得ベクトルは
…
…
…
t 回目
(C,D)
(1,4)
…
…
…
プレイヤー2の
割引利得和
4 ⎞
⎛ 1
,
⎟
⎜
⎝1− δ 1− δ ⎠
に収束
∞
t
4
δ
∑ =
t =0
4
1− δ
無限繰り返し囚人のジレンマ 5
しっぺ返し… 初回C を出し、 2回目以降相手の前回の行動と同じ行動を選択
前回相手が協調 → 今回自分も協調
前回相手が裏切り → 今回自分も裏切り
2人ともしっぺ返しを選択した場合の毎回の行動と実現する利得ベクトル
1回目
2回目
行動
(C,C)
(C,C)
利得
(3,3)
(3,3)
…
…
…
t 回目
(C,C)
(3,3)
…
…
…
∞
プレイヤー1とプレイヤー2のそれぞれの割引利得和は
利得ベクトルは
3 ⎞
⎛ 3
,
⎟
⎜
⎝1− δ 1− δ ⎠
に収束
3
3δ =
∑
1− δ
t =0
t
無限繰り返し囚人のジレンマ 6
プレイヤー1が しっぺ返し、プレイヤー2が all-D の場合に
毎回の行動と実現する利得ベクトル
1回目
2回目
行動
(C,D)
(D,D)
利得
(1,4)
(2,2)
プレイヤー1の
割引利得和
…
…
…
1+ δ
1 + ∑ 2δ t =
1− δ
t =1
∞
利得ベクトルは
t 回目
(D,D)
(2,2)
…
…
…
プレイヤー2の
割引利得和
⎛ 1 + δ 4 − 2δ ⎞
,
⎟
⎜
⎝1− δ 1− δ ⎠
に収束
∞
4 + ∑ 2δ t =
t =1
4 − 2δ
1− δ
無限繰り返し囚人のジレンマ 7
プレイヤー1が しっぺ返し、プレイヤー2が 3回目だけ必ずD を選択する
変形しっぺ返しの場合に毎回の行動と実現する利得ベクトル
行動
利得
1回目 2回目 3回目 4回目 5回目 6回目
(C,C) (C,C) (C,D) (D,C) (C,D) (D,C)
(3,3)
(3,3)
(1,4)
(4,1)
(1,4)
∞
プレイヤー1の
割引利得和
3 + 3δ + ∑ (δ + 4δ )δ
プレイヤー2の
割引利得和
3 + 3δ + ∑ ( 4δ 2 + δ 3 )δ 2 k
2
k =0
∞
k =0
3
2k
(4,1)
…
…
…
以降 (C,D) (D,C)
の繰り返し
δ 2 (1 + 4δ )
= 3 + 3δ +
1− δ 2
δ 2 (4 + δ )
= 3 + 3δ +
1−δ 2
(プレイヤー2 の割引利得和) ＞ (プレイヤー1の割引利得和)
δの値によっては ( δ＞1/2 )
(プレイヤー2 の割引利得和) ＜ (お互いしっぺ返しの場合の割引利得和)
目先の利益のための D の選択 → 合理的ではない
無限繰り返し囚人のジレンマ 8
all-D と all-C が選択可能な場合の割引利得和の利得表
プレイヤー2
all-C
プレイヤー1
all-C
all-D
3
1− δ
4
1− δ
3
,
1− δ
1
,
1− δ
all-D
1
1− δ
2
1− δ
4
,
1− δ
2
,
1− δ
「相手が all-C」 → 自分の割引利得和を最大にする戦略は「 all-D 」
「相手が all-D」 → 自分の割引利得和を最大にする戦略は「 all-D 」
プレイヤー1、プレイヤー2のそれぞれの戦略に対する最適反応戦略は「 all-D 」
(all-D, all-D) がナッシュ均衡
無限繰り返し囚人のジレンマ 9
all-D, all-C, しっぺ返し が選択可能な場合の割引利得和の利得表
プレイヤー2
all-C
プレイヤー1
all-D
しっぺ返し
all-C
3 ,3
1, 4
3 ,3
all-D
4 ,1
2 ,2
4−2δ,1+δ
しっぺ返し
3 ,3
1+δ ,4 − 2δ
3 ,3
ただし、表中の値は全て
1−δ
倍してある
無限繰り返し囚人のジレンマ 10
all-D, all-C, しっぺ返し が選択可能な場合の最適反応戦略
1. 相手の all-C
→ all-D
2. 相手の all-D
→ all-D
3. 相手のしっぺ返し → 割引因子δ の値により変化
割引利得和
しっぺ返しに対して
all-C 又はしっぺ返し
3
1− δ
しっぺ返しに
対して all-D
4 − 2δ
1−δ
最適反応戦略…割引因子による場合分け
3 < 4 − 2δ (δ < 1 / 2) … all-D
3 = 4 − 2δ (δ = 1 / 2) … all-D, all-C, しっぺ返し
3 > 4 − 2δ (δ > 1 / 2) … all-C, しっぺ返し
無限繰り返し囚人のジレンマ 11
3 < 4 − 2δ (δ < 1 / 2)
である場合の最適反応戦略
プレイヤー1のプレイヤー2に対する最適反応戦略
プレイヤー2のプレイヤー1に対する最適反応戦略
ナッシュ均衡（定理１より）
プレイヤー2
all-C
プレイヤー1
all-D
しっぺ返し
all-C
3 ,3
1, 4
3 ,3
all-D
4 ,1
2 ,2
4−2δ,1+δ
しっぺ返し
3 ,3
1+δ ,4 − 2δ
3 ,3
ただし、表中の値は全て
1−δ
倍してある
無限繰り返し囚人のジレンマ 12
3 ≥ 4 − 2δ (δ ≥ 1 / 2)
である場合の最適反応戦略
プレイヤー1のプレイヤー2に対する最適反応戦略
プレイヤー2のプレイヤー1に対する最適反応戦略
(δ = 1 / 2) の場合の最適反応戦略
プレイヤー2
all-C
プレイヤー1
all-D
しっぺ返し
all-C
3 ,3
1, 4
3 ,3
all-D
4 ,1
2 ,2
4−2δ,1+δ
しっぺ返し
3 ,3
1+δ ,4 − 2δ
3 ,3
ただし、表中の値は全て
1−δ
倍してある
２つの
ナッシュ
均衡
無限繰り返し囚人のジレンマ 13
3 < 4 − 2δ (δ < 1 / 2)
ただし、表中の値は全て
(1,4)
お互いしっぺ返しの
場合の割引利得和
(3,3)
(1 + δ ,4 − 2δ )
1−δ
倍してある
しっぺ返しに対する
all-Dの割引利得和
4 − 2δ
＞
プレイヤー1：all-D
プレイヤー2：しっぺ返し
の場合の割引利得和
のとる範囲
の場合
しっぺ返しに対する
しっぺ返しの割引利得和
3
(2,2)
(4,1)
プレイヤー2
の利得
(4 − 2δ ,1 + δ )
プレイヤー1
の利得
プレイヤー1：しっぺ返し
プレイヤー2：all-D
の場合の割引利得和のとる範囲
しっぺ返しを選択する
誘因がない
無限繰り返し囚人のジレンマ 14
プレイヤー1：all-D
プレイヤー2：しっぺ返し
の場合の割引利得和
のとる範囲
(1 + δ ,4 − 2δ )
(1,4)
の場合
ただし、表中の値は全て
お互いしっぺ返しの
場合の割引利得和
(3,3)
(2,2)
プレイヤー2
の利得
(4 − 2δ ,1 + δ )
(4,1)
プレイヤー1
の利得
プレイヤー1：しっぺ返し
プレイヤー2：all-D
の場合の割引利得和のとる範囲
1−δ
倍してある
しっぺ返しに対する
all-Dの割引利得和
4 − 2δ
＞
3 ≥ 4 − 2δ (δ ≥ 1 / 2)
しっぺ返しに対する
しっぺ返しの割引利得和
3
しっぺ返しを選択する
誘因が発生
無限繰り返し囚人のジレンマ 15
無限に繰り返される囚人のジレンマ
ゲームの環境として長期にわたる相互関係が保障
＋
十分に大きい割引因子δ
プレイヤーが将来の利得を高く評価 →長期の相互関係と認識
一回ゲーム… (D,D)の系列を実現する戦略の組のみがナッシュ均衡
繰り返しゲーム… (C,C)の系列を実現する戦略の組がナッシュ均衡に含まれる
ゲームの無限繰り返しによる
協調の可能性の発生