角谷の不動点定理(Kakutani fixed-point theorem)とは、$\mathbb{R}^n$ の空でないコンパクト凸集合 $K$ の各点 $x$ に $K$ の空でない凸部分集合 $\Phi(x)$ を割り当てる対応 $\Phi$ が閉グラフをもつなら、$x\in\Phi(x)$ となる点 $x$ があるという定理である。値が 1 点の場合が Brouwer の不動点定理にあたり、逆に Brouwer の定理から、連続な近似写像の不動点の極限をとって証明できる。有限ゲームで相手の戦略に最適反応の集合を対応させる対応に当てると、混合戦略の Nash 均衡の存在が従い、そこから行列ゲームの von Neumann のミニマックス定理も得られる。
前提知識: Brouwerの不動点定理, 凸集合, コンパクト空間
Brouwerの不動点定理 は、閉球からそれ自身への連続写像が不動点をもつことを述べる。経済学やゲーム理論では、点 $x$ に 1 つの点ではなく点の集合 $\Phi(x)$ が対応する場面が多い。たとえば、相手の戦略 $x$ に対する「最も得をする戦略」は 1 つとは限らない。角谷の不動点定理 は、Brouwer の定理をこのような集合値の写像(対応)へ広げたもので、$\mathbb{R}^n$ の空でないコンパクト凸集合 $K$ の各点 $x$ に $K$ の空でない凸部分集合 $\Phi(x)$ を対応させ、そのグラフが閉集合であれば、$x\in\Phi(x)$ となる点 $x$ があると述べる。
この記事では、対応とそのグラフ、上半連続性を定義し、角谷の不動点定理を Brouwer の定理から証明する。応用として、有限ゲームの混合戦略の Nash 均衡の存在と、行列ゲームの von Neumann のミニマックス定理を導く。最後に、どの仮定を外しても結論が崩れることを反例で確かめる。
この記事を通して、$\lvert\cdot\rvert$ は $\mathbb{R}^n$ の Euclid ノルム、$B(x,r)$ は中心 $x$、半径 $r$ の開球である。$\mathbb{R}^n$ の部分集合がコンパクトであることは、有界閉集合であることと同値であり(コンパクト空間 の定理「有界閉集合とコンパクト性の一致」)、そのときその中の点列は収束する部分列をもつ(Bolzano–Weierstrassの定理)。
$X\subset\mathbb{R}^n$、$Y\subset\mathbb{R}^m$ とする。
写像 $f\colon X\to Y$ は、1 点からなる集合を値とする対応 $x\mapsto\{f(x)\}$ とみなせる。このとき $\Phi$ の不動点は $f(x)=x$ となる点、すなわち $f$ の 不動点 にほかならない。$f$ が連続なら、$(x_k,f(x_k))\to(x,y)$ のとき $y=\lim f(x_k)=f(x)$ なので、グラフは閉集合である。
閉グラフの条件は、点列の言葉で「$x_k\to x$、$y_k\in\Phi(x_k)$、$y_k\to y$ なら $y\in\Phi(x)$」と言い換えられる($X\times Y\subset\mathbb{R}^{n+m}$ の部分集合が閉であることは点列の極限で閉じていることと同値だからである)。とくに各値 $\Phi(x)$ は $Y$ の閉集合である($x_k=x$ とおけばよい)。
連続性に当たる条件として、次の上半連続性も使われる。
$X$ から $Y$ への対応 $\Phi$ が点 $x\in X$ で 上半連続 であるとは、$\Phi(x)\subset V$ を満たす $Y$ の任意の開集合 $V$ に対し $\delta>0$ があって、$x'\in X$、$\lvert x'-x\rvert<\delta$ なら $\Phi(x')\subset V$ となることをいう。すべての点で上半連続なとき、$\Phi$ は上半連続であるという。
点 $x$ の近くの点の値は、$\Phi(x)$ の近くからはみ出さない。値が急に大きくなることは許されないが、急に小さくなることは許される。値域がコンパクトなら、閉グラフの条件は、値が閉集合であることとこの上半連続性を合わせた条件と同じになる。
$X\subset\mathbb{R}^n$ とし、$Y\subset\mathbb{R}^m$ をコンパクト集合とする。$X$ から $Y$ への対応 $\Phi$ について、次は同値である。
1 ⇒ 2:値が閉集合であることは上で見た。$\Phi$ がある点 $x$ で上半連続でないとすると、開集合 $V\supset\Phi(x)$ と点列 $x_k\to x$、$y_k\in\Phi(x_k)\setminus V$ がある。$Y$ はコンパクトなので、部分列に取り替えて $y_k\to y\in Y$ としてよい。$Y\setminus V$ は $Y$ の閉集合なので $y\notin V$ である。一方、閉グラフの条件から $y\in\Phi(x)\subset V$ となり、矛盾する。
2 ⇒ 1:$x_k\to x$、$y_k\in\Phi(x_k)$、$y_k\to y$ とし、$y\notin\Phi(x)$ と仮定する。$\Phi(x)$ は閉集合なので、$r>0$ があって $B(y,2r)$ は $\Phi(x)$ と交わらない。$V:=\{z\in Y\mid \lvert z-w\rvert< r\text{ となる }w\in\Phi(x)\text{ がある}\}$ は $Y$ の開集合で $\Phi(x)$ を含む($\Phi(x)=\emptyset$ なら $V=\emptyset$)。上半連続性から、十分大きい $k$ で $y_k\in\Phi(x_k)\subset V$ となるので、$\lvert y_k-w_k\rvert< r$ となる $w_k\in\Phi(x)$ がある。すると $\lvert y-w_k\rvert\le\lvert y-y_k\rvert+r<2r$ が十分大きい $k$ で成り立ち、$B(y,2r)$ が $\Phi(x)$ と交わらないことに反する。$\square$
値域がコンパクトでないと 1 ⇒ 2 は成り立たない。$X=Y=\mathbb{R}$、$\Phi(0)=\{0\}$、$x\ne0$ で $\Phi(x)=\{0,1/x\}$ とすると、グラフ $\{(x,0)\}\cup\{(x,1/x)\mid x\ne0\}$ は閉集合だが、$V=(-1,1)$ について $0$ の近くの $x\neq0$ の値は $V$ に含まれず、$0$ で上半連続でない。
$K\subset\mathbb{R}^n$ を空でないコンパクト凸集合とし、$\Phi$ を $K$ から $K$ への対応とする。各 $x\in K$ で $\Phi(x)$ が空でない凸集合であり、$\Phi$ が閉グラフをもつなら、$\Phi$ は不動点をもつ。すなわち $x^*\in\Phi(x^*)$ となる $x^*\in K$ がある。
prop-kfp-closed-graph により、閉グラフの仮定は「値が閉集合で $\Phi$ が上半連続」と言い換えてもよい。1 点を値とする対応に当てると、Brouwerの不動点定理 のコンパクト凸集合の形(Schauderの不動点定理 の命題「コンパクト凸集合での Brouwer の定理」)が戻る。逆に、次の証明はその Brouwer の定理だけを使う。
証明の考え方は、対応から連続写像を「選び出して」Brouwer の定理を当てることである。ただし、閉グラフをもつ凸値の対応から、グラフに入る連続写像が選べるとは限らない(ex-kfp-no-selection)。そこで、グラフに近い連続写像を作り、その不動点の極限をとる。
段 1(近似の連続写像):$\varepsilon>0$ とする。開球 $B(x,\varepsilon)$($x\in K$)は $K$ を覆うので、コンパクト性から有限個の点 $x_1,\dots,x_m\in K$ があって $K\subset\bigcup_iB(x_i,\varepsilon)$ となる。各 $i$ について $y_i\in\Phi(x_i)$ を 1 つ選ぶ。
$$
\psi_i(x):=\max\{0,\ \varepsilon-\lvert x-x_i\rvert\},\qquad f_\varepsilon(x):=\frac{\sum_{i=1}^m\psi_i(x)\,y_i}{\sum_{j=1}^m\psi_j(x)}
$$
とおく。各 $\psi_i$ は連続で $\psi_i\ge0$、各 $x\in K$ はある $B(x_i,\varepsilon)$ に入るので分母は正である。よって $f_\varepsilon$ は $K$ の上で連続である。$f_\varepsilon(x)$ は $y_1,\dots,y_m\in K$ の凸結合なので、凸集合 の命題「凸集合は凸結合で閉じている」により $f_\varepsilon(x)\in K$ である。コンパクト凸集合での Brouwer の定理により、$f_\varepsilon(z)=z$ となる $z\in K$ がある。
段 2(不動点を短い凸結合で書く):$I:=\{i\mid\psi_i(z)>0\}=\{i\mid\lvert z-x_i\rvert<\varepsilon\}$ とすると、$z=f_\varepsilon(z)$ は $\{y_i\mid i\in I\}$ の凸結合である。Carathéodoryの定理(凸幾何) の定理「Carathéodoryの定理」により、$z$ はこのうち高々 $n+1$ 個の点の凸結合として書ける。同じ点を繰り返してよいことにすると、ちょうど $n+1$ 個の添字 $i_0,\dots,i_n\in I$ と $\lambda_0,\dots,\lambda_n\ge0$、$\sum_j\lambda_j=1$ があって
$$
z=\sum_{j=0}^n\lambda_jy_{i_j},\qquad y_{i_j}\in\Phi(x_{i_j}),\qquad \lvert x_{i_j}-z\rvert<\varepsilon
$$
となる。
段 3(極限):$\varepsilon=1/k$($k=1,2,\dots$)として段 1・段 2 を行い、得られた $z,\lambda_j,x_{i_j},y_{i_j}$ を $z^k,\lambda^k_j,a^k_j,b^k_j$ と書く。$z^k,b^k_j\in K$、$(\lambda^k_0,\dots,\lambda^k_n)$ は $\mathbb{R}^{n+1}$ の有界閉集合 $\{\lambda\ge0,\ \sum\lambda_j=1\}$ にあるので、部分列に取り替えて $z^k\to x^*$、$\lambda^k_j\to\lambda_j$、$b^k_j\to b_j$($j=0,\dots,n$)としてよい。$\lambda_j\ge0$、$\sum\lambda_j=1$ である。$\lvert a^k_j-z^k\rvert<1/k$ なので $a^k_j\to x^*$ であり、$(a^k_j,b^k_j)\in\Gamma(\Phi)$ とグラフが閉であることから $b_j\in\Phi(x^*)$ である。$z^k=\sum_j\lambda^k_jb^k_j$ で極限をとると $x^*=\sum_j\lambda_jb_j$ となり、$\Phi(x^*)$ が凸なので $x^*\in\Phi(x^*)$ である。$\square$
段 2 で凸結合の長さを $n+1$ にそろえたのは、段 3 で $k$ を動かしても決まった個数の点列の極限として扱うためである。段 1 の有限個の点 $x_i$ の個数 $m$ は $\varepsilon$ を小さくすると一般に増えるので、Carathéodory の定理なしでは係数の極限をとれない。
$K=[0,1]$ とし、$x<1/2$ で $\Phi(x)=\{1\}$、$\Phi(1/2)=[0,1]$、$x>1/2$ で $\Phi(x)=\{0\}$ とおく。グラフ $([0,1/2)\times\{1\})\cup(\{1/2\}\times[0,1])\cup((1/2,1]\times\{0\})$ は閉集合で、値はどれも空でない凸集合である。不動点は $1/2$ だけである($x<1/2$ なら $x\ne1$、$x>1/2$ なら $x\ne0$)。連続写像 $f\colon K\to K$ で、すべての $x$ で $f(x)\in\Phi(x)$ となるものはない。そのような $f$ は $x<1/2$ で $1$、$x>1/2$ で $0$ でなければならず、$1/2$ で連続にならないからである。
$N\ge1$ 人のプレイヤー $i=1,\dots,N$ がいて、プレイヤー $i$ は空でない有限集合 $S_i$ から 1 つの 純粋戦略 を選ぶとする。$S:=S_1\times\cdots\times S_N$ の上の実数値関数 $u_i\colon S\to\mathbb{R}$ をプレイヤー $i$ の 利得 という。
$U_i$ は各 $\sigma_j$ について 1 次式(他の成分を固定すると $\sigma_j$ の成分の 1 次関数)であり、全体として $\Delta$ の上で連続である。$\Delta_i$ は $\mathbb{R}^{S_i}$ の空でないコンパクト凸集合(標準単体)であり、$\Delta$ も $\mathbb{R}^{\lvert S_1\rvert+\cdots+\lvert S_N\rvert}$ の空でないコンパクト凸集合である。
有限ゲームには、混合戦略の Nash 均衡が少なくとも 1 つある。
$\sigma\in\Delta$ に対し、プレイヤー $i$ の 最適反応 の集合を
$$
R_i(\sigma):=\Bigl\{\rho_i\in\Delta_i\Bigm| U_i(\rho_i,\sigma_{-i})=\max_{\tau_i\in\Delta_i}U_i(\tau_i,\sigma_{-i})\Bigr\}
$$
とし、$\Phi(\sigma):=R_1(\sigma)\times\cdots\times R_N(\sigma)\subset\Delta$ とおく。$\Phi$ が thm-kfp-main の仮定を満たすことを示す。
空でないこと:$\tau_i\mapsto U_i(\tau_i,\sigma_{-i})$ はコンパクト集合 $\Delta_i$ の上の連続関数なので最大値をとる(コンパクト空間 の定理「最大値・最小値の存在」)。
凸であること:$h(\tau_i):=U_i(\tau_i,\sigma_{-i})$ は $\tau_i$ の 1 次関数である。最大値を $M$ とし、$\rho,\rho'\in R_i(\sigma)$、$0\le t\le1$ とすると $h(t\rho+(1-t)\rho')=th(\rho)+(1-t)h(\rho')=M$ なので、$R_i(\sigma)$ は凸である。凸集合の直積は凸なので $\Phi(\sigma)$ も凸である。
グラフが閉であること:$\sigma^k\to\sigma$、$\rho^k\in\Phi(\sigma^k)$、$\rho^k\to\rho$ とする。各 $i$ と各 $\tau_i\in\Delta_i$ について $U_i(\rho^k_i,\sigma^k_{-i})\ge U_i(\tau_i,\sigma^k_{-i})$ であり、$U_i$ の連続性から極限をとると $U_i(\rho_i,\sigma_{-i})\ge U_i(\tau_i,\sigma_{-i})$ となる。よって $\rho_i\in R_i(\sigma)$、すなわち $\rho\in\Phi(\sigma)$ である。
thm-kfp-main により $\sigma^*\in\Phi(\sigma^*)$ となる $\sigma^*$ がある。これはすべての $i$ で $\sigma^*_i$ が $\sigma^*_{-i}$ への最適反応であること、つまり $\sigma^*$ が Nash 均衡であることを意味する。$\square$
最適反応は 1 つとは限らないので、$R_i$ は写像ではなく対応である。ここで集合値の不動点定理が自然に必要になる。
2 人がそれぞれ硬貨の表 $H$ か裏 $T$ を選び、一致すればプレイヤー 1 が $1$ を得てプレイヤー 2 が $1$ を失い、一致しなければその逆になるとする($u_1(s)=1$、$u_2(s)=-1$($s_1=s_2$)、$u_1(s)=-1$、$u_2(s)=1$($s_1\ne s_2$))。純粋戦略の組には Nash 均衡がない。一致していればプレイヤー 2 が、一致していなければプレイヤー 1 が、自分の選択を変えて得をするからである。混合戦略では、$p,q$ をプレイヤー 1・2 が $H$ を選ぶ確率とすると $U_1=(2p-1)(2q-1)$、$U_2=-U_1$ である。$q=1/2$ なら $U_1=0$ は $p$ によらず、$p=1/2$ なら $U_2=0$ は $q$ によらないので、$p=q=1/2$ は Nash 均衡である。ほかに均衡はない。$(p,q)$ を均衡とする。$q>1/2$ なら $U_1$ は $p$ について真に増えるので $p=1$ であり、すると $U_2=-(2q-1)$ を最大にする $q$ は $0$ だけなので $q>1/2$ に反する。$q<1/2$ なら同じく $p=0$ で、$U_2=2q-1$ から $q=1$ となり反する。よって $q=1/2$ である。$p>1/2$ なら $U_2$ は $q$ について真に減るので $q=0$、すると $U_1=-(2p-1)$ から $p=0$ となり反する。$p<1/2$ でも同様なので $p=1/2$ である。
$A$ を実数を成分とする $m\times n$ 行列とし、$\Delta_m\subset\mathbb{R}^m$、$\Delta_n\subset\mathbb{R}^n$ を確率ベクトル全体とする。このとき
$$
\max_{x\in\Delta_m}\min_{y\in\Delta_n}x^{\mathsf T}Ay=\min_{y\in\Delta_n}\max_{x\in\Delta_m}x^{\mathsf T}Ay
$$
が成り立つ。
$\phi(x):=\min_yx^{\mathsf T}Ay$ と $\chi(y):=\max_xx^{\mathsf T}Ay$ を考える。$y\mapsto x^{\mathsf T}Ay$ は 1 次関数なので、$\Delta_n$ の上の最小値は頂点(標準基底 $e_1,\dots,e_n$)のどれかでとられ、$\phi(x)=\min_l(x^{\mathsf T}A)_l$ は有限個の 1 次関数の最小値として連続である。同様に $\chi$ も連続なので、両辺の $\max$ と $\min$ は存在する。
左辺 $\le$ 右辺:任意の $x',y'$ について $\phi(x')\le x'^{\mathsf T}Ay'\le\chi(y')$ なので、$x'$ について最大、$y'$ について最小をとればよい。
左辺 $\ge$ 右辺:プレイヤー 1 の純粋戦略を $\{1,\dots,m\}$、プレイヤー 2 の純粋戦略を $\{1,\dots,n\}$、利得を $u_1(k,l)=a_{kl}$、$u_2(k,l)=-a_{kl}$ とする 2 人ゲームを考える。混合戦略 $x,y$ に対し $U_1=x^{\mathsf T}Ay$、$U_2=-x^{\mathsf T}Ay$ である。thm-kfp-nash により Nash 均衡 $(x^*,y^*)$ があり、すべての $x,y$ で $x^{\mathsf T}Ay^*\le x^{*\mathsf T}Ay^*\le x^{*\mathsf T}Ay$ である。よって
$$
\max_x\phi(x)\ge\phi(x^*)=x^{*\mathsf T}Ay^*=\chi(y^*)\ge\min_y\chi(y)
$$
である。$\square$
同じ等式を線形計画の双対定理から導く証明は、線形計画法 の定理「最小最大定理」にある。
thm-kfp-main の仮定は、$K$ が空でなく、凸で、有界で、閉であること、値が空でなく凸であること、グラフが閉であることである。次の表の各行は、そのうち 1 つだけを外した例である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 値が空でない | $K=[0,1]$、$\Phi(x)=[x+\frac12,1]$($x>\frac12$ では $\emptyset$) | 不動点がない |
| 値が凸 | $K=[0,1]$、$x<\frac12$ で $\{1\}$、$\Phi(\frac12)=\{0,1\}$、$x>\frac12$ で $\{0\}$ | 不動点がない |
| グラフが閉 | $K=[0,1]$、$x\le\frac12$ で $\{1\}$、$x>\frac12$ で $\{0\}$ | 不動点がない |
| $K$ が凸 | $K$ は単位円周、$\Phi(x)=\{\text{$x$ の }90^\circ\text{ 回転}\}$ | 不動点がない |
| $K$ が有界 | $K=[0,\infty)$、$\Phi(x)=\{x+1\}$ | 不動点がない |
| $K$ が閉 | $K=(0,1]$、$\Phi(x)=\{x/2\}$ | 不動点がない |
1 行目:$x\le1/2$ なら $\Phi(x)=[x+1/2,1]$ は空でない閉区間、$x>1/2$ なら空集合である。グラフ $\{(x,y)\in[0,1]^2\mid y\ge x+1/2\}$ は閉集合で、値はどれも凸(空集合も凸)である。$x\in\Phi(x)$ なら $x\ge x+1/2$ となり不可能である。
2 行目:グラフ $([0,\frac12]\times\{1\})\cup([\frac12,1]\times\{0\})$ は 2 つの閉線分の和で閉集合であり、値はすべて空でない。凸でない値は $\Phi(1/2)=\{0,1\}$ だけである。$x<1/2$ では $x\ne1$、$x>1/2$ では $x\ne0$、$1/2\notin\{0,1\}$ なので不動点はない。
3 行目:値は 1 点で凸、空でない。$x_k=\frac12+\frac1k$ で $(x_k,0)\to(\frac12,0)$ だが $0\notin\Phi(\frac12)$ なので、グラフは閉でない。不動点がないことは 2 行目と同じである。
4 行目:単位円周はコンパクトだが凸でない。値は 1 点で、回転は連続なのでグラフは閉である。回転 $x\mapsto(-x_2,x_1)$ で動かない点は原点だけで、円周の上にない。
5 行目:$[0,\infty)$ は閉凸だが有界でない。$x+1\ne x$ である。
6 行目:$(0,1]$ は有界凸だが閉でない。$x/2=x$ となる $x$ は $0$ だけで、$K$ にない。
この定理は角谷静夫(Shizuo Kakutani、1911–2004)が 1941 年に Duke Mathematical Journal に発表した「Brouwer の不動点定理の一般化」による(定理の形は Hen16 p. 2)。角谷の元の証明は、定義域を細かく分割し、分割の各頂点で値 $\Phi(x)$ の点を 1 つ選んで区分的に 1 次の写像を作り、その不動点の極限をとるものだった(Hen16 p. 3 の Theorem 1 の証明は、これを立方体の上で述べている)。この記事の証明は、分割の代わりに有限個の開球と連続な重みを使い、Carathéodory の定理で凸結合の長さをそろえた形である。角谷は同じ論文で、この定理から von Neumann のミニマックス定理の一般化を導いている(Hen16 §3、p. 11)。J. Nash は 1950 年ごろ、混合戦略の均衡の存在を最初はこの定理で示し、のちに Brouwer の定理で足りることに気づいた(PVZ23 §1、p. 1)。
1 点を値とする対応に当てればコンパクト凸集合での Brouwer の定理になり、逆に prf-kfp-main はその Brouwer の定理だけから角谷の定理を導いた。したがって、$\mathbb{R}^n$ のコンパクト凸集合について、2 つの定理は互いに導き合う。無限次元で写像の像のコンパクト性を仮定する Brouwer の定理の拡張は Schauderの不動点定理 である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する