(1)(2)ゲーム理論とは
マルチエージェントシステム
あるエージェントの意思決定
⇔ 他のエージェントの意思決定
ゲーム的状況 : エージェント間の相互依存関係 …対立と協力
合理的意思決定を解析する理論の必要性
利害が対立するプレイヤーの合理的行動を表現する数理モ
デルを構築し､数理的に合理的行動の一般的特性を導出
ゲーム理論 [1944 フォン・ノイマン，オスカー・モルゲンシュテルン]
ゲーム理論の歴史
1944年
1990年
1990年
進化ゲーム理論
1994年
フォン・ノイマンとオスカー・モルゲンシュテルン
「ゲームの理論と経済行動」の出版
［Axelrod：The evolution of cooperation, 1984］
限定合理性アプローチ…合理性アプローチに対する再検討
完全合理性アプローチ…
情報処理や計算能力に関する限定
合理的推論結果に対する限定
［Maynard：Evolution and the theory of games, 1982］
1950年 ジョン･ナッシュによるナッシュ均衡解の提唱
例）チェーンストア パラドックス ［Selten: 1990］
ナッシュ、ゼルテン、ハルサニがノーベル経済学賞受賞
1980～
ナッシュ均衡解の提唱、均衡解の選択理論
主体は利益の最大化を目指し､
相手の行動を可能な限り推論
ゲームの分類
分類 1
非協力ゲーム…拘束力のある合意なし
協力ゲーム…拘束力のある合意あり
分類 2
戦略形ゲーム…一度きりの行動決定を同時におこなう
•ゼロ和ゲーム…全員の利得の総和がゼロ ex.) ジャンケン
•非ゼロ和ゲーム…全員の利得の総和が非ゼロ
繰り返しゲーム…同じゲームを繰り返しおこなう
•無限繰り返しゲーム…戦略形ゲームを無限回繰り返す
•有限繰り返しゲーム…戦略形ゲームを有限回繰り返す
展開形ゲーム…行動決定を時間の経過とともにおこなう
ex.) 将棋、チェス
戦略形ゲームの表現
戦略形ゲームの構成要素
¾ プレイヤー …決定主体は誰か？
¾ 戦略…プレイヤーはどのような行動計画を持つか？
¾ 利得…戦略の選択の結果に対してどのような評価を持つか？
}
2
,
1
{
=
N
¾ プレイヤー集合
¾ 戦略集合
¾ 利得関数（利得行列）
例） 2人でジャンケン
=
A
｛グー、チョキ､パー｝
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
0
1
1
1
0
1
1
1
0
グー チョキ パー
グー
チョキ
パー
A
勝：１
負：-１
引き分け：０
2人ゼロ和ゲームの一般型
ゲームに参加する全てのプレイヤーはゲームに関する全ての
ルールを完全に知っていて、全てのプレイヤーが他のプレイヤーも
ゲームのルールを完全に知っていることを相互に認識し合っている
合理的なプレイヤー…
共有知識…
1) 利得の最大化を目指す
2) 相手の行動を可能な限り推論する
ゲームの前提条件
2人ゼロ和ゲーム
１．プレイヤーの数は2人
２．利得の和はゼロ
３．各プレイヤーのとりうる戦略の数は有限
４．ゲームは一回限り
５．各プレイヤーは相手の戦略に関して情報を持たない
ゲームのルール… プレイヤーの集合、プレイヤーの目的、選択可能な行動の
集合等のゲームの進行を定めるさまざまな規定
2人ゼロ和ゲーム
}
2
,
1
{
=
N
¾ プレイヤー集合
例） あるゲーム
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
−
−
−
−
−
2
,
2
1
,
1
3
,
3
3
,
3
0
,
0
3
,
3
2
,
2
1
,
1
4
,
4
¾ 戦略集合
¾利得関数
}
3
,
2
,
1
{
1
=
S
S
2 =
{
1
,
2
,
3
}
1 2 3
1
2
3
プレイヤー1
プレイヤー2
この双行列では、
左側の要素がプレイヤー1の利得
右側の要素がプレイヤー2の利得
を表わしている
プレイヤー2の利得…
-3
プレイヤー1の利得…
3
同一の行列に対して、お互いに最大を求めて行動
利害の対立する状況 単純な最大化原理によって
プレイヤーの行動を考えることはできない
どのような行動原理を用いるべきだろうか？
ミニマックス原理
プレイヤー1 のミニマックス行動
1 2 3
1
2
3
プレイヤー1
プレイヤー2
2
)
2
,
1
,
4
min(
−
−
=
−
3
)
3
,
0
,
3
min(
−
=
−
1
)
2
,
1
,
3
min(
=
1
)
1
,
3
,
2
max(
−
−
=
プレイヤー1の戦略1～3に対しての保障水準を求める
保障水準…プレイヤー2がどの戦略を選択しても最
低限獲得できるプレイヤー1の利得
最低限得られる利得の中から
最大の利得を選択する
①
②
①
②
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
−
−
−
−
−
2
,
2
1
,
1
3
,
3
3
,
3
0
,
0
3
,
3
2
,
2
1
,
1
4
,
4
=
−
−
−
1
,
2
),
min(
3
,
0
,
3
),
min(
3
,
1
,
2
))
,
4
max(min(
プレイヤー1は戦略3を選択すれば、
最低でも利得1 は獲得できる
ミニマックス原理
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
−
−
−
−
−
2
,
2
1
,
1
3
,
3
3
,
3
0
,
0
3
,
3
2
,
2
1
,
1
4
,
4
1 2 3
1
2
3
プレイヤー1
プレイヤー2
4
)
3
,
3
,
4
min(
−
−
=
−
1
)
1
,
0
,
1
min(
−
=
−
3
)
2
,
3
,
2
min(
−
−
=
−
1
)
3
,
1
,
4
max(
−
−
−
=
−
プレイヤー2の
戦略1～3に対しての
保障水準を求める 最低限得られる利得の中から
最大の利得を選択する
①
②
①
②
c
a
b
c
a
b
プレイヤー2 のミニマックス行動
プレイヤー2は戦略2選択すれば、
最低でも利得-1 は獲得できる
ミニマックス原理
プレイヤー1とプレイヤー2 のミニマックス行動をまとめると…
1 2 3
1
2
3
プレイヤー1
プレイヤー2
2
)
2
,
1
,
4
min( − − = −
3
)
3
,
0
,
3
min(
−
=
−
1
)
2
,
1
,
3
min( =
1
)
1
,
0
,
1
min( − = −
4
)
3
,
3
,
4
min(− − = −
2
)
2
,
3
,
2
min( − − = −
1
)
2
,
1
,
4
max(
−
−
−
=
1
)
1
,
3
,
1
max(
−
−
=
プレイヤー1は戦略3を選択し、
プレイヤー2は戦略2を選択する
それ以外の戦略を選択すると
獲得できる利得が減ってしまう
戦略の組（3,2）を均衡点、
プレイヤー1の戦略3と
プレイヤー2の戦略2を
最適戦略という
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
−
−
−
−
−
2
,
2
1
,
1
3
,
3
3
,
3
0
,
0
3
,
3
2
,
2
1
,
1
4
,
4
プレイヤー1は戦略3を選択
プレイヤー2は
戦略2を選択
非ゼロ和ゲーム
ゼロ和ゲームから非ゼロ和ゲームへ
• ゼロ和ゲーム
自分の利益＝相手の損失
協力の可能性なし
自分の損失＝相手の利益
• 非ゼロ和ゲーム
自分の利益＝相手の損失？
協力の可能性が
生まれるか？
自分の損失＝相手の利益？
2人非ゼロ和ゲームの一般型
ゼロ和ゲーム
１．プレイヤーの数は2人
２．利得の和はゼロ
３．各プレイヤーのとりうる戦略の数は有限
４．ゲームは一回限り
５．各プレイヤーは相手の戦略に関して情報を持たない
２．利得の和はゼロ を変更する
非ゼロ和ゲーム
２‘．利得の和はゼロとは限らない
2人非ゼロ和ゲームの一般型
プレイヤー1とプレイヤー2の戦略集合
}
,...,
2
,
1
{
1
m
S
=
S
2 {
1
,
2
,...,
n
}
2
1
, S
S
=
プレイヤー1の利得行列
A=(a
ij)
とプレイヤー2の利得行列
B=(b
ij)
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
=
mn
n
n
m
ij
b
b
b
b
b
b
b
B
M
L
L
L
L
M
2
1
1
21
11
)
(
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
=
mn
n
n
m
ij
a
a
a
a
a
a
a
A
M
L
L
L
L
M
2
1
1
21
11
)
(
A,B
をまとめて双行列
G
で表す
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
=
mn
mn
n
n
n
n
m
m
ij
ij
b
a
b
a
b
a
b
a
b
a
b
a
b
a
G
,
,
,
,
,
,
)
,
( 2 2
1
1
1
1
21
21
11
11
M
L
L
L
L
M
a
ij +
b
ij =
0
が常に成り立っている場合
ゼロ和ゲームは双行列
G
において
囚人のジレンマ
2人の容疑者は隔離…相談は不可能
容疑者2
黙秘
黙秘 自白
1年,1年 10年,3ヶ月 右が容疑者1の刑期、
左が容疑者2の刑期
容疑者1
3ヶ月, 10年 8年,8年
自白
二人とも黙秘…二人とも懲役1年 一方が黙秘、一方が自白
二人とも自白…二人とも懲役8年 黙秘…懲役10年 自白…懲役3ヶ月
双行列表現
⎥
⎦
⎤
⎢
⎣
⎡
=
=
2
,
2
1
,
4
4
,
1
3
,
3
)
,
(
a
ij b
ij
G
右がプレイヤー1の利得、
左がプレイヤー2の利得
囚人のジレンマ
•容疑者１の合理的な思考
•容疑者２の合理的な思考
そのとき自分は黙秘に変えると刑期が
延びてしまうから，自白に留まる．
もし相手が黙秘するならば，
自分は自白をするのが適当である．
もしそうすると，相手は黙秘から
自白に変えるであろう．
2人とも自白を選択…二人とも懲役８年
そのとき自分は黙秘に変えると刑期が
延びてしまうから，自白に留まる．
もし相手が黙秘するならば，
自分は自白をするのが適当である．
もしそうすると，相手は黙秘から
自白に変えるであろう．
ナッシュ均衡とは
非ゼロ和ゲームの均衡解
ナッシュ均衡解
均衡解に自己拘束性がなければ必ず少なくとも一人のプレイヤーはその均衡
から離脱する動機を持つ.このときゲームの解自体は拘束力のある合意に
基づくものではないから,実際のプレイがゲームの解と一致する保証はない
自己拘束性を持つため非ゼロ和ゲームに
おける合理的行動の解となり得る
自己拘束性の必要性
相手のナッシュ均衡戦略に対して自分の利得を
最大にする戦略はナッシュ均衡戦略である
他のすべてのプレイヤーがナッシュ均衡点に従うと
予想するとき,どのプレイヤーも自らそのナッシュ
均衡点から離脱する動機を持たない
定義…
ナッシュ均衡の定義
定義 5
ナッシュ均衡
［Nash, 1950］
戦略の組
s
*
=
(
s
1*
,
s
*
2)
)
,
(
max
)
,
(
1*
2*
1 1 2*
1
1
1
s
s
f
s
s
f
S
s ∈
=
が
)
,
(
max
)
,
(
1*
2*
2 1*
2
2
2
2
s
s
f
s
s
f
S
s ∈
=
*
s
をナッシュ均衡点という
を満たすとき
相手のナッシュ均衡戦略に対して自分の利得を
最大にする戦略はナッシュ均衡戦略である
最適反応戦略の定義
定義 1
最適反応
)
,
(
max
)
,
(
1*
2 1 1 2
1
1
1
s
s
f
s
s
f
S
s ∈
=
*
1
s
がプレイヤー2の 戦略
s
2 に対する
定義 2
最適反応戦略
最適反応戦略であるとは、
であるときをいう
)
,
(
1 2
1
s
s
f
このとき
相手がある戦略を取ったときに，その戦略のもとで自分の利益を
最大にするように行動するという行動原理を最適反応原理という
最適反応原理により選択された戦略を最適反応戦略という
プレイヤー1の戦略
はプレイヤー1の利得関数である
最適反応戦略
囚人のジレンマでの最適反応戦略
⎥
⎦
⎤
⎢
⎣
⎡
2
,
2
1
,
4
4
,
1
3
,
3
黙秘
プレイヤー2
黙秘
自白
自白
右がプレイヤー1の利得、
左がプレイヤー2の利得
プレイヤー1
プレイヤー1、プレイヤー2のそれぞれ戦略に対する最適反応戦略
「相手が黙秘」
自分の利得を最大にする戦略は「自白」
「相手が自白」
自分の利得を最大にする戦略は「自白」
最適反応戦略集合の定義
定義 3 最適反応戦略集合
プレイヤー1の任意の戦略
最適反応戦略は，存在するとしてもただ一つであるとは限らない．
その集合を最適反応戦略集合
1
s
に対するプレイヤー2の
)
(
1
2
s
R とすると
}
)
,
(
max
)
,
(
,
{
)
(
2
2
2
1
2
*
2
1
2
2
*
2
1
2
S
s
s
s
f
s
s
f
S
s
s
R
∈
=
∈
=
最適反応戦略集合
囚人のジレンマでの最適反応戦略集合
⎥
⎦
⎤
⎢
⎣
⎡
2
,
2
1
,
4
4
,
1
3
,
3
黙秘
プレイヤー2
黙秘
自白
自白
右がプレイヤー1の利得、
左がプレイヤー2の利得
プレイヤー2
プレイヤー2の各戦略に対するプレイヤー1の最適反応戦略集合
1
R
（「プレイヤー2が黙秘」） ＝｛「自白」｝
1
R
（「プレイヤー2が自白」） ＝｛「自白」｝
プレイヤー1の各戦略に対するプレイヤー2の最適反応戦略集合
2
R
（「プレイヤー1が黙秘」）＝｛「自白」｝
2
R
（「プレイヤー1が自白」）＝｛「自白」｝
最適反応集合の定義
最適反応集合
プレイヤー 1の戦略 とそれに対するプレイヤー 2の
最適反応戦略の組の集合をプレイヤー2の最適反応集合，
プレイヤー2の戦略 とそれに対するプレイヤー1の
最適反応戦略の組の集合をプレイヤー1の最適反応集合とよぶ．
1
s
2
s
定義 4
1
D
2
D
プレイヤー2の最適反応集合を とすると，次のように表される．
プレイヤー1の最適反応集合を ,
}
),
(
:
)
,
(
{
1 2 1 1 2 2 2
1
s
s
s
s
R
s
s
S
D
=
=
∈
∈
)}
(
,
:
)
,
(
{
1 2 1 1 2 2 1
2
s
s
s
s
S
s
R
s
D
=
=
∈
∈
最適反応集合
囚人のジレンマでの最適反応集合
プレイヤー2に対するプレイヤー1の最適反応集合
1
R
（「プレイヤー2が黙秘」） ＝｛「自白」｝
1
R
（「プレイヤー2が自白」） ＝｛「自白」｝
＝｛（自白,黙秘）,（自白,自白）｝
1
D
（プレイヤー１の戦略,プレイヤー２の戦略）
プレイヤー1に対するプレイヤー2の最適反応集合
2
R
2
R
（「プレイヤー1が黙秘」） ＝｛「自白」｝
（「プレイヤー1が自白」） ＝｛「自白」｝
＝｛（黙秘,自白）,（自白,自白）｝
2
D
ナッシュ均衡
定理 1
ナッシュ均衡の集合を
Ｄ
とすると次のことが成り立つ
2
1
D
D
D
=
∩
囚人のジレンマでのナッシュ均衡
＝｛（自白,黙秘）,（自白,自白）｝
1
D
D
2 ＝｛（黙秘,自白）,（自白,自白）｝
（プレイヤー１の戦略、プレイヤー２の戦略）
2
1
D
D
D
=
∩
＝｛（自白,自白）｝
定理 1 より
ゲーム理論的な合理的行動は「自白」を選択
