Nash均衡

同義語:ナッシュ均衡Nash equilibrium

概要

Nash均衡(Nash equilibrium)とは、複数の参加者が戦略を選ぶ状況で、ほかの全員の戦略を固定したとき誰も 1 人だけ戦略を変えて得をしない戦略の組である。判定は、各人が正の確率を置く純粋戦略の利得が等しく最大であることを確かめればよく、2 人のゲームの均衡は、その条件の連立 1 次方程式を解いて求める。有限のゲームには混合戦略の均衡が必ずあり、最適反応の対応に角谷の不動点定理を当てて示される。2 人ゼロ和ゲームでは最適戦略の組と一致し、潜在ゲームには純粋戦略の均衡がある。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: ゲーム理論, 角谷の不動点定理

Nash均衡(Nash equilibrium)は、複数の参加者がそれぞれ戦略を選ぶ状況で、ほかの全員の戦略を固定したとき、どの参加者も自分 1 人だけ戦略を変えて得をすることができない 戦略の組である。
たとえば 2 人が待ち合わせの場所を A か B から選ぶ。同じ場所を選べば 2 人とも得をし、参加者 1 は A を、参加者 2 は B をより好むとする(ex-ne-battle の男女の争い)。2 人とも A を選ぶ組と、2 人とも B を選ぶ組は Nash 均衡である。どちらかが 1 人で場所を変えると会えなくなるからである。さらに、確率的に場所を選ぶ均衡がもう 1 つある。
この記事は、与えられた利得の表から Nash 均衡を 計算する ことを中心に、次のことを扱う。

  • ある戦略の組が均衡であるかは、有限個の利得の比較で判定できる(prop-ne-support)。
  • 有限のゲームには、混合戦略まで許せば必ず均衡がある(thm-ne-existence)。
  • 2 人のゲームの均衡は、台(正の確率を置く戦略の集合)を決めて連立 1 次方程式を解いて求める(節「計算の手順」)。
  • 2 人ゼロ和ゲームでは均衡は最適戦略の組と一致し(prop-ne-zero-sum)、潜在関数をもつゲームには純粋戦略の均衡がある(prop-ne-potential)。
    ゲーム理論の全体の案内は ゲーム理論 にある。存在定理の鍵になる不動点定理は 角谷の不動点定理 で証明している。

定義と使える条件

戦略形ゲーム

有限の戦略形ゲーム は、$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$ を置く混合戦略と同一視する。

Nash 均衡

$\sigma\in\Delta$ とする。

  1. $\tau_i\in\Delta_i$ が $\sigma_{-i}$ への 最適反応 であるとは、すべての $\tau_i'\in\Delta_i$ について $U_i(\tau_i,\sigma_{-i})\ge U_i(\tau_i',\sigma_{-i})$ となることをいう。
  2. すべての $i$ について $\sigma_i$ が $\sigma_{-i}$ への最適反応であるとき、$\sigma$ を Nash 均衡 という。
  3. すべての $\sigma_i$ が純粋戦略である Nash 均衡を 純粋 Nash 均衡 という。

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\}$ に含まれることと同値である。したがって次は同値である。

  1. $\sigma$ は Nash 均衡である。
  2. 各 $i$ について定数 $c_i$ があって、$\sigma_i$ の台の上で $v_i(s)=c_i$、台の外で $v_i(s)\le c_i$ である。
平均は最大値以下
  1. の右辺は $v_i(s)$ の重み付き平均なので $m_i$ 以下であり、$\tau_i$ を $v_i(s)=m_i$ となる純粋戦略にとれば $m_i$ に等しい。よって $U_i(\cdot,\sigma_{-i})$ の最大値は $m_i$ である。また $\sum_s\tau_i(s)(m_i-v_i(s))=0$ で各項は $0$ 以上なので、$U_i(\tau_i,\sigma_{-i})=m_i$ は、$\tau_i(s)>0$ なら $v_i(s)=m_i$ であることと同値である。
    2 の条件は $c_i=m_i$ として、$\sigma_i$ の台が $v_i=m_i$ の集合に含まれることと同じである。$\square$

純粋戦略の組 $s$ が均衡であることは、prop-ne-support から、各 $i$ とすべての $t\in S_i$ で $u_i(t,s_{-i})\le u_i(s)$ であることと同値である。
判定に使う「台の上で利得が等しい」という条件は、自分の 利得の等式である。その等式を成り立たせるのは 相手の 確率なので、混合戦略の均衡では、各人の確率は相手を無差別にするように決まる。$2\times2$ の場合はこれがそのまま公式になる。

$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 の存在定理

有限の戦略形ゲームには、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)。

Brouwer の不動点定理で示す

要点:得をする純粋戦略の確率を増やす連続写像 $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$

特別な形のゲーム

2 人ゼロ和ゲーム

$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 人ゼロ和ゲームの均衡

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 均衡で止まる。

手順の各段で $P$ が増える

$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$

計算の手順

有限のゲームの均衡をすべて求める標準の手順は次のとおりである。

  1. 支配された戦略を消す:狭義に支配された純粋戦略を、消せなくなるまで消す(prop-ne-dominated)。
  2. 純粋均衡を探す:表の各欄について、$a_{ij}$ が列 $j$ の中で最大で、$b_{ij}$ が行 $i$ の中で最大かを調べる(参加者 1 は相手の列を固定して行を選び、参加者 2 は相手の行を固定して列を選ぶ)。
  3. 台を決める:2 人のゲームなら、$I\subset\{1,\dots,m\}$、$J\subset\{1,\dots,n\}$ の組を 1 つ選ぶ。
  4. 連立 1 次方程式を解く:$\sum_{j\in J}y_j=1$ と、$i\in I$ について $\sum_{j\in J}a_{ij}y_j$ がすべて等しいことを解く。同様に $x$ を $B$ の列の等式から解く。
  5. 不等式を確かめる:$x_i>0$($i\in I$)、$y_j>0$($j\in J$)と、台の外の行・列の利得が台の上の値以下であること(prop-ne-support の条件 2)を確かめる。
    場合方法手間の目安
    一般の 2 人ゲーム手順 3〜5 を全部の組で行う台の組は $(2^m-1)(2^n-1)$ 通りで、指数関数的(KP17 Exercise 4.12、p. 96)
    2 人ゼロ和ゲーム線形計画を解く(線形計画法)線形計画の手間。均衡は 1 組求まれば値が分かる
    潜在ゲーム改善の手順を回す(prop-ne-potential)回数は $P$ の値の個数以下
    3 人以上手順 4 の等式の係数に相手の確率の積が入る台の組ごとに多項式の連立方程式を解く
    一般の 2 人ゲームの均衡を求める問題は PPAD 完全である(CDT09。ゲーム理論 を参照)。この記事では証明しない。

例題

男女の争い

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 点で交わる。 横軸を参加者 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)$ だけである。純粋均衡はない。

$3\times3$ のゲームの全部の均衡

利得の行列を
$$ 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)。存在定理は不動点定理による証明で、均衡を効率よく求める方法は与えない。

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, 著者公開版(2016 年 12 月 13 日)の番号:Theorem 4.3.6・Lemma 4.3.7(p. 84)、Definition 4.3.10(p. 85)、Example 4.4.1・Corollary 4.4.2(pp. 85–86)、§4.4.1・Claim 4.4.3・Proposition 4.4.6(p. 87)、第 4 章の注(p. 93)、Exercise 4.12(p. 96)、Theorem 5.1.1(pp. 99–100)、第 5 章の注(p. 112)
[2]
Xi Chen, Xiaotie Deng, Shang-Hua Teng, Settling the complexity of computing two-player Nash equilibria, Journal of the ACM 56 (2009), no. 3, Article 14; arXiv:0704.1678, 2009

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する