完全均衡(ゲーム理論)(trembling-hand perfect equilibrium)とは、有限の戦略形ゲームで、各参加者がすべての純粋戦略に正の下限以上の確率を置くよう制限した摂動ゲームの均衡の、下限を 0 に近づけた極限として得られる Nash 均衡である。完全に混合した戦略の組の列への最適反応の極限と言い換えられ、どの有限ゲームにも存在する。完全均衡では弱く支配された戦略は使われず、2 人のゲームでは逆に、弱く支配されない戦略からなる Nash 均衡はすべて完全均衡であるが、3 人以上ではこの逆は成り立たない。
前提知識: Nash均衡, 線形計画法, Bolzano–Weierstrassの定理
完全均衡(trembling-hand perfect equilibrium、摂動完全均衡)は、各参加者が意図した戦略をとろうとしても、ごく小さな確率で手が震えて別の純粋戦略を選んでしまう、という状況でも崩れない Nash均衡 である。正確には、すべての純粋戦略に正の確率を置くように制限した「摂動ゲーム」の均衡の、制限を $0$ に近づけたときの極限として定める(KP17 p. 94 の注)。Selten が 1975 年に導入した(Sel75)。展開形ゲームの 部分ゲーム完全均衡 とは別の概念である。
Nash 均衡は、相手が均衡の戦略を 正確に とるときの最適性しか求めない。たとえば次の $2\times2$ のゲーム(左が参加者 1 の利得)では、(B, R) も Nash 均衡である。
| L | R | |
|---|---|---|
| T | $(1,1)$ | $(0,0)$ |
| B | $(0,0)$ | $(0,0)$ |
相手が R を確実に選ぶなら、T と B はどちらも利得 $0$ で差がない。しかし相手が少しでも L を選ぶ可能性があれば T が真に得で、B を選ぶ理由はない。完全均衡はこのような均衡を除く。
この記事では、有限の戦略形ゲームについて次のことを示す。
記号は Nash均衡 の定義「戦略形ゲーム」に従う。参加者は $i=1,\dots,N$、純粋戦略の有限集合は $S_i$、混合戦略の全体は $\Delta_i$、$\Delta:=\Delta_1\times\cdots\times\Delta_N$、期待利得は $U_i$ である。すべての $s\in S_i$ で $\sigma_i(s)>0$ となる $\sigma_i$ を 完全に混合した 戦略という。
$\sigma_i,\tau_i\in\Delta_i$ とする。$i$ 以外の参加者の純粋戦略のすべての組 $s_{-i}$ について $U_i(\tau_i,s_{-i})\ge U_i(\sigma_i,s_{-i})$ で、少なくとも 1 つの $s_{-i}$ で狭義の不等号が成り立つとき、$\sigma_i$ は $\tau_i$ に 弱く支配される という。どの $\tau_i$ にも弱く支配されない $\sigma_i$ を 支配されない 戦略という。
Nash均衡 の節「支配された戦略」の狭義の支配とは違い、弱く支配された戦略が Nash 均衡で使われることはある。冒頭の例の B は T に弱く支配される。
この記事の結果が使える条件は次のとおりである。
(i) 有限:人数と純粋戦略の数は有限である。
(ii) 震えは完全に混合し、参加者ごとに独立:摂動ゲームでは各参加者がすべての純粋戦略に正の確率を置き、確率は参加者ごとに独立に選ばれる。
(iii) 2 人:thm-pe-two の「支配されない Nash 均衡は完全」の向きだけに使う。
| 問い | 答え | 条件 | 根拠 |
|---|---|---|---|
| 言い換え | 完全に混合した組の列 $\sigma^k\to\sigma$ で、$\sigma_i$ が $\sigma^k_{-i}$ への最適反応 | (i)(ii) | thm-pe-char |
| Nash 均衡との関係 | 完全均衡は Nash 均衡。逆は不成立 | (i)(ii) | thm-pe-char、冒頭の例 |
| 存在 | どの有限ゲームにもある | (i)(ii) | thm-pe-existence |
| 弱い支配 | 完全均衡の戦略は支配されない | (i)(ii) | thm-pe-undominated |
| 2 人の場合 | 完全均衡 ⇔ 支配されない戦略の Nash 均衡 | (i)(ii)(iii) | thm-pe-two |
| 3 人以上 | 支配されない Nash 均衡でも完全とは限らない | (i)(ii) | ex-pe-three |
$\sigma\in\Delta$ と $s\in S_i$ について $v_i(s):=U_i(s,\sigma_{-i})$ とおく。$U_i(\tau_i,\sigma_{-i})=\sum_s\tau_i(s)v_i(s)$ である(Nash均衡 の (1))。
$\sigma\in\Delta(\eta)$ が $G(\eta)$ の均衡であることは、次と同値である:すべての $i$ と $s\in S_i$ について、$v_i(s)< \max_{t\in S_i}v_i(t)$ なら $\sigma_i(s)=\eta_i(s)$。
$\tau_i\in\Delta_i(\eta_i)$ を $\tau_i=\eta_i+\rho_i$ と書くと、$\rho_i\ge0$、$\sum_s\rho_i(s)=1-\sum_s\eta_i(s)=:c_i>0$ で、逆にこの形の $\rho_i$ はすべて現れる。
$$
U_i(\tau_i,\sigma_{-i})=\sum_s\eta_i(s)v_i(s)+\sum_s\rho_i(s)v_i(s)
$$
の第 1 項は $\tau_i$ によらず、第 2 項は $c_i\max_tv_i(t)$ 以下で、等号は $\rho_i$ が $v_i$ の最大点の上にだけ正の値をもつときに限る。よって $\sigma_i$ が最大を与えることは、$v_i(s)$ が最大でない $s$ で $\sigma_i(s)-\eta_i(s)=0$ となることと同値である。$\square$
$\sigma\in\Delta$ について次は同値である。
1 ⇒ 2。 $\eta^k\to0$、$G(\eta^k)$ の均衡 $\sigma^k\to\sigma$ とする。$\sigma^k_i(s)\ge\eta^k_i(s)>0$ なので $\sigma^k$ は完全に混合している。$\sigma_i(s)>0$ とすると、十分大きい $k$ で $\sigma^k_i(s)>\sigma_i(s)/2>\eta^k_i(s)$ となるので、lem-pe-perturbed から $s$ は $\sigma^k_{-i}$ への純粋最適反応である。$S_i$ は有限なので、ある $k_0$ 以降では、$\sigma_i$ の台のすべての $s$ がそうなる。Nash均衡 の命題「台による判定」から、$\sigma_i$ は $\sigma^k_{-i}$ への最適反応である。列を $k\ge k_0$ に取り直せばよい。
2 ⇒ 1。 $\sigma^k$ を 2 の列とする。$\sigma_i(s)=0$ なら $\eta^k_i(s):=\sigma^k_i(s)$、$\sigma_i(s)>0$ なら $\eta^k_i(s):=\varepsilon_k$ とおく。ここで $\varepsilon_k>0$、$\varepsilon_k\to0$ である。$\sigma^k\to\sigma$ なので、十分大きい $k$ では、$\sigma_i(s)>0$ のとき $\sigma^k_i(s)\ge\varepsilon_k$、また $\sum_s\eta^k_i(s)< 1$ である。$k$ をそのように取り直すと、$\eta^k$ は震えの下限で $\eta^k\to0$、$\sigma^k\in\Delta(\eta^k)$ である。
$\sigma^k$ が $G(\eta^k)$ の均衡であることを lem-pe-perturbed で確かめる。$s$ が $\sigma^k_{-i}$ への純粋最適反応でないとする。$\sigma_i$ は $\sigma^k_{-i}$ への最適反応なので、台による判定から $\sigma_i(s)=0$ であり、定義から $\sigma^k_i(s)=\eta^k_i(s)$ である。よって $\sigma$ は完全均衡である。
Nash 均衡であること。 2 の列について、$\sigma_i$ と任意の $\tau_i$ で $U_i(\sigma_i,\sigma^k_{-i})\ge U_i(\tau_i,\sigma^k_{-i})$ であり、$U_i$ は連続なので $k\to\infty$ で $U_i(\sigma)\ge U_i(\tau_i,\sigma_{-i})$ を得る。$\square$
有限の戦略形ゲームには完全均衡がある。
摂動ゲームの均衡の存在。 震えの下限 $\eta$ を固定し、$c_i:=1-\sum_s\eta_i(s)>0$ とおく。$\tau_i\in\Delta_i$ に $\phi_i(\tau_i):=\eta_i+c_i\tau_i\in\Delta_i(\eta_i)$ を対応させると、$\phi_i$ は $\Delta_i$ から $\Delta_i(\eta_i)$ への全単射で、各成分について 1 次式である。純粋戦略の集合を同じ $S_i$ とし、純粋戦略の組 $t$ に利得 $u'_i(t):=U_i(\phi(t))$ を与える有限ゲーム $G'$ を作る($t_j$ を $t_j$ に確率 $1$ を置く混合戦略とみる)。
$G'$ の期待利得 $U'_i(\tau)$ と $U_i(\phi(\tau))$ は、どちらも各 $\tau_j$ について(ほかを固定して)1 次式であり、純粋戦略の組で値が一致する。各 $\tau_j=\sum_t\tau_j(t)\,t$ を 1 つずつ展開すると、そのような関数は純粋戦略の組での値で決まるので、$U'_i(\tau)=U_i(\phi(\tau))$ である。
Nash均衡 の定理「Nash の存在定理」により $G'$ には均衡 $\tau^\ast$ がある。$\phi_i$ が全単射なので、$\tau^\ast_i$ が $U'_i(\cdot,\tau^\ast_{-i})$ を $\Delta_i$ で最大にすることは、$\phi_i(\tau^\ast_i)$ が $U_i(\cdot,\phi(\tau^\ast)_{-i})$ を $\Delta_i(\eta_i)$ で最大にすることと同じである。よって $\phi(\tau^\ast)$ は $G(\eta)$ の均衡である。
極限をとる。 $\eta^k_i(s):=1/(2k\lvert S_i\rvert)$ とおくと震えの下限で $\eta^k\to0$ である。$G(\eta^k)$ の均衡 $\sigma^k$ をとる。$\Delta$ は有限次元のコンパクト集合なので、Bolzano–Weierstrassの定理 により収束する部分列があり、その極限は定義により完全均衡である。$\square$
$\sigma$ が完全均衡なら、どの $i$ についても $\sigma_i$ は支配されない。
thm-pe-char の列 $\sigma^k$ をとる。$\sigma_i$ が $\tau_i$ に弱く支配されるとすると、$\sigma^k_{-i}$ は完全に混合した戦略の積なので、$i$ 以外の純粋戦略のすべての組 $s_{-i}$ に正の確率を置く。支配の不等式をこの確率で平均すると、狭義の不等号の組の寄与から
$$
U_i(\tau_i,\sigma^k_{-i})>U_i(\sigma_i,\sigma^k_{-i})
$$
となり、$\sigma_i$ が $\sigma^k_{-i}$ への最適反応であることに反する。$\square$
逆向きには、支配されない戦略がある完全に混合した相手の戦略への最適反応であることが要る。2 人なら、これは 1 次不等式系の択一定理から従う。
2 人の有限ゲームで、参加者 1 の $x\in\Delta_1$ が支配されないなら、参加者 2 の完全に混合した戦略 $y$ で、$x$ が $y$ への最適反応となるものがある。参加者 2 についても同じである。
$s\in S_1$、$j\in S_2$ について $D_{sj}:=U_1(s,j)-U_1(x,j)$ とおく。$z\in\mathbb R^{S_2}$ についての 1 次不等式系
$$
-z_j\le-1\ (j\in S_2),\qquad\sum_{j}D_{sj}z_j\le0\ (s\in S_1)
$$
に解があるとする。$y:=z/\sum_jz_j$ は完全に混合しており、すべての $s$ で $U_1(s,y)\le U_1(x,y)$ なので、$x$ は $y$ への最適反応である(台による判定)。
解がないとすると、線形計画法 の定理「1 次不等式系の択一定理」により、$0$ 以上の数 $\mu_j$($j\in S_2$)、$\lambda_s$($s\in S_1$)で
$$
-\mu_j+\sum_s\lambda_sD_{sj}=0\ (j\in S_2),\qquad-\sum_j\mu_j< 0
$$
となるものがある。$\mu\ne0$ なので $\lambda\ne0$ で、$\tau:=\lambda/\sum_s\lambda_s\in\Delta_1$ とおくと
$$
U_1(\tau,j)-U_1(x,j)=\sum_s\tau_sD_{sj}=\frac{\mu_j}{\sum_s\lambda_s}\ge0
$$
がすべての $j$ で成り立ち、$\mu_j>0$ となる $j$ では狭義である。これは $x$ が $\tau$ に弱く支配されることを意味し、仮定に反する。$\square$
2 人の有限ゲームで、$(x,y)$ が完全均衡であることは、$(x,y)$ が Nash 均衡で、$x$ と $y$ がともに支配されないことと同値である。
完全均衡なら Nash 均衡で(thm-pe-char)、$x,y$ は支配されない(thm-pe-undominated)。
逆を示す。lem-pe-farkas により、完全に混合した $y'$ で $x$ がその最適反応となるもの、完全に混合した $x'$ で $y$ がその最適反応となるものがある。$k\ge2$ について
$$
x^k:=(1-\tfrac1k)x+\tfrac1kx',\qquad y^k:=(1-\tfrac1k)y+\tfrac1ky'
$$
とおくと、$x^k,y^k$ は完全に混合し、$(x^k,y^k)\to(x,y)$ である。$U_1(\cdot,y^k)=(1-\frac1k)U_1(\cdot,y)+\frac1kU_1(\cdot,y')$ で、$x$ は $y$ と $y'$ の両方への最適反応なので、$y^k$ への最適反応である。$y$ についても同じである。thm-pe-char から $(x,y)$ は完全均衡である。$\square$
2 人の場合は、相手の純粋戦略の上の 任意の 完全に混合した分布が、相手の 1 つの混合戦略として実現できる。3 人以上では、自分以外の参加者の組の上の分布は、震えが独立なので各人の分布の積に限られる。lem-pe-farkas の証明が与える分布は積とは限らないので、thm-pe-two の逆向きは 3 人以上には広がらない(ex-pe-three)。
2 人のゲームで、与えられた Nash 均衡 $(x,y)$ が完全均衡かを調べるには、thm-pe-two により、$x$ と $y$ が支配されないかを調べればよい。prf-pe-farkas の不等式系は線形計画で解けるので、次の手順になる。
冒頭のゲームの Nash 均衡は (T, L) と (B, R) である($y$ の L の確率が正なら T が真に得で、そのとき L が真に得。$y=$ R なら参加者 1 はどれでも $0$ で、R が最適反応であるのは $x=$ B のとき)。
(B, R) は完全均衡でない。完全に混合したどの $y$ でも $U_1(\mathrm T,y)=y_{\mathrm L}>0=U_1(\mathrm B,y)$ で、B は最適反応でない。あるいは、B が T に弱く支配されるので thm-pe-undominated から直ちに分かる。
(T, L) は完全均衡である。$x^k=y^k=(1-\frac1k,\frac1k)$ とおくと、$U_1(\mathrm T,y^k)=1-\frac1k>0$ で T が最適反応、参加者 2 についても同じなので、thm-pe-char の 2 が成り立つ。
部分ゲーム完全均衡 の例「参入阻止ゲーム」を戦略形で書く。参加者 1 は「参入しない」「参入する」、参加者 2 は「報復する」「受け入れる」を選び、利得は(参入しない、どちらでも)$(0,2)$、(参入する、報復する)$(-1,-1)$、(参入する、受け入れる)$(1,1)$ である。
純粋戦略の Nash 均衡は(参入する、受け入れる)と(参入しない、報復する)で、ほかに、参加者 1 が参入せず、参加者 2 が確率 $\frac12$ 以上で報復する混合の均衡がある(参入の利得 $-q+(1-q)$ が $0$ 以下になる報復の確率 $q$)。報復に正の確率を置く参加者 2 の戦略は、「受け入れる」に弱く支配される(参入しないなら同じ $2$、参入するなら $-q+(1-q)< 1$)。よって thm-pe-two により、完全均衡では参加者 2 は受け入れ、参加者 1 は参入する。完全均衡は(参入する、受け入れる)だけで、部分ゲーム完全均衡と一致する。実行されない脅しは、相手の手の震えで試されるので除かれる。
参加者 1 の純粋戦略を W、Y、Z、参加者 2 と 3 の純粋戦略をそれぞれ L、R、O とする。参加者 2 と 3 の利得はつねに $0$ とする。参加者 1 の利得は、参加者 2 か 3 の少なくとも一方が O を選べば何を選んでも $0$、W を選べばつねに $0$、それ以外は次のとおりとする(参加者 2・参加者 3 の順に書く)。
| (L, L) | (R, R) | (L, R) | (R, L) | |
|---|---|---|---|---|
| Y | $1$ | $1$ | $1$ | $-2$ |
| Z | $1$ | $1$ | $-2$ | $1$ |
(W, O, O) は Nash 均衡で、どの戦略も支配されない。 誰が手を変えても参加者 1 の利得は $0$ のままで、参加者 2・3 の利得はつねに $0$ なので、Nash 均衡である。参加者 2・3 の戦略は利得が一定なので弱く支配されない。参加者 1 の W が $\tau=(\tau_{\mathrm W},b,c)$ に弱く支配されるとすると、(L, R) で $b-2c\ge0$、(R, L) で $c-2b\ge0$ なので $b\ge2c\ge4b$ から $b=c=0$、$\tau=$ W となり、狭義の不等号の組がない。
(W, O, O) は完全均衡でない。 完全に混合した $\sigma^k_2,\sigma^k_3$ をとり、参加者 2・3 が O 以外を選ぶ確率を $\pi_2,\pi_3>0$、そのときに L を選ぶ条件付き確率を $p,q$ とする。震えは独立なので
$$
U_1(\mathrm Y)-U_1(\mathrm W)=\pi_2\pi_3\bigl(1-3(1-p)q\bigr),\qquad U_1(\mathrm Z)-U_1(\mathrm W)=\pi_2\pi_3\bigl(1-3p(1-q)\bigr)
$$
である。両方が $0$ 以下なら $(1-p)q\ge\frac13$ かつ $p(1-q)\ge\frac13$ で、掛けると $p(1-p)\,q(1-q)\ge\frac19$ となるが、左辺は $\frac1{16}$ 以下なので矛盾である。よって Y か Z が W より真に得で、W は最適反応でない。thm-pe-char から完全均衡でない。
参加者 2・3 の選択が相関してよいなら、たとえば (L, R) と (R, L) を $\frac12$ ずつにすると Y と Z の利得はともに $-\frac12$ で、W が最適反応になる。独立な震えではこの分布を作れないことが、2 人の場合との違いである。
Selten の論文(Sel75)は、題のとおり展開形ゲームの均衡点の完全性を扱う。この記事は戦略形ゲームでの定義に限った。展開形の均衡の別の精緻化として、Kreps と Wilson(KW82)の逐次均衡がある。完全均衡と部分ゲーム完全均衡はどちらも Nash 均衡の精緻化で、ex-pe-entry では一致するが、定義は別である。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 震えが完全に混合すること((ii)) | 冒頭のゲームで、震えのない列 $\sigma^k=(\mathrm B,\mathrm R)$ | 極限の戦略が支配されないこと(thm-pe-undominated) |
| 2 人((iii)) | ex-pe-three | 支配されない Nash 均衡が完全均衡であること(thm-pe-two の逆向き) |
| 純粋戦略が有限((i)) | 1 人で、純粋戦略 $n=1,2,\dots$ の利得が $1-\frac1n$ | 完全均衡の存在(thm-pe-existence) |
確かめ:1 行目:thm-pe-char の 2 で「完全に混合した」を外すと、一定の列 $\sigma^k=(\mathrm B,\mathrm R)$ について B は R への最適反応、R は B への最適反応なので条件を満たす。しかし B は T に弱く支配される。
2 行目:ex-pe-three で、(W, O, O) は支配されない Nash 均衡だが完全均衡でない。
3 行目:震えの下限 $\eta$ をどうとっても、prf-pe-perturbed と同じ計算で、下限を超える分 $\rho$ の寄与 $\sum_n\rho(n)(1-\frac1n)$ は、$\rho$ の総量 $c>0$ より真に小さく、$c$ にいくらでも近い。最大を与える $\rho$ がないので摂動ゲーム $G(\eta)$ に均衡がなく、定義から完全均衡もない。
| 誤り | 正しくは | なぜ |
|---|---|---|
| Nash 均衡はどれも完全均衡 | 弱く支配された戦略を使う Nash 均衡は完全でない | ex-pe-two-by-two |
| 支配されない Nash 均衡は完全均衡 | 2 人なら正しいが、3 人以上では成り立たない | ex-pe-three |
| 完全均衡は部分ゲーム完全均衡と同じ | 別の定義の精緻化。例によっては一致する | rem-pe-extensive |
| 完全に混合した組の列のどれか 1 つで最適反応なら完全 | 列の各項で最適反応であることが要る | thm-pe-char |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する