Nash均衡(Nash equilibrium)とは、複数の参加者が戦略を選ぶ状況で、ほかの全員の戦略を固定したとき誰も 1 人だけ戦略を変えて得をしない戦略の組である。判定は、各人が正の確率を置く純粋戦略の利得が等しく最大であることを確かめればよく、2 人のゲームの均衡は、その条件の連立 1 次方程式を解いて求める。有限のゲームには混合戦略の均衡が必ずあり、最適反応の対応に角谷の不動点定理を当てて示される。2 人ゼロ和ゲームでは最適戦略の組と一致し、潜在ゲームには純粋戦略の均衡がある。
Nash均衡(Nash equilibrium)は、複数の参加者がそれぞれ戦略を選ぶ状況で、ほかの全員の戦略を固定したとき、どの参加者も自分 1 人だけ戦略を変えて得をすることができない 戦略の組である。
たとえば 2 人が待ち合わせの場所を A か B から選ぶ。同じ場所を選べば 2 人とも得をし、参加者 1 は A を、参加者 2 は B をより好むとする(ex-ne-battle の男女の争い)。2 人とも A を選ぶ組と、2 人とも B を選ぶ組は Nash 均衡である。どちらかが 1 人で場所を変えると会えなくなるからである。さらに、確率的に場所を選ぶ均衡がもう 1 つある。
この記事は、与えられた利得の表から Nash 均衡を 計算する ことを中心に、次のことを扱う。
有限の戦略形ゲーム は、$N\ge1$ 人の 参加者 $i=1,\dots,N$、各参加者の空でない有限集合 $S_i$(純粋戦略 の集合)、関数 $u_i\colon S:=S_1\times\cdots\times S_N\to\mathbb R$(利得)からなる。
参加者 $i$ の 混合戦略 とは $S_i$ の上の確率分布 $\sigma_i$ であり、その全体を $\Delta_i$ と書く。$\sigma_i(s)>0$ となる $s\in S_i$ の集合を $\sigma_i$ の 台 という。$\Delta:=\Delta_1\times\cdots\times\Delta_N$ の元 $\sigma$ を 戦略の組 という。各参加者が独立に戦略を選ぶときの期待利得を
$$
U_i(\sigma):=\sum_{s\in S}u_i(s)\prod_{j=1}^N\sigma_j(s_j)
$$
とする。$\sigma$ の第 $i$ 成分を $\tau_i$ に取り替えた組を $(\tau_i,\sigma_{-i})$ と書き、純粋戦略 $s\in S_i$ を、$s$ に確率 $1$ を置く混合戦略と同一視する。
$\sigma\in\Delta$ とする。
2 人のゲームでは、参加者 1 の利得を $m\times n$ 行列 $A$、参加者 2 の利得を行列 $B$ で表す。混合戦略を確率ベクトル $x,y$ で書くと $U_1=x^{\mathsf T}Ay$、$U_2=x^{\mathsf T}By$ である。表の各欄には $(a_{ij},b_{ij})$ を書く。
この記事の結果が使える条件は次のとおりである。
(i) 有限性:人数も各人の純粋戦略も有限である。無限の場合については反例の節を見よ。
(ii) 同時に独立に選ぶ:各参加者は相手の選択を知らずに選び、混合戦略の乱数は参加者ごとに独立である。
(iii) 期待利得で比べる:参加者は期待利得 $U_i$ の大小だけで戦略を比べる。
| 問い | 答え | 条件 | 根拠 |
|---|---|---|---|
| $\sigma$ は均衡か | 台の純粋戦略の利得がすべて、その人の純粋戦略の利得の最大値に等しい | 有限 | prop-ne-support |
| 均衡はあるか | 混合戦略の均衡が必ずある | 有限 | thm-ne-existence |
| 対称なゲームでは | 全員が同じ戦略をとる均衡がある | 有限、対称 | thm-ne-symmetric |
| $2\times2$ の完全に混合した均衡 | $p=\dfrac{b_{22}-b_{21}}{b_{11}-b_{12}-b_{21}+b_{22}}$、$q=\dfrac{a_{22}-a_{12}}{a_{11}-a_{12}-a_{21}+a_{22}}$ | 分母が $0$ でなく $0< p,q<1$ | prop-ne-two-by-two |
| 2 人ゼロ和 | 均衡は最適戦略の組と一致し、利得は値 $V$ | $B=-A$ | prop-ne-zero-sum |
| 潜在関数があるとき | 最大点が純粋均衡。改善の手順が止まる | 有限 | prop-ne-potential |
| 消してよい戦略 | 狭義に支配された純粋戦略 | 有限 | prop-ne-dominated |
次の判定法は KP17 Lemma 4.3.7(p. 84)のものである。混合戦略の期待利得は純粋戦略の期待利得の平均である。$v_i(s):=U_i(s,\sigma_{-i})$($s\in S_i$)とおくと
$$
U_i(\tau_i,\sigma_{-i})=\sum_{s\in S_i}\tau_i(s)\,v_i(s)\qquad\text{(1)}
$$
である。$v_i(s)$ は $\sigma_i$ によらない。
$\sigma\in\Delta$ とし、$m_i:=\max_{s\in S_i}v_i(s)$ とおく。$\tau_i$ が $\sigma_{-i}$ への最適反応であることは、$\tau_i$ の台が $\{s\in S_i\mid v_i(s)=m_i\}$ に含まれることと同値である。したがって次は同値である。
純粋戦略の組 $s$ が均衡であることは、prop-ne-support から、各 $i$ とすべての $t\in S_i$ で $u_i(t,s_{-i})\le u_i(s)$ であることと同値である。
判定に使う「台の上で利得が等しい」という条件は、自分の 利得の等式である。その等式を成り立たせるのは 相手の 確率なので、混合戦略の均衡では、各人の確率は相手を無差別にするように決まる。$2\times2$ の場合はこれがそのまま公式になる。
$2\times2$ のゲームで、参加者 1 が第 1 行を確率 $p$ で、参加者 2 が第 1 列を確率 $q$ で選ぶとする。$0< p<1$、$0< q<1$ の組 $(p,q)$ が Nash 均衡であることは、次の 2 式と同値である。
$$
p(b_{11}-b_{12})+(1-p)(b_{21}-b_{22})=0,\qquad q(a_{11}-a_{21})+(1-q)(a_{12}-a_{22})=0
$$
分母が $0$ でなければ、これを解いて公式の表の $p,q$ を得る。
台はともに全体なので、prop-ne-support の条件は、参加者 2 の 2 列の利得が等しいこと $pb_{11}+(1-p)b_{21}=pb_{12}+(1-p)b_{22}$ と、参加者 1 の 2 行の利得が等しいこと $qa_{11}+(1-q)a_{12}=qa_{21}+(1-q)a_{22}$ である。移項すると 2 式になる。$\square$
有限の戦略形ゲームには、Nash 均衡が少なくとも 1 つある。
これは KP17 Theorem 4.3.6(p. 84)である。$\Delta$ の点 $\sigma$ に最適反応の組の集合を対応させ、その不動点をとる。最適反応は 1 つとは限らないので、写像ではなく集合値の対応になり、角谷の不動点定理 を使う。
$\Delta_i$ は $\mathbb R^{S_i}$ の標準単体で、$\Delta$ は有限次元の空でないコンパクト凸集合である。$\sigma\in\Delta$ に対し、$\sigma_{-i}$ への最適反応の全体を $R_i(\sigma)$ とし、$\Phi(\sigma):=R_1(\sigma)\times\cdots\times R_N(\sigma)\subset\Delta$ とおく。
$\Phi(\sigma)$ は空でなく凸である。実際 prop-ne-support により、$R_i(\sigma)$ は台が空でない集合 $\{s\mid v_i(s)=m_i\}$ に含まれる確率分布の全体である。
$\Phi$ のグラフは閉じている。$\sigma^k\to\sigma$、$\rho^k\in\Phi(\sigma^k)$、$\rho^k\to\rho$ とする。$\rho_i(s)>0$ なら、十分大きい $k$ で $\rho_i^k(s)>0$ なので、prop-ne-support から $U_i(s,\sigma^k_{-i})=\max_{t}U_i(t,\sigma^k_{-i})$ である。$U_i$ は連続なので、極限で $U_i(s,\sigma_{-i})=\max_tU_i(t,\sigma_{-i})$ となる。よって $\rho\in\Phi(\sigma)$ である。
角谷の不動点定理 により $\sigma^*\in\Phi(\sigma^*)$ となる $\sigma^*$ がある。これは、すべての $i$ で $\sigma^*_i$ が $\sigma^*_{-i}$ への最適反応であること、つまり $\sigma^*$ が Nash 均衡であることにほかならない。$\square$
集合値の対応を使わず、1 点を値とする連続写像と Brouwerの不動点定理 で示すこともできる(KP17 Theorem 5.1.1、pp. 99–100)。
要点:得をする純粋戦略の確率を増やす連続写像 $T$ を作ると、不動点では得をする純粋戦略がない。
$\sigma\in\Delta$ と $s\in S_i$ に対し $g_{i,s}(\sigma):=\max\{0,\ U_i(s,\sigma_{-i})-U_i(\sigma)\}$、$G_i(\sigma):=\sum_{s\in S_i}g_{i,s}(\sigma)$ とおき、$T(\sigma)_i(s):=\dfrac{\sigma_i(s)+g_{i,s}(\sigma)}{1+G_i(\sigma)}$ と定める。$T\colon\Delta\to\Delta$ は連続で $\Delta$ は空でないコンパクト凸集合なので、Schauderの不動点定理 の命題「コンパクト凸集合での Brouwer の定理」により不動点 $\sigma$ がある。
各 $i$ を固定する。(1) から $U_i(\sigma)$ は $\sigma_i$ の台の上の $U_i(s,\sigma_{-i})$ の平均なので、台の中に $U_i(s,\sigma_{-i})\le U_i(\sigma)$ となる $s$ がある。この $s$ で $g_{i,s}(\sigma)=0$ なので、不動点の式は $\sigma_i(s)=\sigma_i(s)/(1+G_i(\sigma))$ となる。$\sigma_i(s)>0$ なので $G_i(\sigma)=0$ である。よってすべての $s$ で $U_i(s,\sigma_{-i})\le U_i(\sigma)$ であり、(1) から $\sigma_i$ は最適反応である。$\square$
対称なゲーム とは、全員の純粋戦略の集合が同じ集合 $S_0$ で、ほかの全員が混合戦略 $x$ をとるときに $s\in S_0$ を選ぶ人の利得 $v(s;x)$ が、参加者によらないゲームである(KP17 Definition 4.3.10、p. 85)。
有限の対称なゲームには、全員が同じ混合戦略をとる Nash 均衡がある。
$S_0$ の上の確率分布の全体 $\Delta_0$ の点 $x$ に、$v(\cdot\,;x)$ を最大にする純粋戦略の上の確率分布の全体 $\Psi(x)\subset\Delta_0$ を対応させる。prf-ne-existence と同じ議論で、$\Psi(x)$ は空でなく凸で、$\Psi$ のグラフは閉じている。不動点 $x\in\Psi(x)$ をとると、全員が $x$ をとる組は prop-ne-support の条件を満たす。$\square$
$B=-A$ のゲームを 2 人ゼロ和ゲーム という。von Neumann のミニマックス定理により
$$
V:=\max_x\min_yx^{\mathsf T}Ay=\min_y\max_xx^{\mathsf T}Ay
$$
である(線形計画法 の定理「最小最大定理」、角谷の不動点定理 の系「行列ゲームのミニマックス定理」)。$V$ を 値 という。$\min_yx^{\mathsf T}Ay=V$ となる $x$ と、$\max_xx^{\mathsf T}Ay=V$ となる $y$ を 最適戦略 という。
2 人ゼロ和ゲームで、$(x^*,y^*)$ が Nash 均衡であることは、$x^*,y^*$ がともに最適戦略であることと同値である。このとき $(x^*)^{\mathsf T}Ay^*=V$ である。とくに、均衡の組 $(x,y)$、$(x',y')$ があれば $(x,y')$、$(x',y)$ も均衡で、利得はすべて $V$ である。
$U(x,y):=x^{\mathsf T}Ay$、$U^*:=U(x^*,y^*)$ とする。
$(x^*,y^*)$ が均衡なら、すべての $x,y$ で $U(x,y^*)\le U^*\le U(x^*,y)$ なので、
$$
V\le\max_xU(x,y^*)\le U^*\le\min_yU(x^*,y)\le V
$$
である。よって等号が成り立ち、$x^*,y^*$ は最適戦略で $U^*=V$ である。
逆に $x^*,y^*$ が最適戦略なら、$V=\min_yU(x^*,y)\le U^*\le\max_xU(x,y^*)=V$ なので $U^*=V$ で、すべての $x,y$ で $U(x,y^*)\le V=U^*\le U(x^*,y)$ となる。これは均衡の条件である。
最適戦略の条件は $x$ と $y$ について別々の条件なので、最後の主張が従う。$\square$
一般のゲームには純粋均衡があるとは限らない(ex-ne-counterexamples)。次のゲームには必ずある(KP17 §4.4.1、Claim 4.4.3、Proposition 4.4.6、p. 87)。
有限のゲームに関数 $P\colon S\to\mathbb R$ があって、すべての $i$、$s_i,t_i\in S_i$、$s_{-i}$ について
$$
P(t_i,s_{-i})-P(s_i,s_{-i})=u_i(t_i,s_{-i})-u_i(s_i,s_{-i})
$$
が成り立つとき、$P$ を 潜在関数、このゲームを 潜在ゲーム という。
潜在ゲームでは、$P$ の最大点は純粋 Nash 均衡である。さらに、1 人ずつ利得が真に増える純粋戦略に変える手順は、有限回で純粋 Nash 均衡で止まる。
$s$ が $P$ の最大点なら、定義の左辺は $0$ 以下なので、誰も 1 人で利得を増やせない。手順の各段で $P$ は同じ量だけ真に増える。$S$ は有限なので同じ組に戻らず、手順は止まる。止まった組では誰も利得を増やせない。$\square$
代表例は 混雑ゲーム である。資源(道路)$r$ を $n$ 人が使うと 1 人あたり費用 $c_r(n)$ がかかり、各参加者 $i$ は資源の集合(経路)$A_i$ を選択肢の中から選び、$\sum_{r\in A_i}c_r(n_r)$ を支払う($n_r$ は $r$ を使う人数)。利得は費用の符号を変えたものである。このとき
$$
P(A_1,\dots,A_N):=-\sum_r\sum_{\ell=1}^{n_r}c_r(\ell)
$$
は潜在関数である(KP17 Example 4.4.1、Corollary 4.4.2、pp. 85–86)。実際、$i$ が経路を $A$ から $A'$ に変えると、$A\setminus A'$ の資源の項から $c_r(n_r)$ が消え、$A'\setminus A$ の資源の項に $c_r(n_r+1)$ が加わる。これは $i$ の費用の変化そのものである。潜在ゲーム(ポテンシャルゲーム)であるための判定と、逆にどの潜在ゲームも混雑ゲームとして実現できることは ポテンシャルゲーム で扱う。
純粋戦略 $s\in S_i$ が 狭義に支配される とは、$\tau_i(s)=0$ である混合戦略 $\tau_i$ があって、すべての $s_{-i}$ で $U_i(\tau_i,s_{-i})>u_i(s,s_{-i})$ となることをいう。
$s\in S_i$ が狭義に支配されるとする。どの Nash 均衡でも $\sigma_i(s)=0$ である。さらに、$s$ を $S_i$ から除いたゲームの Nash 均衡と、もとのゲームの Nash 均衡は一致する。
任意の $\sigma$ について、支配の不等式を $\sigma_{-i}$ で平均すると $U_i(\tau_i,\sigma_{-i})>v_i(s)$ である。よって (1) から、$\tau_i$ の台の中に $v_i(t)>v_i(s)$ となる $t\ne s$ があり、$s$ は最適反応の台に入らない。prop-ne-support から $\sigma_i(s)=0$ である。
$\sigma$ が $s$ を除いたゲームの均衡であるとする。もとのゲームで見ると、$i$ 以外の参加者の純粋戦略の利得は変わらない。$i$ については、今示したとおり $v_i(s)<\max_{t\ne s}v_i(t)$ なので、prop-ne-support の条件は保たれる。逆に、もとのゲームの均衡は $s$ を使わないので、$s$ を除いたゲームの均衡である。$\square$
有限のゲームの均衡をすべて求める標準の手順は次のとおりである。
| 場合 | 方法 | 手間の目安 |
|---|---|---|
| 一般の 2 人ゲーム | 手順 3〜5 を全部の組で行う | 台の組は $(2^m-1)(2^n-1)$ 通りで、指数関数的(KP17 Exercise 4.12、p. 96) |
| 2 人ゼロ和ゲーム | 線形計画を解く(線形計画法) | 線形計画の手間。均衡は 1 組求まれば値が分かる |
| 潜在ゲーム | 改善の手順を回す(prop-ne-potential) | 回数は $P$ の値の個数以下 |
| 3 人以上 | 手順 4 の等式の係数に相手の確率の積が入る | 台の組ごとに多項式の連立方程式を解く |
2 人が待ち合わせの場所 A, B を選ぶ。利得の表は次のとおりである。
| 参加者 2 が A | 参加者 2 が B | |
|---|---|---|
| 参加者 1 が A | $(2,1)$ | $(0,0)$ |
| 参加者 1 が B | $(0,0)$ | $(1,2)$ |
手順 2 により、(A, A) と (B, B) が純粋均衡である。完全に混合した均衡は、公式の表から
$$
p=\frac{2-0}{1-0-0+2}=\frac23,\qquad q=\frac{1-0}{2-0-0+1}=\frac13
$$
で、利得は 2 人とも $2q=\frac23$ である。どちらの純粋均衡よりも、2 人とも利得が小さい。
参加者 1 にとって A の利得は $2q$、B の利得は $1-q$ なので、A が最適なのは $q\ge\frac13$ のときである。参加者 2 にとって A の利得は $p$、B の利得は $2(1-p)$ なので、A が最適なのは $p\ge\frac23$ のときである。最適反応のグラフを描くと、次の図のように 3 点で交わる。
横軸を参加者 1 が A を選ぶ確率 p、縦軸を参加者 2 が A を選ぶ確率 q とした単位正方形。参加者 1 の最適反応は q=1/3 で段差をもつ折れ線、参加者 2 の最適反応は p=2/3 で段差をもつ折れ線で、2 本は (0,0)、(1,1)、(2/3,1/3) の 3 点で交わる。
交点が均衡である。thm-ne-existence の証明の $\Phi$ の不動点は、この交点にあたる。
グー・パー・チョキの 2 人ゼロ和ゲームの $A$ は
$$
A=\begin{pmatrix}0&-1&1\\1&0&-1\\-1&1&0\end{pmatrix}
$$
である(行と列の順はグー・パー・チョキ)。$u:=(\frac13,\frac13,\frac13)$ について $u^{\mathsf T}A=0$、$Au=0$ なので、$V=0$ である。$x$ が最適戦略なら $x^{\mathsf T}A$ の成分はすべて $0$ 以上で、その和は $0$ なので、$x_2-x_3=x_3-x_1=x_1-x_2=0$ である。よって $x=u$ である。$y$ も同様である。prop-ne-zero-sum により、均衡は $(u,u)$ だけである。純粋均衡はない。
利得の行列を
$$
A=\begin{pmatrix}3&0&1\\1&2&0\\0&1&4\end{pmatrix},\qquad B=\begin{pmatrix}2&1&0\\0&3&1\\1&0&2\end{pmatrix}
$$
とする。$a_{ij}$ の列の中の最大と $b_{ij}$ の行の中の最大が重なるのは対角成分なので、純粋均衡は 3 つある。どの純粋戦略も純粋均衡に現れるので、prop-ne-dominated により、狭義に支配された戦略はない。
台 $I=J=\{1,2\}$ の場合を手順どおり解く。行 1, 2 の利得が等しい条件は $3y_1=y_1+2y_2$ で、$y_1+y_2=1$ と合わせて $y=(\frac12,\frac12,0)$、値は $\frac32$ である。行 3 の利得は $y_2=\frac12\le\frac32$ である。列 1, 2 の利得が等しい条件は $2x_1=x_1+3x_2$ で、$x=(\frac34,\frac14,0)$、値は $\frac32$ である。列 3 の利得は $x_2=\frac14\le\frac32$ である。よってこの組は均衡である。
全部の台の組を調べると、均衡は次の 7 個である。
| $x$ | $y$ | $U_1$ | $U_2$ |
|---|---|---|---|
| $(1,0,0)$ | $(1,0,0)$ | $3$ | $2$ |
| $(0,1,0)$ | $(0,1,0)$ | $2$ | $3$ |
| $(0,0,1)$ | $(0,0,1)$ | $4$ | $2$ |
| $(\frac34,\frac14,0)$ | $(\frac12,\frac12,0)$ | $\frac32$ | $\frac32$ |
| $(\frac13,0,\frac23)$ | $(\frac12,0,\frac12)$ | $2$ | $\frac43$ |
| $(0,\frac12,\frac12)$ | $(0,\frac45,\frac15)$ | $\frac85$ | $\frac32$ |
| $(\frac13,\frac14,\frac5{12})$ | $(\frac7{20},\frac9{20},\frac15)$ | $\frac54$ | $\frac{13}{12}$ |
6 人が 2 本の道路のどちらかを選ぶ。道路 1 を $n$ 人が使うと 1 人あたりの費用は $n$、道路 2 の費用は人数によらず 1 人あたり $4$ である。
道路 1 の人が道路 2 へ移って得をするのは $n>4$ のとき、道路 2 の人が道路 1 へ移って得をするのは $n+1<4$ のときなので、純粋均衡は $n=3,4$ である。潜在関数の符号を変えた $-P=\frac{n(n+1)}2+4(6-n)$ と、全員の費用の和 $n^2+4(6-n)$ は次のとおりである。
| $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|---|
| $-P$ | $24$ | $21$ | $19$ | $18$ | $18$ | $19$ | $21$ |
| 費用の和 | $24$ | $21$ | $20$ | $21$ | $24$ | $29$ | $36$ |
$-P$ の最小点が均衡である。費用の和が最小の $n=2$ は均衡でない。道路 2 の人が 1 人で道路 1 へ移ると、自分の費用が $4$ から $3$ に下がるからである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 混合戦略を許すこと | コイン合わせ | 純粋戦略だけでは均衡がない |
| 純粋戦略が有限であること | 大きい数を言うゲーム | 混合戦略を許しても均衡がない |
| 利得の連続性(戦略の集合はコンパクト) | $S=[0,1]$ の 1 人のゲーム | 最適反応がなく、均衡がない |
| 潜在関数があること | コイン合わせ | 純粋均衡がなく、改善の手順が止まらない |
| ゼロ和であること | 男女の争い | 均衡の成分を組み替えると均衡でなくなる |
コイン合わせ:$A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$、$B=-A$ とする。純粋戦略の組のどれでも、負けた側が戦略を変えると得をする。改善の手順はこの 4 つの組を回り続ける。混合戦略の均衡は $p=q=\frac12$ である(角谷の不動点定理 の例「コイン合わせ」)。
大きい数を言うゲーム:2 人が自然数を 1 つずつ言い、大きい数を言った人が $1$ を得て相手が $1$ を失い、同じ数なら利得は $0$ とする。混合戦略は自然数の上の確率分布である。参加者 2 の混合戦略 $y$ に対し、参加者 1 が $n$ を言う利得は $y(\{m< n\})-y(\{m>n\})$ で、$n\to\infty$ のとき $1$ に近づく。よって $(x,y)$ が均衡なら $U_1(x,y)\ge1$ であり、同様に $U_2(x,y)\ge1$ である。これは $U_1+U_2=0$ に反する。
$S=[0,1]$ の 1 人のゲーム:$x<1$ で $u(x)=x$、$u(1)=0$ とする。$[0,1]$ の上のどの確率分布の期待利得も $1$ より小さく、$x<1$ を $1$ に近くとった純粋戦略の方が利得が大きい。よって最適反応はない。
男女の争い:ex-ne-battle の (A, A) と (B, B) は均衡だが、成分を組み替えた (A, B) は均衡でない。2 つの均衡の利得も異なる。prop-ne-zero-sum の結論はゼロ和でないゲームでは成り立たない。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 均衡は全員にとって最善の結果である | 均衡は 1 人の変更に対する安定性で、効率とは別である | ex-ne-congestion の均衡の費用の和は $21$ 以上で、最小値は $20$ |
| 自分の確率は自分の利得から決まる | 均衡の確率は相手を無差別にするように決まる | prop-ne-two-by-two の $p$ は $B$ だけで決まる |
| 台の上の等式だけを確かめる | 台の外の不等式も確かめる | prop-ne-support の条件 2 |
| 弱く支配された戦略も消してよい | 均衡を失うことがある | $a_{11}=b_{11}=1$、ほかの成分が $0$ の $2\times2$ のゲームの第 2 行・第 2 列の組は均衡だが、第 2 行は第 1 行に弱く支配される |
| 純粋均衡がないなら均衡はない | 有限なら混合戦略の均衡がある | thm-ne-existence、ex-ne-rps |
| 2 人ゼロ和ゲームの性質を一般のゲームに使う | 成分の組み替えや値の一意性はゼロ和でないと成り立たない | ex-ne-counterexamples |
Nash 均衡の概念と thm-ne-existence は J. F. Nash の 1950 年の論文による(KP17 第 4 章の注、p. 93)。Nash は学位論文で Brouwer の不動点定理を使い、論文では角谷の不動点定理を使った(KP17 第 5 章の注、p. 112)。
均衡の定義は、均衡が複数あるときにどれが選ばれるかを決めない。また、実際に均衡を実現するには、参加者が利得の構造を知っていることや、均衡を求められることが要る(KP17 第 4 章の注、p. 93)。存在定理は不動点定理による証明で、均衡を効率よく求める方法は与えない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する