情報と戦略---ゲーム理論入門
内容
●
●
●
●
●
●
2015/10/1
ゲームの理論とは →合理的な戦略予測
誰と手を組むか
→協力ゲーム
最適応答で行動予測 →ナッシュ均衡
共通知識の役割 →混合戦略と相関戦略
意外な行動の意図は →信号と評判
長い付き合いと信頼 →繰り返しゲーム
情報と戦略---ゲーム理論入門
1
ゲーム理論とは
・ ゲーム理論（Game
Theory)は、自分自
身の利益が相手の
行動によって変化す
る状況において
人々の合理的行動
（ゲームの解）を予
測するための数学
モデルである。
2015/10/1
ゲーム理論や期待効用理論の最初の成
果は、フォン・ノイマンとモルゲンシュタン
によって『経済行動とゲームの理論』
（1944）という本にまとめられた。Ｎ人非協
力ゲームの均衡点はノイマンの生徒だっ
たジョン・ナッシュJr．によって1950年に発
表され、ゲーム理論の発展に決定的な役
割を果たした。
その後ゲーム理論は経済学だけでなく、
心理学、経営学、生物学、法学等の諸分
野で用いられた。 １９９４年、ナッシュはゼ
ルテン、ハルサニィの２人と共にノーベル
経済学賞を授与されその功績が称えられ
た。
情報と戦略---ゲーム理論入門
2
ゲームの形式
・ 大別して以下の４種類のゲーム形式がある。
・ 提携形ゲーム
・ もしくは協力ゲーム。誰と誰が組むと共有利益がいくらにな
るかが特性関数によって決まる。
・ 標準形ゲーム
・ 同時手番のゲームを表現する。戦略組と結果の対応は利
得表によって表される。繰り返しゲームに拡張できる。
・ 展開形ゲーム
・ 決定木を使って手番を明示する。先行するゲーム履歴は信
用できるシグナルとして解釈され得る。
・ 繰り返しゲーム
・ 標準形や展開形のゲームが有限ないし無限期間繰り返さ
れるゲーム。進化ゲーム論における中心的な考察対象。
2015/10/1
3
情報と戦略---ゲーム理論入門
協力ゲーム（提携形）
・ 協力ゲーム（提携形ゲーム）はプレイヤーの提携ないし結託
の戦略を分析する。
・ 非協力ゲームよりも数学的にエレガントである。
・ 公平な利益配分や費用分担、投票者の決定力などを明確
に計算できる。
・ 特性関数が凸であるゲームはバンドワゴン効果（ネット
ワーク外部性）のような興味深い社会現象を説明できる。
・ 各プレイヤーはいったん合意した提携にコミットするものと
仮定されるが、その解概念は多彩である。
これと対照的に、非協力ゲームはその前提として、拘束力の
ある合意をとりつける（ゲームの外での）コミュニケーションは
不可能だが、解概念はナッシュの最適反応だけである。
2015/10/1
情報と戦略---ゲーム理論入門
4
協力ゲームの解
・ 提携形ゲーム（N,ｖ）ないし（N,ｖ，X）はプレイ
ヤー集合Nと特性関数ｖ：２N→Rの集合Xに
よって定義される。 またＸは利得ベクトルｘ＝
（ｘ１，…，ｘN）の集合である。
・ 提携S⊆N、φ⊆Sに対して特性関数の値ｖ（S)
は提携値と呼ばれ、実現された共通利益を
表す。ただしｖ（φ）＝０である。
・ 協力ゲームの解Fは、利得ベクトル集合Xか
らその部分集合F（N,v,X)⊆Xを特定する。
2015/10/1
情報と戦略---ゲーム理論入門
もし提携外の
N－Sの行動
が心配ならば、
例えばその最
悪の場合を
想定すればよ
い（VNM型特
性関数）。
5
協力ゲームの例と配分
・ ３人多数決ゲーム
・ １万円を３人で分ける方法を多数派が決定できる場合。
・ N={1,2,3}、
・ ｖ（φ）＝ｖ（｛１｝）＝ｖ（｛2｝）＝ｖ（｛3｝）＝０、
・ ｖ（｛１，2｝）＝ｖ（｛2，3｝）＝ｖ（｛3，1｝）＝ｖ（｛１，2，3｝）＝ １、
・ ただし利得ｘの実現値は多数派内部の勢力関係に依存しており、これ
だけでは分からない。配分（Imputation)とは以下の意味で合理的な利
得のことである。
・ 配分
・ 全体合理性： ｖ（N)＝ｘ１+･･･+ｘN
・ 個人合理性： ｘｉ≧ｖ（{ｉ})、i ＝ １、…、N．
2015/10/1
情報と戦略---ゲーム理論入門
6
協力ゲームの解概念
提携Sにかんして配分ｘが配分yを支配するというのは、
ｘが実現可能Σｘi＝ｖ（Ｓ）で、Ｓ内のあるメンバーｉについ
てｘi＞ｙiのときであり、これをｘ ｄｏｍＳ ｙと書く。
・ 安定集合 ←ｖＮＭ解
・ その内部ではお互いに支配されない配分（Imputation)の全体。また外部
の配分は、内部のどれかによって支配される。
・ コア ← 支配されない配分の集合。
コアの概念はエッジワースによる完全競争均衡
の研究にさかのぼる。
・ コアは安定集合の共通部分に含まれるが、３人多数決ゲームのように存
在しないこともある。一方、凸ゲームでは一般に大きな集合になる。
・ 仁 ← 最小不満解
仁はシュマイドラー（Schmeidler）によって提案された。
・ 各提携Sの下で各プレイヤーの超過要求（＝自力で獲得できたはずの利
得－実際配分された利得）のベクトルを辞書式順序で最小化する。
・ シャープレー値 ←
i
i where S
S vS vS
SN
1
s 1!n s !.
n!
・ 各プレイヤーの各提携に対する貢献度を提携の成立確率で加重平均したもの。
シャープレー値φは一つの配分を定めるが、支配されない保証は無い。
シャープレー値はSharpleyによって提案された。
2015/10/1
情報と戦略---ゲーム理論入門
7
コアの例
・ コアの定義． Ｃｏｒｅ(N，v)＝｛x｜S⊆N→v（S)（S)≦Σｉ
∈Ｓxｉ、xは配分｝．
・ ２人交渉ゲーム
・ N={1,2}、ｖ（φ）＝ｖ（｛１｝）＝ｖ（｛2｝）＝０、ｖ（｛１，2｝）＝１．
・ コアは明らかにすべての配分の集合に一致する。
・ 配分
・ 全体合理性： ｖ（｛1，2｝)＝ｘ１+ｘ２、
・ 個人合理性： ｘ１≧０、ｘ２≧０．
2015/10/1
情報と戦略---ゲーム理論入門
8
Prologによるモデリング（提携
形）
・ 論理プログラミング言語Prologを用いて提携形ゲーム（N,ｖ，
X）とその解をモデリング＆シミュレーションしてみよう。これら
のプログラムは筆者のホームページから入手できる
(http://www.us.kanto-gakuen.ac.jp/indo)。
・ モデリング例
% a majority vote.
game(c1, form(characteristic),
players([a,b,c]), coalitions([[],[a],[b],[c],[a,b],[b,c],[a,c],[a,b,c]])).
game(c1,value,[],0).
game(c1,value,[a],0).
game(c1,value,[b],0).
game(c1,value,[c],0).
game(c1,value,[a,b],1).
game(c1,value,[b,c],1).
game(c1,value,[a,c],1).
game(c1,value,[a,b,c],1).
2015/10/1
情報と戦略---ゲーム理論入門
9
Prologによるモデリング（配分）
% imputation, and core
col_rat_outcome(G,players(N),payoff(A)):var(A),
game(G,form(characteristic),players(N),coalitions(C)),
member(N,C),
game(G,value,N,V),
length(N,LN),
allocation(LN,V,A).
individually_complain(G,J/N,RJ-AJ=Z/A,X):col_rat_outcome(G,players(N),payoff(A)),
nth1(K,N,J),
nth1(K,A,AJ),
game(G,value,[J],RJ),
Z is RJ - AJ,
(AJ < RJ -> X = yes; X = no).
imputation(game(G),players(N),payoff(A)):% collectively (i.e.,group) rational outcome.
col_rat_outcome(G,players(N),payoff(A)),
% individual rationality.
\+ individually_complain(G,_J/N,_RJ-_AJ=_Z/A,yes).
2015/10/1
情報と戦略---ゲーム理論入門
10
Prologによるモデリング（コア）
% imputation, and core
excess_of_coalition(G,Y/N,RY-AY=Z/A,X):coalitionally_complain(G,Y/N,RY-AY=Z/A,X).
coalitionally_complain(G,Y/N,RY-AY=Z/A,X):imputation(game(G),players(N),payoff(A)),
game(G,value,Y,RY),
Y \= N,
selected_sum(Y/N,_B/A,AY),
Z is RY - AY,
(AY < RY -> X = yes; X = no).
core(game(G),players(N),payoff(A)):imputation(game(G),players(N),payoff(A)),
% coaltional rationality.
\+ coalitionally_complain(G,_Y/N,_RY-_AY=_Z/A,yes).
2015/10/1
情報と戦略---ゲーム理論入門
11
Prologによるモデリング（実行
例）
?- core(game(c1),B,C).
No
?- core(game(c0),B,C).
B = players([a, b])
C = payoff([1, 0]) ;
B = players([a, b])
C = payoff([0, 1]) ;
No
?- core(game(c2),B,C).
B = players([a, b, c])
C = payoff([5, 0, 0]) ;
B = players([a, b, c])
C = payoff([4, 0, 1]) ;
B = players([a, b, c])
C = payoff([3, 0, 2]) ;
B = players([a, b, c])
C = payoff([2, 0, 3]) ;
2015/10/1
Yes
% game c0: a 2-person bargaining.
game(c0,
form(characteristic),
players([a,b]),
coalitions([[],[a],[b],[a,b]])).
game(c0,value,[],0).
game(c0,value,[a],0).
game(c0,value,[b],0).
game(c0,value,[a,b],1).
% game c3: cost-sharing problem among 3 cities.
game(c3,
form(characteristic),
players([a,b,c]),
coalitions([[],[a],[b],[c],[a,b],[b,c],[a,c],[a,b,c]])).
game(c3,value,[],0).
game(c3,value,[a],0).
game(c3,value,[b],0).
game(c3,value,[c],0).
game(c3,value,[a,b],6).
game(c3,value,[b,c],8).
game(c3,value,[a,c],0).
game(c3,value,[a,b,c],20).
情報と戦略---ゲーム理論入門
12
Prologによるモデリング（仁）
% sample execution
%-----------------------------------------------------/*
?- is_more_acceptable_than(c3,[12,4,4],[6,0,14],B,C).
B = [0, 0, -4, -4, -10, -12, -16]
C = [0, 0, 0, -6, -6, -14, -20]
Yes
?- nucleolus(A,B).
A = c1
B = [1, 0, 0] ;
A = c1
B = [0, 1, 0] ;
A = c1
B = [0, 0, 1] ;
A = c2
B = [3, 0, 2] ;
A = c3
B = [6, 7, 7] ;
No
?-
2015/10/1
% Schmeidler(1969)'s nucleolus
% ------------------------------------------------- %
% lexicographically minimizing the sorted complaining vector.
complain_vector(G,A,Zs):imputation(game(G),players(N),payoff(A)),
findall(Z,coalitionally_complain(G,_B/N,_=Z/A,_),Zs).
sorted_complain_vector(G,A,Z):complain_vector(G,A,S0),
asort(S0,S),
reverse(S,Z).
is_more_acceptable_than(G,A,A1):is_more_acceptable_than(G,A,A1,_,_).
is_more_acceptable_than(G,A,A1,Z,Z1):sorted_complain_vector(G,A,Z),
sorted_complain_vector(G,A1,Z1),
Z @< Z1.
nucleolus(G,A):imputation(game(G),players(_N),payoff(A)),
\+ is_more_acceptable_than(G,_A1,A).
情報と戦略---ゲーム理論入門
13
Prologによるモデリング（Shapley
値）
% Shapley(1953)'s value
% ------------------------------------------------- %
contribution(G,J,X,Y,A):game(G,form(characteristic),players(_N),coalitions(C)),
member(Y,C),
game(G,value,Y,VY),
member(J,Y),
subtract(Y,[J],X),
game(G,value,X,VX),
A is VY - VX.
coalition_formation(G,[],[]/N,[],0):game(G,form(characteristic),players(N),coalitions(_C)).
coalition_formation(G,[J|Z],Y/N,[A|B],P):coalition_formation(G,Z,X/N,B,_Q),
(X=N -> (!,fail);true),
contribution(G,J,X,Y,A),
game(G,value,Y,P).
contribution_to_coalition_formation(G,J,X,K,VJ/V):coalition_formation(G,X,N/N,VX,V),
nth1(K,X,J),
nth1(K,VX,VJ).
shapley(G,J/N,Ps,SV):game(G,form(characteristic),players(N),coalitions(_C)),
member(J,N),
bagof(VJ,
X^K^contribution_to_coalition_formation(G,J,X,K,VJ/_V),
Ps),
length(Ps,L),
sum(Ps,B),
SV is B / L.
shapley(G,N,V):- bagof(SV, J^Ps^shapley(G,J/N,Ps,SV), V).
% sample execution
?- shapley(A,B,C).
A = c1
B = [a, b, c]
C = [0.333333, 0.333333, 0.333333] ;
A = c3
B = [a, b, c]
C = [5, 9, 6] ;
A = c0
B = [a, b]
C = [0.5, 0.5] ;
No
2015/10/1
情報と戦略---ゲーム理論入門
14
非協力ゲーム理論の３要素
・ ゲームの基本３要素は、プレイヤー、戦略、結
果の各集合である。
・ ゲームに参加するプレイヤー
・ ゲームに参加する人達、あるいは機械や動物もありう
る。
・ プレイヤーの戦略
・ 各プレイヤーが選ぶことの出来る行動パターン
・ ゲームの結果
・ 全プレイヤーの戦略の組から決まる各人の利益（損失）
2015/10/1
情報と戦略---ゲーム理論入門
15
非協力ゲーム（標準形）
●非協力ゲームでは拘束力のある合意は不可能であると
考え、ゲームの結果はすべて各プレイヤーの合理性（最
適反応）の仮定から導く。
●標準形ゲームは以下のような表形式（利得表；Payoff
Matrix)によって表される。
2
1
ピザ
ピザ
うどん
うどん
2 , 1
0 , 0
0 , 0
1 , 2
表１．協調性が試されるゲーム
2015/10/1
情報と戦略---ゲーム理論入門
ゲームの利得は利益の金額
そそのものでなく、各プレイ
ヤーの期待効用であると仮定
する。すなわちこれらは各プレ
イヤーのリスクへの態度を反
映済みであり、混合戦略は期
待値の大小で評価できる。ま
たU=αU+βのようにアフィン変
換しても優劣は変わらない。
16
2
ナッシュ均衡
1
ピザ
ピザ
うどん
うどん
2 , 1
0 , 0
0 , 0
1 , 2
表１．協調性が試されるゲーム
●ナッシュ均衡はお互いに最適応答（Best Response)とな
る戦略の組によってもたらされるゲームの結果である。
つまり、ひとたび相手の行動を固定すると自分だけ行動
変更しても得にならない。
●最適反応組としてのNashの均衡点は、すべての非協力
ゲーム理論（Non-Cooperative Game Theory）が基礎とす
る唯一の解概念である。
●表1のゲームには２つのナッシュ均衡がある。
●ジャンケンには純粋戦略｛石、剪み、紙｝でのナッシュ均
衡は無い。
クールノ均衡は、相手の戦略を学習せず近視眼的に最適応答を続ける２
2015/10/1
つの寡占企業による繰り返しゲームが1回限りのゲームのナッシュ均衡
に収束するという例である。
17
情報と戦略---ゲーム理論入門
食事問題のナッシュ均衡
● （食事問題） プレイヤー1はピザが食べたい。プレイヤー２
はうどんが食べたい。 この２人が一緒に入る店を決めようとし
ている。この状況を模式化した表1のゲームには２つのナッ
シュ均衡がある。また表２のゲームは唯一のナッシュ均衡を
表２には唯一のナッシュ
22
持つ。
11
ピザ
ピザ
（ピザ,ピザ）
22 ,,12
0 ,,00
2.01
う
ど
ん
う
ど
ん
＞
＜２２
00 ,,02.01
＜１
＜
１
＜１
＞
１
ピザ
ピザ
う
ど
ん
う
ど
ん
＜
＜２２
11 ,,20.1
0.
表１
．
協調性が試さ
れるゲーム
表２
．
囚人ジレンマ型ゲーム
2015/10/1
情報と戦略---ゲーム理論入門
均衡があって非協力解で
あり、さらにこれが支配戦
略均衡でもある。協力解
は両者にとって望ましい
のだが最適反応でないた
め実現しない。
このタイプのゲームは
「囚人のジレンマ」と呼ば
れ、１９５０年代にドレッ
（うどん,うどん）
シャ-とフラッドの心理学実
験で使われ、タッカーに
よって紹介された。
18
混合戦略と相関均衡
●（混合戦略） 一定の確率で（純粋）戦略をランダマイズする行
動パターンを混合戦略という。
●（存在定理） 有限個の純粋戦略のｎ人ゲームで混合戦略が
使えるなら、ナッシュ均衡は必ず存在する。
●（相関均衡） 各プレイヤーが観察できるランダム信号を発信
する共通の装置があるとき、信号に依存した戦略の下での均
衡利得は混合戦略のそれを改善する。
ノイマンらのミニマックス定理を拡張したこの定理の証明には角谷の不動点定理
が用いられた。
2015/10/1
情報と戦略---ゲーム理論入門
19
Let
p P r(Pizza, player1),
q P r(Pizza, player2).
Then the" expected payoffs" of each player is
混合均衡の例
v1 ( p, q ) 2 pq (1 p)(1 q )
● 食事問題における混合ナッシュ戦略組は（ｐ
＝２/３、ｑ＝１/３）である。つまり両者とも3回
に１回妥協することによって均衡利得（2/3、
2/3）を落し所として実現する。 (右式）
● 注意！ ところで両者が等確率1/2で選んだ
場合、実現される利得組は（3/4、3/4）だが、
これはいずれにとってもより高い利得に改善
する機会を有しており、均衡として成立しえな
い。
(3q 1) p (1 q ),
v2 ( p, q) pq 2(1 p)(1 q )
(3 p 2)q 2(1 p).
v1
2q (1 q) 3q 1 0 q 1 / 3.
p
v2
p 2(1 p) 3 p 2 0 p 2 / 3.
q
Therefore the equilibrium payoff vectoris
v1 ( p 1 / 3, q 2 / 3) (1 1 / 3) 2 / 3,
*
v2 ( p 1 / 3, q 2 / 3) 2(1 2 / 3) 2 / 3.
*
● ジャンケンの混合戦略均衡は等確率１/３
でランダマイズすることである。つまり相
手が等確率で選ぶ限り、いずれの純粋
戦略についても確率１/３から増やすのも
減らすのも損である。
2015/10/1
情報と戦略---ゲーム理論入門
20
プレイヤ－１の期待利得と
最適応答
●先の食事問題で混合戦略
ナッシュ均衡を求めてみる
と、（ｐ＝２/３、ｑ＝１/３）が
混合ナッシュ戦略となる。
2015/10/1
0.3
0.7
0.7
0.7
0.7
0.7
0.7
0.6
0.6
0.6
0.6
0.6
0.4
0.6
0.6
0.6
0.7
0.7
0.7
0.7
0.7
0.8
0.8
0.8
0.5
0.5
0.6
0.6
0.7
0.7
0.8
0.8
0.9
0.9
1
1
0.6
0.4
0.5
0.6
0.6
0.7
0.8
0.9
1
1
1.1
1.2
0.7
0.3
0.4
0.5
0.6
0.7
0.9
1
1.1
1.2
1.3
1.4
0.8
0.2
0.3
0.5
0.6
0.8
0.9
1
1.2
1.3
1.5
1.6
0.9
0.1
0.3
0.4
0.6
0.8
1
1.1
1.3
1.5
1.6
1.8
1.0
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
2
1.5
ｖ１
1
0.5
0
情報と戦略---ゲーム理論入門
S7
0.9
0.2
0.8
0.8
0.7
0.7
0.6
0.6
0.6
0.5
0.5
0.4
0.4
0.6
0.1
0.9
0.8
0.8
0.7
0.6
0.6
0.5
0.4
0.3
0.3
0.2
0.3
ｑ
0.0
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
V1
ｐ
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
プレイヤー１の期待利得
ｑ
0
ｐ
21
プレイヤー２の期待利得と
最適応答
●先の食事問題で混合戦略
ナッシュ均衡を求めてみる
と、（ｐ＝２/３、ｑ＝１/３）が
混合ナッシュ戦略となる。
2015/10/1
0.5
1
1.1
1.1
1.2
1.2
1.3
1.3
1.4
1.4
1.5
1.5
0.6
0.8
0.9
1
1
1.1
1.2
1.3
1.4
1.4
1.5
1.6
0.7
0.6
0.7
0.8
0.9
1
1.2
1.3
1.4
1.5
1.6
1.7
0.8
0.4
0.5
0.7
0.8
1
1.1
1.2
1.4
1.5
1.7
1.8
0.9
0.2
0.4
0.5
0.7
0.9
1.1
1.2
1.4
1.6
1.7
1.9
1.0
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
ｖ１
1
0.5
0
S7
1
0.4
1.2
1.2
1.2
1.3
1.3
1.3
1.3
1.3
1.4
1.4
1.4
0.8
0.3
1.4
1.4
1.4
1.4
1.4
1.4
1.3
1.3
1.3
1.3
1.3
0.6
0.2
1.6
1.6
1.5
1.5
1.4
1.4
1.4
1.3
1.3
1.2
1.2
0.4
0.1
1.8
1.7
1.7
1.6
1.5
1.5
1.4
1.3
1.2
1.2
1.1
1.5
0.2
ｑ
0.0
2
1.9
1.8
1.7
1.6
1.5
1.4
1.3
1.2
1.1
1
2
0
ｖ２
ｐ
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
プレイヤー２の期待利得
ｑ
0
ｐ
ナッシュ均衡は各プレイヤーの最適応答
のグラフの交点である。
情報と戦略---ゲーム理論入門
22
相関均衡の例
●再び食事問題を考えよう。ただし今回は
両者が同じ１枚のコイン投げの結果を観
察できるものと仮定する。
●両者とも（オモテ→ピザ、ウラ→うどん）ま
たは（オモテ→うどん、ウラ→ピザ）という
情報に依存した戦略を用いれば、双方と
も２回に１回は好物を食べられる。→均衡
利得は両者ともに１を得る。
●これを相関均衡(Correlated Equilibrium)と
いう。なおプレイヤーが観察する信号は
別々でも互いに相関関係が分かっていれ
ば良い。→共通知識の価値
2015/10/1
情報と戦略---ゲーム理論入門
相関均衡を考案した
R. J. オーマン
（Aumann）は、またプ
レイヤーの共通知識
(Common
knowledge)や合理性
の仮定がナッシュ均
衡を正当化するかと
いった認識問題を
ゲーム理論の主題と
して形式化した人で
もある。
23
展開形ゲームと不完全情報
● 展開形（Extensive Form)は手番に順序のあ
るゲームをゲームの木（決定木）によって表
現する。
● また展開形はプレイヤーの利用できる不完
全な情報を情報集合によって表せる。
後手の情報
先手の情
集合
報集合
ゲーム木１：不完全情報ゲーム
2015/10/1
情報と戦略---ゲーム理論入門
このゲームにおける後手
の情報集合は一つである。
これは先手の行動を観察
できない（あるいは失念す
る）ことを意味する。さて先
手はどちらを選ぶだろう
か？直観的に言えば、後
手はａを望みたいが、残念
なことに先手の利得は後
手の選択によらずつねにｂ
の方が１だけ上回る。また
後手は先手の選択にかか
わりなくｄの方が１だけよい。
それゆえ支配戦略均衡
（1,1) が存在し、両者とも
望ましい結果(3、3)は実現
されない。注意：このゲー
ムが囚人ジレンマの変形
であることは利得表を書け
24
ば分かる。
展開形ゲーム理論の再生
• 有限ゲームに対しては動的計画法における最適性原理の
考え方を適用できるが、形式化は大変煩雑である。また人
工知能研究を通じて明らかにされたようにチェスや将棋の
ような完全記憶のゲームの均衡戦略は実質的に計算不可
能である。このため展開形ゲーム研究は滞ったが、1965年
にゼルテン（R. Selten)が部分ゲーム完全均衡（SPE；
Subgame-Perfect Equilibrium）や摂動完全均衡を導入して
様相は一変した。ハーサニー（Harsanyi)の不完備情報の完
備化技法と共に、さまざまなナッシュ均衡概念の精緻化
(refinement)のさきがけとなり、またゲーム論の応用分野を
飛躍的に広がるきっかけとなった。
2015/10/1
情報と戦略---ゲーム理論入門
25
ナッシュ均衡の洗練
● ナッシュ均衡が複数あるときは、どれが実際にプレーするのか
それだけでは決定できない。そこで良くない均衡を排除する方
法がさまざまな研究者によって提案された。これをナッシュ均衡
の洗練（Ｒｅｆｉｎｅｍｅｎｔ）という。
●部分ゲーム完全均衡（Selten，1965）
●完全ベイズ均衡（Selten-Harsanyi）
●逐次均衡（Kreps & Wiｌson，1982）
●完全均衡（摂動均衡）（Selten, 1975）
●固有均衡（Myerson，1978）
●他：反復支配、進化的安定性、リスク支配など．
● なお合理化可能性、相関均衡はナッシュ均衡の数を減らさない。
2015/10/1
情報と戦略---ゲーム理論入門
26
部分ゲーム完全均衡
● 部分ゲーム完全均衡（SPE)とは、その任意の均衡戦略の部分
が対応する部分ゲームでのナッシュ均衡となる場合を言う。
● 展開形ゲームにおける部分ゲームの構造から、標準形では明
らかでないナッシュ均衡の不完全性が明らかになる。
● 例えば下図のゲームには (a,d)と(b,c)の２つのNE戦略組がある
が、このうち (a,d)は不完全である。
＞
ゲーム木３：新規参入を阻止できるか？
2015/10/1
情報と戦略---ゲーム理論入門
シュタッケルベル
ク均衡は、クー
ルノの場合と同
様に２つの寡占
企業による交代
手番の生産量調
整ゲームにおけ
る部分ゲーム完
全均衡である。
27
信憑性のある脅し
● 均衡戦略(a,d)を仮定しよう。万が一参入bが起きたならば、後手の情報集合
から再開される部分ゲームにおいて、もはや対抗aは後手の最適反応では
ない。それゆえ先手は対抗策を信用できない脅しとみなし参入する。 一方
(b,c)を仮定すると、これに反して参入が起きなかったとしても後手は行動を
変えない。以上から(1,-1) のみが部分ゲーム完全均衡である。
● しかし利得ベクトルを少し変えてやって下図のようなゲームにすれば、先手
の参入を阻止する「信憑性のある脅し」を部分ゲーム完全均衡において実
現できる。
＜
ゲーム木４：信憑性のある脅し（強い独占企業のケース）
2015/10/1
情報と戦略---ゲーム理論入門
28
＞
ムカデゲームと評判
● 下図に示されたムカデゲームから容易に類推できるように、弱い独占企業は
参入阻止ゲーム（ゲーム２）を有限回繰り返しても、対抗による参入を抑止しえ
ない。→ チェーンストア・パラドックス
● ところが独占企業が強い（ないし
＞
非合理的）タイプである僅かな可
能性を考慮すると、独占企業は
参入を一定の期間阻止できる評
判(Reputation）を維持する。
＞
＞
＞
＞
＞
＞
＞
＞
2015/10/1
＞
チェーンストア・パラドックスを駆逐
したKrepsらの評判モデルは、 プレ
イヤーの合理的な行動だけでなく、
それをベイズの定理に従って予想
した信念の整合性を同時に考慮す
る逐次均衡（Sequential
equilibrium)を用いている。
ゲーム木５：Rosentahlのムカデ
情報と戦略---ゲーム理論入門
29
後方帰納と交渉
先手の申し出
ｘ万円
後手の申し出
ｙ万円
ゲーム木２：逐次交渉ゲーム
仮に反対提案（ｙ）が提示
されたなら、先手は５０万
円のうち１万円をゆずれ
ば受諾される。よって先
手は最初の提案（ｘ）を拒
否されないために、ｘ＞４
９を提示する。またｘ＝５
０を提案すれば、後手は
ｘを超える利得を獲得で
きないから受諾し、この
交渉は最初の提案で成
立し、 SPE＝（５０、５０）
である。
● 完全情報の有限ゲームにおける部分ゲーム完全均衡解（SPE）
は後方帰納（Backward Induction）によって解かれる。
● 以下はRubinsteinによる２人逐次交渉モデル２段階の場合であ
る。１００万円を１割引率５０％、一万円刻みで分配する。 このと
きSPE＝（５０、５０）である。問．割引率２５％のときは？また段
階数３を変えるとSPEどうなるか？
2015/10/1
情報と戦略---ゲーム理論入門
30
整合的な信念と摂動
● 完全ベイズ均衡や逐次均衡では、期待効用
を最大化する行動と、他者の行動についての
ベイズルールに矛盾しない信念（確率的予想）
とを同時に決定する。
●また逐次均衡、完全均衡、固有均衡に共通す
るテクニックである摂動（Trembling Hand)とは、
小さな非合理性の確率を導入することである。
それによって均衡では起こり得ない（それゆえ
ベイズルールが直接適用できない）行動パ
ターンに対する信念に制約を加える。
2015/10/1
情報と戦略---ゲーム理論入門
31
入学許可ゲーム
● ある学校では学力考査をせずに申し込みした受験生をそ
の場で面接して入学許可させるか否かを決める。受験生の
タイプは「優れている（E)」と「並み（A)」の２つであり、
●本人は自分がどちらのタイプであるか知っているが、
●学校側が知っているのはその人口比率がｐということだ
けで、
●学校は個人のタイプについては入学するまで分からない
ものとする。
2015/10/1
情報と戦略---ゲーム理論入門
32
PBE：
完全
ベイズ
均衡
●
学校の戦略： 例えばもし「優れている」者だけが申し込むという戦略が取ら
れているなら、 「申し込みあり」の下で「優れている」の条件付確率は１だから、
ただちに入学許可すれば良い。それ以外の場合は、各タイプの申し込み戦略
を条件付確率ｑE、ｑAで表すと、学校は受験生がタイプEであるという信念をベ
イズルールｐ‘＝ｐｑE/（ｐｑE＋（１‐ｐ）ｑA）に矛盾せずに更新する。
● 完全ベイズ均衡（PBE)は、ｐが小さいとき、いずれのタイプも申し込まない、入
学許可しないというもの。ただしｐ≧0.6なら両タイプとも申し込み、平均ｐの割合
でEタイプを入学させることができる。
2015/10/1
情報と戦略---ゲーム理論入門
33
2
ピザ
2 ,2
2.01 , 0
うどん
＜２
0 , 2.01
＜１
ピザ
うどん
＜１
繰り返しゲームと
フォーク定理
1
＜２
0.1 , 0.1
表２．囚人ジレンマ型ゲーム
● 囚人ジレンマ・ゲーム（表２）が繰り返しプレイされる状況を考えよう。有限
期の繰り返しなら、全期非協力が唯一の部分ゲーム完全均衡であるという
事実は、多くの人の直観に反するのではないか。しかしもし任意のｋ≧２期
以前で１度でも協調が成立していたら？
● 無限期の繰り返し囚人ジレンマでは、様相は一変する。無限期繰り返し
ゲームG=(ｇ,ｇ,…）はそのステージ・ゲームｇをある標準形や展開形のゲー
ムとして無限回繰り返す。適切な共通の割引率δの下でプレイヤーの平均
利得（の極限値）を求め、それによって部分ゲーム完全均衡戦略を吟味す
る。
● （フォーク定理） 裏切りに対してつねに最悪のペナルティ（永久懲罰）で対
応する戦略やその引き金となる任意の戦略がいずれもGのナッシュ戦略に
なることを利用すれば、δが１に近いとき、ほぼ任意の望ましい利得ベクト
ルを実現できる。
2015/10/1
情報と戦略---ゲーム理論入門
34
有限 IPDに協調を！
2
1
ピザ
うどん
おでん
＜１
＜１
● 有限期の繰り返し囚人ジレンマ（有
＜２
2
,
2
0 , 2.01
0
, 0
限 IPD)では毎期の裏切りが唯一
ピザ
の部分ゲーム完全均衡であるが、
これはステージゲームに裏切り均
2.01 , 0
0.1 , 0.1
0
, 0
衡しかないためである。
＜２
うどん
● それゆえ次のように利得表を修正
0 ,0
0 ,0
0
, 0
すれば、依然として協力解自体は
≦２
おでん
ステージゲームのナッシュ均衡で
はないものの、繰り返しゲームの部
表３．修正された囚人ジレンマ型ゲーム
分ゲーム完全均衡において（最終
期以外の）協調を達成できる。
裏切り
裏切り
協力
● すなわち両者にとって劣った戦略
協力
裏切り
を加えてナッシュ均衡を作り、ぺナ
ルティに利用するのである。（中山、
協力
pp.89‐90）
≦１
2015/10/1
情報と戦略---ゲーム理論入門
35
図.しっぺ返し（TFT)をプレイするオートマトン
日常の社会文脈と信頼（エッセー）
●
●
●
●
●
●
協力の発生は、単なるエラーなのか？日常的な感覚から類推できるように、社会とは
「しがらみ」や「もちつもたれつ」の長期的関係の延長にあり、協力的な状況あるいは非
協力的（競争的）な状況が、いずれもフェアな関係として成立しているように、 、あるい
は一部はアンフェアだがしかしそのように各メンバーによって認識されていると、共通
認識されている状況のことである。
社会とは、つまりゲームフォーム自体が、一定の信頼度でもって共通認識として醸成さ
れている状況のことである。したがって顔を見知らぬ人々にまで社会の範囲を広げる
ためには、法律のように明確なルールが必要になる。むしろそれらのケースでは経済
学的な意味では裏切りの動機が潜在することを含意しているものの、何等かの情報伝
達のしくみと違反に対する強制力の存在でもって防がれているから、安心していられる。
これはゲーム理論におけるフォーク定理のアナロジーと考えることもできる。違反の検
証と違反者に対する社会的ペナルティは、共同の利益を一種の会員特権として守るた
めの制度的しくみとして不可欠なのだと。しかしそれはゲームの状況が、非協力ゲー
ムの状況であるという不安な認識を反映しているともいえるだろう。
現実社会という生きた文脈から切り離された理想的ゲームプレイヤーの数理世界を論
じてきたゲーム理論では、本来の意味でのコミットメント（約束）やコンベンション（とりき
め）の役割は、かならずしもうまく扱われていると思われない。
繰り返すが、協力的な状況あるいは非協力的（競争的）な状況が、いずれもフェアな関
係として成立しているように、 、あるいは一部はアンフェアだがしかしそのように各メン
バーによって認識されていると、共通認識されている状況が、社会なのであり、もし社
会のメンバーが、何らかの意味で合理的にプレイするのだとすれば、そのゲームの状
況を創出する情報伝達やゲーム理解についても含まれているはずである。
そうしたゲームを認識したとき、その下でのプレイヤーとしての各自のふるまいの合理
性を、はじめて考えることになる。ゲームは「とりきめ」であり、かつそれは一種の人工
物であるが、それゆえ自分自身が人工物として振舞う主体として自分自身によって再
認識され、その行動プログラムを変化させることになり、おそらくその変化を受け入れ
るべきかどうかを自問するだろう。
2015/10/1
情報と戦略---ゲーム理論入門
1980年にアクセルロッドが
主催した最初のコン
ピュータ・プログラム・トー
ナメント実験ではTFT
（“Tit For Tat”）がコンスタ
ントによい成績を収めたと
いう。TFTは前回の相手
の戦略を真似る４行のプ
ログラムで「おうむ返し」ま
たは「しっぺ返し」と訳され
る。
36
参考文献
• 鈴木光男. 『新ゲーム理論』. 勁草書房. 1994.
• 中山幹夫. 『はじめてのゲーム理論』. 有斐閣.
1997．
• 武藤滋夫.『ゲーム理論入門』.日経文庫.2001.
• オーマン著．丸山徹・立石寛訳．『ゲーム論の基
礎』．勁草書房．1991．
2015/10/1
情報と戦略---ゲーム理論入門
37
© Copyright 2024 ExpyDoc
