部分ゲーム完全均衡(subgame perfect equilibrium)とは、手番が順に回る展開形ゲームの戦略の組で、どの途中の局面から始めた残りのゲーム(部分ゲーム)でも Nash 均衡になっているものである。実際には通らない局面での不合理な脅しを含む Nash 均衡を除く。完全情報の有限ゲームでは、各局面で 1 手だけ変える逸脱で得をしないことと同値で(一段逸脱原理)、終局から逆にたどる後ろ向き帰納法で純粋戦略のものが必ず得られ、各参加者の利得に同点がなければ一意である。
部分ゲーム完全均衡(subgame perfect equilibrium)は、手番が順に回るゲーム(展開形ゲーム)の戦略の組で、ゲームのどの途中の局面から始めた残りのゲーム(部分ゲーム)でも Nash 均衡になっているものである。Selten が 1965 年に定式化した(KP17 p. 134 の注)。
Nash均衡 は、実際に通る道筋の上での最適性しか求めない。通らない局面での行動は、どれほど不合理でも Nash 均衡の条件に引っかからない。たとえば「参入してきたら、自分が損をしてでも値下げ競争で報復する」という脅しは、実際には参入が起きないので試されず、それを含む戦略の組が Nash 均衡になりうる(ex-spe-entry)。部分ゲーム完全均衡は、すべての局面で最適な行動を求めることで、このような実行されない脅し(空脅し)を除く。
この記事では、完全情報の有限な展開形ゲームについて次のことを示す。
$k\ge1$ とする。完全情報の $k$ 人有限展開形ゲーム $\Gamma$ は次のものからなる(KP17 Definition 6.1.2、p. 115)。
$\Gamma$ を def-spe-game のゲームとする。
$v=r$ のとき $\Gamma_r=\Gamma$ なので、部分ゲーム完全均衡は Nash 均衡である。逆は成り立たない。違いは、$s$ に従ったとき通らない局面 $v$ での条件にある。
この記事の結果が使える条件は次のとおりである。
(i) 木が有限:局面が有限個である。とくに各局面の手は有限個で、どの道筋も有限の長さで終局に着く。
(ii) 完全情報:手を選ぶ参加者は、自分がどの局面にいるかを知っている。偶然の手番(くじ)を含む場合は、利得を期待値に替えれば同じ議論が通るが、この記事では扱わない。
(iii) 純粋戦略:完全情報の有限ゲームでは純粋戦略の部分ゲーム完全均衡が必ずある(thm-spe-backward)ので、混合戦略は扱わない。
| 問い | 答え | 条件 | 根拠 |
|---|---|---|---|
| 判定 | 各局面で 1 手だけ変える逸脱で得をしない | (i)(ii) | thm-spe-one-shot |
| 存在 | 純粋戦略の部分ゲーム完全均衡がある | (i)(ii) | thm-spe-backward |
| 求め方 | 終局から逆にたどり、各局面で手番の参加者の利得が最大の子を選ぶ | (i)(ii) | thm-spe-backward |
| 一意性 | 各参加者の利得が終局ごとに相異なれば一意 | (i)(ii) | thm-spe-backward の 3 |
| Nash 均衡との関係 | 部分ゲーム完全均衡は Nash 均衡。逆は不成立 | — | ex-spe-entry |
| 計算量 | 局面の数に比例する回数の比較で求まる | (i)(ii) | thm-spe-backward の証明 |
局面 $v$ の 高さ $h(v)$ を、$v$ から終局までの道筋の辺の数の最大値とする。終局の高さは $0$ で、$v\in X$ なら $h(v)=1+\max_{c\in C(v)}h(c)$ である。以下の証明はすべて高さについての帰納法である。
$s$ と局面 $v\in X$ と $c\in C(v)$ に対し、$j=\iota(v)$ の戦略 $s_j$ の $v$ での値だけを $c$ に替えた戦略を $s_j^{v\to c}$ と書く。$v$ から $s_j^{v\to c}$ と $s_{-j}$ に従って進むと、最初の手で $c$ へ行き、その後は $s$ に従うので
$$
U_j(s_j^{v\to c},s_{-j}\mid v)=U_j(s\mid c)
$$
である(以下、この等式を「一段逸脱の等式」と呼ぶ)。この 1 手だけの変更を $v$ での 一段逸脱 という。
$\Gamma$ を def-spe-game のゲーム、$s$ を純粋戦略の組とする。次は同値である。
条件 2 は一段逸脱の等式により、「どの局面でも、手番の参加者は一段逸脱で得をしない」ことである。調べる組の数は $\sum_{v\in X}\lvert C(v)\rvert$ で、これは木の辺の数、すなわち局面の数より 1 少ない。一方、条件 1 を定義どおりに調べると、各部分ゲームで参加者の純粋戦略をすべて比べることになる。純粋戦略の数は、その参加者の局面ごとの手の数の積で、一般にはるかに多い。
1 ⇒ 2。 $s$ が部分ゲーム完全均衡なら、$v$ で $s_j^{v\to c}$ に替えても得をしないので、一段逸脱の等式より $U_j(s\mid c)=U_j(s_j^{v\to c},s_{-j}\mid v)\le U_j(s\mid v)=U_j(s\mid s(v))$ である。最後の等号は、$v$ から $s$ に従うと最初に $s(v)$ へ進むことによる。
2 ⇒ 1。 条件 2 を仮定し、次の主張 $P(n)$ をすべての $n\ge1$ について示す。
$P(n)$:$h(v)\le n$ のすべての $v\in X$、すべての $i$、$i$ のすべての純粋戦略 $s_i'$ について $U_i(s_i',s_{-i}\mid v)\le U_i(s\mid v)$。
これがすべての $n$ で成り立てば、$s$ は部分ゲーム完全均衡である。
$n\ge1$ とし、$h(c)< n$ の $c\in X$ については主張が成り立つと仮定する($n=1$ ではこの仮定は空である)。終局 $c\in Z$ では $U_i(s_i',s_{-i}\mid c)=u_i(c)=U_i(s\mid c)$ なので、$h(c)< n$ のすべての局面 $c$ で不等式が成り立つ。$h(v)=n$ の $v\in X$ をとり、$j=\iota(v)$、$c^\ast=s(v)$ とおく。$v$ の子の高さはどれも $n$ より小さい。
$\Gamma$ を def-spe-game のゲームとする。
1 の存在の部分は KP17 Theorem 6.1.7(p. 118)の主張で、そこでは証明が演習(Exercise 6.a)に回されている。有限の完全情報ゲームに純粋戦略の均衡、実は部分ゲーム完全均衡があることの証明は、Zermelo(Zer13)と Kuhn(Kuh53)に帰せられる(KP17 p. 134 の注)。
1。 高さについての帰納法で $U(s^\ast\mid v)=W(v)$ を示す。終局では定義どおりである。$v\in X$ で子について成り立てば、$v$ から $s^\ast$ に従うと $s^\ast(v)$ へ進むので $U(s^\ast\mid v)=U(s^\ast\mid s^\ast(v))=W(s^\ast(v))=W(v)$ である。
次に、$v\in X$、$j=\iota(v)$、$c\in C(v)$ とすると、$s^\ast(v)$ の選び方から
$$
U_j(s^\ast\mid c)=W_j(c)\le W_j(s^\ast(v))=U_j(s^\ast\mid s^\ast(v))
$$
である。これは thm-spe-one-shot の条件 2 なので、$s^\ast$ は部分ゲーム完全均衡である。
2。 $s$ を部分ゲーム完全均衡とし、$W(v):=U(s\mid v)$ とおく。thm-spe-one-shot の条件 2 より、各 $v\in X$ で $s(v)$ は $j=\iota(v)$ の値 $W_j(c)=U_j(s\mid c)$ を最大にする子の 1 つであり、$W(v)=U(s\mid s(v))=W(s(v))$ である。よって $s$ は、1 の手順で各局面の選択を $s(v)$ にとったものと一致する。
3。 1 の手順で $W(c)$ は終局 $z_{s^\ast}(c)$ の利得 $u(z_{s^\ast}(c))$ であり、異なる子 $c\ne c'$ の部分木は交わらないので、$z_{s^\ast}(c)\ne z_{s^\ast}(c')$ である。$u_j$ が単射なら $W_j(c)\ne W_j(c')$ となり、最大の子はただ 1 つに決まる。よって 1 の手順の選び方は 1 通りで、2 より部分ゲーム完全均衡は 1 つである。$\square$
1 の手順は、各局面で子の値を 1 回ずつ比べるだけなので、比べる回数は $\sum_{v\in X}\lvert C(v)\rvert=\lvert V\rvert-1$($V$ は局面全体)である。ただし、チェスのように局面の数が膨大なゲームでは、この手順を実際に実行することはできない。
2 人ゼロ和の場合には、$W_1(v)$ は局面 $v$ からの値で、後ろ向き帰納法は値の再帰計算になる。勝ち・負け・引き分けの 3 つの結果をもつゲームでの帰結は Zermeloの定理(ゲーム理論) で扱う。
参加者 1(参入者)がまず「参入しない」か「参入する」を選ぶ。参入しなければ利得は $(0,2)$ である(左が参加者 1)。参入すると、参加者 2(既存の企業)が「報復する」か「受け入れる」を選び、利得はそれぞれ $(-1,-1)$、$(1,1)$ である。
Nash 均衡:純粋戦略の組は 4 つで、Nash 均衡は(参入する、受け入れる)と(参入しない、報復する)の 2 つである。後者では、参加者 1 が参入すると $-1<0$ なので参入せず、参加者 2 の手番は実際には来ないので、報復も受け入れも利得 $2$ で同じである。
部分ゲーム完全均衡:参加者 2 の局面を根とする部分ゲームでは、受け入れる($1>-1$)が唯一の最適な手である。これを見越して参加者 1 は参入する($1>0$)。部分ゲーム完全均衡は(参入する、受け入れる)だけである。利得 $u_1$ の値 $0,-1,1$ も $u_2$ の値 $2,-1,1$ も相異なるので、thm-spe-backward の 3 と合う。
(参入しない、報復する)の「報復する」は、実行すれば自分も損をする脅しで、部分ゲームの Nash 均衡になっていない。同じ形の例が KP17 Example 6.1.4(p. 116)にある。
参加者 1 が、2 単位のうち $x\in\{0,1,2\}$ 単位を参加者 2 に渡す提案をし、参加者 2 は各 $x$ について受け入れるか拒むかを決める。受け入れれば利得は $(2-x,x)$、拒めば $(0,0)$ である。参加者 2 の純粋戦略は $\{0,1,2\}$ から {受ける, 拒む} への写像で、8 個ある。
一段逸脱原理で調べる。$x=1,2$ の局面では受け入れる方が真に得なので、部分ゲーム完全均衡では受け入れる。$x=0$ の局面では受けても拒んでも $0$ で、どちらでもよい。
$n\ge2$ とする。段 $t=1,\dots,n$ で、$t$ が奇数なら参加者 1、偶数なら参加者 2 が「取る」か「回す」を選ぶ。段 $t$ で取ると、取った人の利得が $t+1$、相手の利得が $t-1$ で終わる。段 $n$ でも回すと、両者の利得が $n$ で終わる。
部分ゲーム完全均衡:段 $n$ では、取る($n+1$)が回す($n$)より真に得である。段 $t< n$ では、後の段で相手が必ず取るなら、回すと相手が段 $t+1$ で取って自分の利得は $(t+1)-1=t$ になり、取る($t+1$)が真に得である。どの段の比較も等号がないので、thm-spe-backward の 2 より、部分ゲーム完全均衡は「全員がどの段でも取る」ただ 1 つで、利得は $(2,0)$ である。全員が回し続ければ両者とも $n$ を得るのにである。
Nash 均衡の結果も同じ:純粋戦略の Nash 均衡 $s$ の道筋が段 $t'\ge2$ の「取る」で終わるとする。段 $t'-1$ で回した人は $t'-1$ を得るが、その段で取るように変えれば $t'$ を得るので、$s$ は Nash 均衡でない。道筋が全員回して終わる場合も、段 $n$ の手番の人は取れば $n+1>n$ を得る。よって Nash 均衡の道筋は段 1 で取って終わる。Nash 均衡と部分ゲーム完全均衡の違いは、道筋の外の段での行動だけである。
賞金が 1 段ごとに 1 ドル増える 96 段のムカデゲームが KP17 Example 6.1.6(p. 116)にある。
同時に手を選ぶゲームや、相手の手を見ずに選ぶゲームでは、参加者は自分がどの局面にいるかを知らない。これを、各参加者の局面を 情報集合 に分け、同じ情報集合の局面では同じ手の集合から同じ手を選ぶ、と定めて表す(KP17 Definition 6.2.2、p. 120)。このときの部分ゲームは、1 点だけの情報集合の局面を根とし、どの情報集合も分けない部分木に限る(同 p. 120)。部分ゲーム完全均衡の定義は def-spe-main の 5 と同じで、戦略は情報集合ごとの確率分布(行動戦略)にとる。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 手が有限個((i) のうち分岐の有限性) | 1 人のゲームで、根の手が $n=1,2,\dots$、手 $n$ の利得 $1-\frac1n$ | 部分ゲーム完全均衡の存在(thm-spe-backward の 1) |
| 道筋の長さが有限((i) のうち深さの有限性) | 1 人のゲームで、段 $t=1,2,\dots$ ごとに止めるか続けるかを選び、段 $t$ で止めると $1-\frac1t$、止めなければ $0$ | 部分ゲーム完全均衡の存在 |
| 道筋の長さが有限 | 1 人のゲームで、各段で止めるか続けるかを選び、止めると $0$、止めなければ $1$ | 一段逸脱原理の「2 ⇒ 1」(thm-spe-one-shot) |
| 完全情報((ii)) | 参加者 1 が表か裏を選び、参加者 2 はそれを見ずに表か裏を選ぶ。一致なら $(1,-1)$、不一致なら $(-1,1)$ | 純粋戦略の部分ゲーム完全均衡の存在 |
| 利得に同点がない | ex-spe-ultimatum | 部分ゲーム完全均衡の一意性(thm-spe-backward の 3) |
確かめを順に書く。
1 行目:どの純粋戦略 $n$ も、$n+1$ に変えれば利得が増えるので、Nash 均衡がなく、部分ゲーム完全均衡もない。木は高さ 1 で、手の数だけが無限である。
2 行目:各局面の手は 2 つで、木は無限に深い。段 $t$ で止める戦略は、段 $t$ で続けて段 $t+1$ で止める戦略に負ける($1-\frac1t<1-\frac1{t+1}$)。決して止めない戦略(利得 $0$)は、段 2 で止める戦略(利得 $\frac12$)に負ける。よって最適な戦略がなく、部分ゲーム完全均衡はない。
3 行目:「どの段でも止める」戦略を $s$ とする。どの段 $t$ で 1 手だけ続けるに変えても、次の段で $s$ に従って止めるので利得は $0$ のままで、一段逸脱では得をしない。しかし「決して止めない」戦略は利得 $1$ を得るので、$s$ は部分ゲーム完全均衡でない。2 ⇒ 1 の証明は高さについての帰納法で、高さが定まらない木では使えない。
4 行目:部分ゲームはゲーム全体だけである。純粋戦略の組 4 つのどれでも、負けている側が手を替えると勝つので、純粋戦略の Nash 均衡がない。混合戦略では、両者が確率 $\frac12$ ずつ選ぶ組が部分ゲーム完全均衡である。
5 行目:ex-spe-ultimatum で、部分ゲーム完全均衡が 2 つあり利得も異なる。
| 誤り | 正しくは | なぜ |
|---|---|---|
| Nash 均衡なら部分ゲーム完全均衡である | 道筋の外の局面でも最適かを調べる | ex-spe-entry |
| 部分ゲーム完全均衡は利得が一意 | 同点があれば均衡も利得も複数ありうる | ex-spe-ultimatum |
| 部分ゲーム完全均衡は全員にとって望ましい結果を与える | 全員が損をする結果になりうる | ex-spe-centipede |
| 一段逸脱を調べれば、どんなゲームでも足りる | 有限の木では足りる。無限に長いゲームでは利得の連続性などの条件が要る | 反例の表の 3 行目 |
| 部分ゲームとは任意の局面から先の部分木である | 不完全情報では情報集合を分けない部分木に限る | 節「不完全情報のゲームへ」 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する