von Neumannのミニマックス定理

同義語:フォン・ノイマンのミニマックス定理von Neumannの最小最大定理von Neumann's minimax theorem

概要

von Neumannのミニマックス定理(von Neumann's minimax theorem)とは、利得行列 $A$ の 2 人ゼロ和ゲームで、混合戦略を許せば $\max_x\min_yx^{\mathsf T}Ay=\min_y\max_xx^{\mathsf T}Ay$ が成り立ち、両者に鞍点の不等式を満たす最適戦略があるという定理で、共通の値をゲームの値という。証明は 1 次不等式系の択一定理(Farkas の補題)から直接に得られ、値と最適戦略は互いに双対な線形計画問題の解として求まり、最適戦略の集合は凸多面体になる。凸性と半連続性の条件に広げた形が Sion の定理である。

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

前提知識: ゲーム理論, 線形計画法, Farkasの補題

von Neumannのミニマックス定理(von Neumann's minimax theorem)は、2 人ゼロ和ゲームで、混合戦略を許せば「自分の最悪の場合を最善にする」値が両方の参加者で一致することを述べる定理である。利得行列を $A$ とすると
$$ \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 $$
が成り立つ。この共通の値をゲームの 値 という。
左辺は、参加者 I が先に混合戦略を公表しても確保できる利得であり、右辺は、参加者 II が先に公表しても抑えられる損失である。純粋戦略だけでは両者は一致するとは限らない(コイン合わせでは $-1$ と $1$)。定理は、確率を混ぜれば、手の内を明かすことの不利が消えることを述べている。J. von Neumann が 1928 年の論文で示し、ゲーム理論の出発点になった(KP17 第 2 章の注、p. 48)。
この記事では、値と最適戦略を定義し、主定理を 1 次不等式系の択一定理(Farkasの補題)から直接に証明する。続いて、最適戦略の集合の形、値の性質、手で解く方法を述べ、例で確かめる。最後に、無限の戦略の集合への一般化である Sion の定理を述べ、仮定を外すと値が存在しなくなる例を挙げる。行列を正にずらして双対定理を当てる証明は 線形計画法 の定理「最小最大定理」に、Nash 均衡の存在から導く証明は 角谷の不動点定理 の系「行列ゲームのミニマックス定理」にあるので、ここでは繰り返さない。

定義

行列ゲーム・値・最適戦略

$A=(a_{ij})$ を実数を成分とする $m\times n$ 行列とする。行列ゲーム $A$ では、参加者 I が行 $i$ を、参加者 II が列 $j$ を、相手の選択を知らずに選び、II が I に $a_{ij}$ を支払う。
$\Delta_m:=\{x\in\mathbb R^m\mid x\ge0,\ \sum_ix_i=1\}$ の元を I の 混合戦略、$\Delta_n$ の元を II の混合戦略といい、組 $(x,y)$ の期待利得を $x^{\mathsf T}Ay=\sum_{i,j}x_ia_{ij}y_j$ とする。
$$ \underline v:=\max_{x\in\Delta_m}\min_{y\in\Delta_n}x^{\mathsf T}Ay,\qquad \overline v:=\min_{y\in\Delta_n}\max_{x\in\Delta_m}x^{\mathsf T}Ay $$
を 下の値・上の値 という。$\min_yx^{\mathsf T}Ay=\underline v$ となる $x$ を I の 最適戦略、$\max_xx^{\mathsf T}Ay=\overline v$ となる $y$ を II の最適戦略という。$\underline v=\overline v$ のとき、この数を 値 といい $V(A)$ と書く。

$\min_y$ は純粋戦略($\Delta_n$ の頂点 $e_j$)で達成される:$y\mapsto x^{\mathsf T}Ay$ は 1 次関数で、$\Delta_n$ の点は頂点の凸結合だからである。よって
$$ \min_{y\in\Delta_n}x^{\mathsf T}Ay=\min_j(A^{\mathsf T}x)_j,\qquad \max_{x\in\Delta_m}x^{\mathsf T}Ay=\max_i(Ay)_i\qquad\text{(1)} $$
である。右辺は有限個の 1 次関数の最小・最大なので連続で、$\Delta_m,\Delta_n$ はコンパクトだから、定義の $\max$・$\min$ は存在する。

下の値は上の値以下

すべての行列 $A$ について
$$ \max_i\min_ja_{ij}\le\underline v\le\overline v\le\min_j\max_ia_{ij} $$
である。

1 つの組をはさむ

任意の $x',y'$ で $\min_yx'^{\mathsf T}Ay\le x'^{\mathsf T}Ay'\le\max_xx^{\mathsf T}Ay'$ である。左辺の $x'$ についての最大は右辺の $y'$ についての最小以下なので $\underline v\le\overline v$ である。純粋戦略 $e_i$ は $\Delta_m$ の元なので、(1) から $\min_ja_{ij}=\min_ye_i^{\mathsf T}Ay\le\underline v$ であり、外側の不等式も同様である。$\square$

外側の 2 数は純粋戦略だけで計算した下の値・上の値である。一致するとき、達成する組 $(i,j)$ を 鞍点 という。鞍点では $a_{ij}$ が列 $j$ の中で最大かつ行 $i$ の中で最小である(KP17 Definition 2.4.1、p. 38)。

主定理と証明

von Neumann のミニマックス定理

任意の実 $m\times n$ 行列 $A$ について $\underline v=\overline v$ である。とくに両方の参加者に最適戦略があり、$x^*,y^*$ が最適戦略なら、すべての $x\in\Delta_m$、$y\in\Delta_n$ について
$$ x^{\mathsf T}Ay^*\le V(A)=x^{*\mathsf T}Ay^*\le x^{*\mathsf T}Ay $$
である。

主張は KP17 Theorem 2.3.1(p. 37)による。KP17 §2.6(pp. 45–48)は分離超平面定理を使って証明している。ここでは同じ分離の考えを、1 次不等式系の択一定理(線形計画法 の定理「1 次不等式系の択一定理」。証明は Farkasの補題 の記事にある)の形で使う。

上の値を保証する戦略を択一定理で探す

prop-mm-weak により、$\underline v\ge\overline v$ を示せばよい。そのためには、$A^{\mathsf T}x\ge\overline v\,\mathbf 1$ を満たす $x\in\Delta_m$ を見つければよい($\mathbf 1$ は成分がすべて $1$ のベクトル)。実際そのような $x$ があれば、(1) から $\underline v\ge\min_j(A^{\mathsf T}x)_j\ge\overline v$ である。
条件を $x\in\mathbb R^m$ についての 1 次不等式系
$$ -(A^{\mathsf T}x)_j\le-\overline v\ (1\le j\le n),\qquad -x_i\le0\ (1\le i\le m),\qquad \textstyle\sum_ix_i\le1,\qquad -\sum_ix_i\le-1 $$
に書く。これに解がないと仮定する。択一定理により、各不等式に掛ける $0$ 以上の数 $q_j,r_i,s,t$ で、左辺の係数ベクトルの和が $0$ になり、右辺の和が負になるものがある。$q=(q_j)$、$r=(r_i)$ と書くと、これは
$$ -Aq-r+(s-t)\mathbf 1=0,\qquad -\overline v\textstyle\sum_jq_j+s-t< 0 $$
である。第 1 式から $Aq=(s-t)\mathbf 1-r\le(s-t)\mathbf 1$ である。
$q=0$ とすると、第 1 式から $r=(s-t)\mathbf 1$ で、$r\ge0$ から $s-t\ge0$ となり、第 2 式の $s-t<0$ に反する。よって $Q:=\sum_jq_j>0$ である。$y:=q/Q\in\Delta_n$、$c:=(s-t)/Q$ とおくと、$Ay\le c\,\mathbf 1$ で、第 2 式から $c<\overline v$ である。すると (1) から $\max_xx^{\mathsf T}Ay=\max_i(Ay)_i\le c<\overline v$ となり、$\overline v$ が $y$ についての最小値であることに反する。
したがって不等式系には解 $x^*$ があり、$\underline v=\overline v$ である。この $x^*$ は I の最適戦略である。II の最適戦略の存在は $\overline v$ の定義の $\min$ が達成されることそのものである。
最後の不等式:$x^*,y^*$ を最適戦略とすると、任意の $x,y$ で $x^{\mathsf T}Ay^*\le\max_{x'}x'^{\mathsf T}Ay^*=V(A)=\min_{y'}x^{*\mathsf T}Ay'\le x^{*\mathsf T}Ay$ である。$x=x^*$、$y=y^*$ を代入すると $x^{*\mathsf T}Ay^*=V(A)$ を得る。$\square$

証明の要は、「上の値より小さい $c$ で $Ay\le c\mathbf 1$ となる $y$ はない」という事実を、択一定理で「$A^{\mathsf T}x\ge\overline v\mathbf 1$ となる $x$ がある」に言い換えるところにある。II の側の問題が解けないことの証拠(不等式の非負結合)が、そのまま I の戦略になっている。
最後の不等式は、最適戦略の組が鞍点の不等式を満たすこと、つまり 2 人ゼロ和ゲームの Nash 均衡であることを述べる。逆にどの Nash 均衡も最適戦略の組である(Nash均衡 の命題「2 人ゼロ和ゲームの均衡」)。

線形計画としての値

証明の不等式系は、次の 2 つの線形計画問題の実行可能性を調べていることになる。
$$ \text{(P)}\ \ \max v\quad\text{条件 } A^{\mathsf T}x\ge v\mathbf 1,\ x\in\Delta_m,\qquad \text{(D)}\ \ \min w\quad\text{条件 } Ay\le w\mathbf 1,\ y\in\Delta_n $$
(P) の最適値は (1) により $\underline v$、(D) の最適値は $\overline v$ で、(P) と (D) は互いの双対問題になっている。主定理はこの組の双対定理であり、ゲームの値と最適戦略は線形計画を解いて求まる(KP17 第 2 章の注、p. 49)。

最適戦略の集合と相補性

$V=V(A)$ とする。
(1) I の最適戦略の全体は $O_{\mathrm I}=\{x\in\Delta_m\mid A^{\mathsf T}x\ge V\mathbf 1\}$、II の最適戦略の全体は $O_{\mathrm{II}}=\{y\in\Delta_n\mid Ay\le V\mathbf 1\}$ で、どちらも空でない有界な凸多面体である。
(2) $x^*\in O_{\mathrm I}$、$y^*\in O_{\mathrm{II}}$ とする。$x^*_i>0$ なら $(Ay^*)_i=V$ であり、$y^*_j>0$ なら $(A^{\mathsf T}x^*)_j=V$ である。

平均が上限に等しい
  1. 式 (1) から、$x$ が最適であることは $\min_j(A^{\mathsf T}x)_j=V$、すなわち $A^{\mathsf T}x\ge V\mathbf 1$ と同値である($\ge$ なら最小値は $V$ 以上で、$V$ は最大値なので等しい)。この集合は有限個の閉半空間と $\Delta_m$ の共通部分なので有界な凸多面体で、thm-mm-main により空でない。$O_{\mathrm{II}}$ も同様である。
  2. thm-mm-main から $V=x^{*\mathsf T}Ay^*=\sum_ix^*_i(Ay^*)_i$ で、各 $(Ay^*)_i\le V$、$\sum_ix_i^*=1$ である。よって $x^*_i>0$ の項ではすべて $(Ay^*)_i=V$ でなければならない。後半も同様である。$\square$
  1. は、最適戦略が正の確率を置く行では、相手の最適戦略に対する利得がすべて値に等しいことを述べる(KP17 Proposition 2.5.3、p. 43 の等化の原理)。これを使うと小さいゲームを手で解ける。

値の性質

値の基本性質

$A,B$ を $m\times n$ 行列、$J$ を成分がすべて $1$ の $m\times n$ 行列とする。
(1) $\alpha>0$、$\beta\in\mathbb R$ なら $V(\alpha A+\beta J)=\alpha V(A)+\beta$ で、最適戦略は変わらない。
(2) すべての $i,j$ で $a_{ij}\le b_{ij}$ なら $V(A)\le V(B)$ である。
(3) $|V(A)-V(B)|\le\max_{i,j}|a_{ij}-b_{ij}|$ である。
(4) 役割を入れ替えた $n\times m$ のゲーム $-A^{\mathsf T}$ について $V(-A^{\mathsf T})=-V(A)$ である。とくに $A$ が正方行列で $A^{\mathsf T}=-A$(交代行列)なら $V(A)=0$ である。

期待利得の不等式を最大・最小に通す
  1. $x^{\mathsf T}(\alpha A+\beta J)y=\alpha x^{\mathsf T}Ay+\beta$ で、$\alpha>0$ の 1 次変換は $\max$・$\min$ と可換である。
  2. すべての $x,y$ で $x^{\mathsf T}Ay\le x^{\mathsf T}By$ なので、$\max_x$ をとってから $\min_y$ をとっても大小は保たれる。
  3. $\delta:=\max|a_{ij}-b_{ij}|$ とすると $A\le B+\delta J$ なので、(2) と (1) から $V(A)\le V(B)+\delta$ である。$A$ と $B$ を入れ替えればよい。
  4. $-A^{\mathsf T}$ では II(もとの列の側)が利得 $y^{\mathsf T}(-A^{\mathsf T})x=-x^{\mathsf T}Ay$ を受け取るので、
    $$ V(-A^{\mathsf T})=\max_y\min_x(-x^{\mathsf T}Ay)=-\min_y\max_xx^{\mathsf T}Ay=-V(A) $$
    である。$A^{\mathsf T}=-A$ なら $-A^{\mathsf T}=A$ なので $V(A)=-V(A)$、すなわち $V(A)=0$ である。$\square$
  1. の後半は、両者の立場が完全に対称なゲームは公平であることを述べる(KP17 Claim 2.4.3、p. 40 は別の計算で示している)。じゃんけんがその例である(Nash均衡 の例「じゃんけん」)。

2 行のゲームを図で解く

$m=2$ のときは $x=(p,1-p)$ と書けるので、(1) から
$$ V(A)=\max_{0\le p\le1}\ \min_j\bigl(pa_{1j}+(1-p)a_{2j}\bigr) $$
である。右辺は $n$ 本の直線の下側の包絡線の最高点で、図を描けば求まる。最高点で交わる直線の列が、prop-mm-optimal-set (2) により II の最適戦略の台の候補になる。

例

鞍点のあるゲーム

$A=\begin{pmatrix}4&2&5\\1&0&3\end{pmatrix}$ では、行の最小値は $2,0$ で最大は $2$、列の最大値は $4,2,5$ で最小は $2$ である。prop-mm-weak の外側の 2 数が一致するので $V(A)=2$ で、純粋戦略の組(第 1 行、第 2 列)が鞍点である。

2 行 3 列のゲーム

$A=\begin{pmatrix}3&-1&2\\-2&2&1\end{pmatrix}$ とする。純粋戦略では行の最小値の最大は $-1$、列の最大値の最小は $2$ で、鞍点はない。
I が第 1 行を確率 $p$ で選ぶと、各列に対する利得は $5p-2$、$2-3p$、$1+p$ である。$5p-2=2-3p$ から $p=\frac12$ で、このとき 3 つの値は $\frac12,\frac12,\frac32$ である。$p<\frac12$ では $5p-2<\frac12$、$p>\frac12$ では $2-3p<\frac12$ なので、包絡線の最高点は $p=\frac12$ で、$V(A)=\frac12$、$x^*=(\frac12,\frac12)$ である。
prop-mm-optimal-set (2) により、II の最適戦略は第 3 列に確率を置かない(第 3 列の利得 $\frac32$ は値より大きい)。$y=(q,1-q,0)$ として行の利得を等しくおくと $4q-1=2-4q$、$q=\frac38$ で、$Ay^*=(\frac12,\frac12)$ となる。よって $y^*=(\frac38,\frac58,0)$ は最適である。

対角行列のゲーム(隠れんぼ)

$d_1,\dots,d_n>0$ とし、$A=\mathrm{diag}(d_1,\dots,d_n)$ とする。II が $n$ か所のどこかに隠れ、I が 1 か所を探して、当たれば場所 $i$ に応じて $d_i$ を得るゲームである。$S:=\sum_k1/d_k$、$x^*_i=y^*_i:=\frac{1/d_i}{S}$ とおくと、$(A^{\mathsf T}x^*)_j=d_jx^*_j=\frac1S$、$(Ay^*)_i=\frac1S$ なので、$A^{\mathsf T}x^*\ge\frac1S\mathbf 1\ge Ay^*$ である。(1) と prop-mm-weak から
$$ \frac1S\le\underline v\le\overline v\le\frac1S $$
となり、$V(A)=1/\sum_k(1/d_k)$ である。両者とも、賞金の小さい場所ほど大きい確率で選ぶ。

一般化:Sion の定理

戦略の集合が無限のときは、$\max$・$\min$ を $\sup$・$\inf$ に替えて同じ問いを立てる。双 1 次の関数を、凸性と半連続性の弱い条件に置き換えた次の形がよく使われる。

Sion のミニマックス定理(主張と所在)

$M,N$ を位相線形空間の凸部分集合とし、どちらか一方はコンパクトとする。関数 $f\colon M\times N\to\mathbb R$ が次を満たすとする。

  • 各 $\nu\in N$ について、$\mu\mapsto f(\mu,\nu)$ は上半連続で準凹($\{\mu\mid f(\mu,\nu)\ge c\}$ がすべての $c$ で凸)。
  • 各 $\mu\in M$ について、$\nu\mapsto f(\mu,\nu)$ は下半連続で準凸($\{\nu\mid f(\mu,\nu)\le c\}$ がすべての $c$ で凸)。
    このとき $\sup_{\mu\in M}\inf_{\nu\in N}f(\mu,\nu)=\inf_{\nu\in N}\sup_{\mu\in M}f(\mu,\nu)$ である。
所在と証明の方法

これは Sio58 の定理 3.4(両方がコンパクトの場合、p. 174)とその直後の系(一方がコンパクトの場合、p. 174。印刷では番号が 3.3 になっている)である。この記事では証明しない。Sio58 の証明は Sperner の補題に基づく Knaster–Kuratowski–Mazurkiewicz の定理を使い、凸集合の分離も不動点定理も使わない(同 p. 171 の序)。

行列ゲームは $M=\Delta_m$、$N=\Delta_n$、$f(x,y)=x^{\mathsf T}Ay$ の場合で、$f$ は各変数について 1 次なので条件を満たす。
$[0,1]$ から数を選ぶゲームで、利得 $A(x,y)$ が $[0,1]^2$ 上で連続なら、$[0,1]$ 上の確率分布を混合戦略として、$\max\min$ と $\min\max$ が一致する(KP17 Theorem 2.7.1、p. 48。証明は利得を階段関数ではさんで行列ゲームに帰着させる)。

反例:仮定を外すと成り立たないこと

次の表の各行は、上の定理の仮定を 1 つ外すと、結論「$\sup\inf=\inf\sup$(値が存在する)」が成り立たなくなる反例である。

外す仮定例下の値と上の値
混合戦略を許す(thm-mm-main)コイン合わせ $A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$ で純粋戦略だけを使う$-1$ と $1$
戦略の集合が有限(thm-mm-main)自然数を言い合い、大きい方が $1$ を得る$-1$ と $1$
$\mu$ について準凹(thm-mm-sion)$M=N=[0,1]$、$f(\mu,\nu)=(\mu-\nu)^2$$0$ と $\frac14$
$\mu$ について上半連続(thm-mm-sion)ex-mm-counterexamples の Sion の例$0$ と $1$
表の例の確かめ

コイン合わせ:どの行にも $-1$ があり、どの列にも $1$ があるので、prop-mm-weak の外側の 2 数は $-1$ と $1$ である。混合戦略を許すと値は $0$ で、$(\frac12,\frac12)$ が両者の最適戦略である。
大きい数:混合戦略は自然数の上の確率分布 $x,y$ で、$f(x,y)=\Pr[X>Y]-\Pr[X< Y]$($X,Y$ は独立に $x,y$ に従う)とする。どの $x$ に対しても、II は十分大きい $k$ を確率 $1$ で言えば $f$ を $-1$ に近づけられるので $\inf_yf(x,y)=-1$、よって下の値は $-1$ である。同様に上の値は $1$ である。
準凹でない例:$f(\mu,\nu)=(\mu-\nu)^2$ は $\nu=\mu$ とすれば $0$ なので $\sup_\mu\inf_\nu f=0$ である。一方 $\sup_\mu f(\mu,\nu)=\max(\nu^2,(1-\nu)^2)\ge\frac14$ で、$\nu=\frac12$ で等号なので $\inf_\nu\sup_\mu f=\frac14$ である。ほかの仮定(凸でコンパクト、連続、$\nu$ について準凸)は満たされ、$\mu\mapsto(\mu-\nu)^2$ の上位集合 $\{\mu\mid(\mu-\nu)^2\ge c\}$ だけが凸でない($c=\frac1{16}$、$\nu=\frac12$ では $[0,\frac14]\cup[\frac34,1]$)。
Sion の例(Sio58 3.6、p. 174):$M=N=[0,1]$ とし、「$0\le\mu<\frac12$ かつ $\nu=0$」または「$\frac12\le\mu\le1$ かつ $\nu=1$」のとき $f(\mu,\nu)=0$、それ以外で $f(\mu,\nu)=1$ とする。各 $\mu$ で $\nu=0$ か $\nu=1$ を選べば $0$ になるので $\sup\inf=0$ である。$\nu=0$ には $\mu=1$、$\nu=1$ には $\mu=0$、ほかの $\nu$ にはどの $\mu$ でも $1$ になるので $\inf\sup=1$ である。$\mu\mapsto f(\mu,\nu)$ の上位集合は空集合・$[\frac12,1]$・$[0,\frac12)$・全体のどれかで凸であり、$\nu\mapsto f(\mu,\nu)$ は 1 点だけで $0$ をとるので準凸かつ下半連続である。上半連続でないのは $f(\cdot,1)$ の $\mu=\frac12$ での値 $0$ が左からの極限 $1$ より小さいところだけである。

補足

証明の系譜

KP17 第 2 章の注(p. 48)によれば、von Neumann の 1928 年の証明は不動点定理を使い、分離超平面定理による証明は H. Weyl(1950 年)、帰納法による証明は G. Owen(1967 年)による。線形計画との関係については、G. Dantzig が 1947 年に von Neumann を訪ねたとき、von Neumann が線形計画の双対性をゲームの理論の類似として即座に説明したという回想が同 p. 49–50 に引かれている。Sio58 の序(p. 171)は、J. Ville や A. Wald が戦略の集合を無限次元の線形空間の部分集合に広げたこと、関数を凹凸の型に広げて凸集合の分離で示す流れ(Kneser、Ky Fan ほか)と、準凹凸の関数に不動点定理を当てる流れがあり、Sion の定理がその 2 つを統一したことを述べている。

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, Definition 2.4.1(p. 38)、Theorem 2.3.1(p. 37)、Claim 2.4.3(p. 40)、Proposition 2.5.3(p. 43)、§2.6(pp. 45–48)、Theorem 2.7.1(p. 48)、第 2 章の注(pp. 48–50)(頁は著者公開版 2016-12-13 による)
[2]
Maurice Sion, On general minimax theorems, Pacific Journal of Mathematics 8 (1958), no. 1, 171–176, 1958, p. 171(序)、p. 174(定理 3.4、その系、注意 3.6)

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