数理解析研究所講究録
第 1829 巻 2013 年 139-148

139
離散不動点定理と単体分割
九州大学大学院数理学研究院川崎英文 (Hidefumi Kawasaki)
Faculty of Mathematics, Kyushu University

kawasaki@math.kyushu-u.ac.jp

近年，離散不動点定理とゲーム理論へのその応用が研究されている．離散不動点定理には，(C) 縮小写像の不動点定理，(M) 単調写像の不動点定理，(B)Brouwer の不動点定理を利用するタイプがあり，それぞれ独立に研究されてきた．本論文では，タイプ (B) を中心に考察し，写像の定義域の単体分割が重要であることを示す．さらに，双行列ゲームを通して，タイプ (M) との比較をおこなう．

1

Brouwer の不動点定理に基づく離散不動点定理
飯村 [2] は，離散集合$X\subset \mathbb{Z}^{n}$からそれ自身への写像$f$を連続写像へ拡張し，Brouwerの不動点定理を適用することにより離散不動点定理を導く方法を提案した．そのアイディ

アは，まず$X$の凸包を単体分割し，単体の頂点での値 $f(x)$ を基に区分的線形写像$g$に拡張する．次に， の不動点が単体内部ではなく頂点になるような条件を与えて離散不動点定理を得る．飯村はその条件を方向保存条件とよんでいる．なお，Hex ゲームと Brouwer$g$の不動点定理の同値性を示した Gale[1] に類似のアイディアが見られる．の単体の族は以下の 3 条件を満たすとき，の単体分割と言う．
$\mathbb{R}^{n}$$C$. (ii)$\mathfrak{S}$$S\in \mathfrak{S}$$C\subset \mathbb{R}^{n}$の面も$\mathfrak{S}$に属する．(iii)$( i)\bigcup_{S\in \mathfrak{S}}S=$$\mathfrak{S}$の二つの単体の共通部分は空力], それらの共$x,$ $x’$

$x\sim x’$ と書く．点はセル連結であると言い，通面である．

単体分割において，同じ単体の頂点$x$とセル連結な $x’\in X$ の集合を対して，任意の点$x$$X$ から $X$ への集合値写像 $F$ にの近傍とよぶ．また，

で $f(x)\in F(x)$なる写像 をセレクションとよぶ．
飯村 [2], 飯村-室田- 田村 [3] は，有限集合 (整凸集合)と集合値写像 $F$ に対し
$x$

$f$

$X\subset \mathbb{Z}^{n}$て，特別なセレクションを用いる形で離散不動点定理を与え，次の条件を方向保存条件と$x\sim x’$ の代わりに $||x-x’||_{\infty}\leq 1$ を用いた).
よんだ (正確には，$x\sim x’\Rightarrow(f_{i}(x)-x_{i})(f_{i}(x’)-x_{i}’)\geq 0 (i=1, \ldots, n)$.

(1)

Yang [12] は単体分割を出発点に，方向保存条件を少し緩めた局所総和方向保存条件 (locallygross direction preserving)$x\sim x’\Rightarrow(f(x)-x)^{T}(f(x’)-x’)\geq 0$(2)140を用いて離散不動点定理 (定理 1) を与えた．なお，方向保存条件，局所総和方向保存条
件いずれを用いても証明は同じである．
定理 1 $coX$ を有限集合
ション $f$2$F$ のあるセレクの凸包， を $coX$ の単体分割とする．
が局所総和方向保存条件を満たすならば，$x\in F(x)$ なる $x\in X$ が存在する．
$X\subset \mathbb{Z}^{n}$$\mathfrak{S}$双行列ゲームに対する方向保存条件離散不動点定理をゲーム理論に適用する際，方向保存条件等を翻訳する必要があり，本節では双行列ゲームを通して方向保存条件を詳しく調べる．
利得行列 $A=(a_{ij}),$ $B=(b_{ij})$ が与えられた対戦型ゲームで，2双行列ゲームとは，人のプレイヤーはそれぞれ $x^{T}Ay,$ $x^{T}By$ を最大にするように確率ベクトル $x\in P_{m},$ $y\in P_{n}$を選ぶ．この確率ベクトルのことを混合戦略，第 単位ベクトル $e_{i}=(0, \ldots, 1, \ldots, 0)$ を$m\cross n$$i$$A,$純戦略とよぶ．ゲーム理論でよく知られているように，$B$がどのような行列であっても$x^{T}A\overline{y}\leq\overline{x}^{T}A\overline{y},\overline{x}^{T}By\leq\overline{x}^{T}B\overline{y} \forall x\in P_{m}, y\in P_{n}$なる確率ベクトル$x=e_{i},$ $y=e_{j}$$\overline{x},\overline{y}$が存在し，それは Nash 均衡とよばれる．一方，戦略を純戦略に限定すると，Nash 均衡が存在するとは限らないが，離散不動点定理を用いることにより，純戦略 Nash 均衡の存在を論じることができる．
ところで，行列の行番号や列番号は通常 1 から始めるが， 次元の場合は から始める方が記述が楽である．そこで，プレイヤー 1,2 の最適応答をそれぞれ次式で定める．
$n$$F_{1}(j)=\{i\in\{0, \ldots, m\}|a_{ij}\geq a_{i’j}\forall i’\},$$0$$F_{2}(i)=\{j\in\{0, \ldots, n\}|b_{ij}\geq b_{ij’}\forall j’\}.$$F(i,j)=F_{1}(j)\cross F_{2}(i)$ とおくと，純戦略 Nash 均衡は $(i, j)\in F(i, j)$ と表現でこのとき，きる．また，双行列ゲームでは $[0, m]\cross[0, n]$ 格子の単体分割を考えるが，最初に特別な単体分割を考察する (命題 1-3). 一般の単体分割は定理 2 で取り扱う．

格子の単体分割として Freudenthal 分割 1 をとるとき，最適応答 $F$のセレクション $f=(fi, f_{2})$ が方向保存であるための必要十分条件は (3) を満たすことで

命題 1$[0, m]\cross[0, n]$ある．
$f_{1}(j)\leq f_{1}(j+1)\leq f_{1}(j)+1, f_{2}(i)\leq f_{2}(i+1)\leq f_{2}(i)+1 \forall i, j$ .

1 この名称藤重悟先生教えて頂いた．

(3)

141

図 1: Freudenthal 分割と近傍．行列の座標の原点は左上にあるが， 次元への拡張に備え$n$て，左下の点 (0,0) を原点にする．

図 2: Freudenthal 分割の場合，方向保存な最適応答は増加量が高々 1 の単調増加関数．

命題 2 $[0, m]\cross[0, n]$ 格子の単体分割として Freudenthal 分割を 90 度回転させたものをとるとき，最適応答$F$のセレクション $f$ が方向保存であるための必要十分条件は (4) を満たすことである．
$f_{1}(j)-1\leq f_{1}(j+1)\leq f_{1}(j) , f_{2}(i)-1\leq f_{2}(i+1)\leq f_{2}(i)\forall i, j$ .

(4)

ユニオンジャック分割をとると，単調でない最適応答を取り扱うことができる．
命題 3 $[0, m]\cross[0, n]$ 格子の単体分割として図 3 のユニオンジャック分割をとるとき，最適応答 $F$ のセレクションが方向保存であるための必要十分条件は (5) と (6) を満たすことである．
$f$$f_{1}(j\pm 1)=\{\begin{array}{l}f_{1}(j), fi(i)+1, fi(j)-1 のどれか，i+fi(j) :evenf_{1}(j) , j+f_{1}(j) :$f_{2}(i),$$f_{2}(j\pm 1)=($$f_{2}(i)$,$f_{2}(i)+1,$ $f_{2}(i)-1$odd.\end{array}$$i+f_{2}(i)$ : evenのどれか，$i+f_{2}(i)$:odd.

(5)

(6)

142

図 3: ユニオンジャック分割の場合，単調でない最適応答が現れる．

このように，離散不動点定理を応用する際に単体分割は重要である．実は，一般の単体分割に対する方向保存条件を特徴づけることができる．$[0, m]\cross[O, n]$ 格子の任意の単体分割 (図 4) に対して，その境界 (辺) から横線をすべて取り除いてできるグラフを, 縦$G_{1}$線をすべて取り除いてできるグラフを$G_{2}$とする．

図 4: 一般の単体分割の場合の最適応答

定理 2 $[0, m]\cross[0, n]$ 格子の任意の単体分割に対して，最適応答 $F$ のセレクション方向保存であるための必要十分条件は折れ線 $(fi(1), 1),$ $(fi(2), 2),$部分グラフに，折れ線 $(1, f_{2}(1)),$ $(2, f_{2}(2)),$$\ldots,$$(m, f_{2}(m))$

が$G_{2}$$\ldots,$$(fi(n), n)$ が$f$が$G_{1}$のの部分グラフになることである．
$(fi(j),j)$ が$(i,j)=$証明．必要条件 : 折れ線 $(fi(1), 1),$の部分グラフとする．
$(f_{1}(j)+1, j)$ における方向保存条件は，$(i, j)$ にセル連結な任意の $(i’, j’)$ 対して $fi(j’)\leq i’$が成立することであるが，そのうち $j’=j+1$ なるものは $i’=fi(j),$ $fi(j)+1,$ $fi(j)+2$ の高々3 つである．Case 1: $(fi(j), j+1)$ が $(fi(j)+1, j)$ とセル連結な場合は $fi(j+1)\leq fi(j)$ が得られる．Case 2: $(f_{1}(j),j+1)$ が $(fi(j)+1,j)$ とセル連結でない場合は $fi(j+1)\leq fi(j)+1$$(i,j)$ にセル連結な$(i, j)=(fi(j)-1,j)$ における方向保存条件は，が得られる．同様に，$\ldots,$$G_{1}$

143
任意の $(i’, j’)$ 対して $f_{1}(j’)\geq i’$ が成立することであるが，そのうち $j’=j+1$ なるもの
は $i’=fi(j)-2,$ $fi(j)-1,$ $fi(j)$ の高々3 つである．Case 3: $(fi(j),j+1)$ が $(fi(j)-1, j)$とセル連結な場合は $fi(j+1)\geq fi(j)$ が得られる．Case 4: $(fi(j), j+1)$ が $(fi(j)-1, j)$とセル連結でない場合は $f_{1}(j+1)\geq f_{1}(j)-1$ が得られる．
$(fi0+1),j+1\rangle$$(f_{1}(j),j_{J}^{\tau}\langle f_{1}\circ.+1)j+1)X(1^{*}$$口_{}\oint\rangle,j\}\ovalbox{\tt\small REJECT}_{(f_{1}(j),j)}$

図 5: 2 重丸が $(fi(j+1), j+1)$ で，白丸が $(fi(j)\pm 1, j)$ である．
$(fi(j+1), j+1)$ が取りうるのは黒丸の点である．
以上の結果を Case 1,3, Case 1,4, Case 2,3, Case 2,4 の 4 つに場合分けしたものが図 5$(fi(j), j)$ と $(fi(j+1), j+1)$ を結ぶ辺は$f_{i}(j)$ がの上段であり，に属する．また，$G_{1}$$0$

または $m$ のときは上の不等式の一部だけを考慮すればよく，図 5 の下段になり，やはり延長した辺はに属する． についても同様である．以上の議論の逆をたどれば，十分条件であることも分かる．
$G_{1}$$G_{2}$$\blacksquare$

注意 $1x\sim x’$ の代わりに$f_{2}(i+1)=f_{2}(i)$$||x’-x||_{\infty}\leq 1$を採用すると，方向保存条件は $fi(j+1)=fi(j)$ ,となる (図 6).

図 6: $x\sim x’$ の代わりに $||x’-x||_{\infty}\leq 1$ とすると，最適応答は定数になってしまう．

注意 2 単体分割は後付で導入したものであり，双行列ゲームの純戦略均衡の存在を保証するためには，方向保存条件を満たすような最適応答のセレクションと単体分割を見つければよいことになる．

144

3

非協力$n$

本節では非協力

人ゲームに対する方向保存条件$n$

人ゲームの最適応答に対して，方向保存条件と単体分割の関係を考$X$ をそれらの察する．ここでは，プレイヤー の純戦略集合を $X_{i}=\{0, \ldots, m_{i}\}$ とし，$i$の利得関数と最適応答をそれぞれ $r_{i}(x)$ ,$F_{i}(x_{-i})=\{x_{i}\in X_{i}|r(x_{i}, x_{-i})\geq r(y_{i}, x_{-i})\forall y_{i}\in X_{i}\}$$F(x)=\Pi_{i=1}^{n}F_{i}(x_{-i})$
とおく．とし，このとき，純戦略 Nash 均衡は $x\in F(x)$ と表現できる．
格子の Freudenthal 分割を考える．即ち，置換に対しそこで先ず，直積集合，$X_{-i}=\Pi_{j\neq i}^{n}X_{j}$とおく．プレイヤー$i$$\Pi_{i=1}^{n}[0, m_{i}]$$\sigma\in \mathfrak{S}_{n}$とおくと，$S_{\sigma}=co\{O, e_{\sigma(1)}, e_{\sigma(1)}+e_{\sigma(2)}, \ldots, e_{\sigma(1)}+e_{\sigma(2)}+\cdots+e_{\sigma(n)}\}$$\{S_{\sigma}|\sigma\in \mathfrak{S}_{n}\}$は格子を構成する全ての超立方体をこの方法で単体分割して得られたものを Freudenthal 分割とよぶ．
$[0,1]^{n}$の単体分割を与える．

$\Pi_{i=1}^{n}[0, m_{i}]$$x\sim x’$ であるための必要十分条件は，比較可能
補題 1 Freudenthal 分割に対し，$(x\leq x’$または $x\geq x’)$ かつ $||x-x’||_{\infty}\leq 1$ が成り立つことである．

定理 3格子の Freudenthal 分割をとるとき，最適応答 $F$ のセレクション方向保存であるための必要十分条件は (7) を満たすことである．
$\Pi_{i=1}^{n}[0, m_{i}]$$f_{i}(x_{-i})\leq f_{i}(x_{-i}+d_{-i})\leq f_{i}(x_{-i})+1 \forall x\in X, \forall d\in\{0,1\}^{n}, \forall i$.

$f$が

(7)

2 次元の場合 (命題 3) と同じように，Freudenthal 分割を回転したものを考え，補題 1の何れか一方として，や定理 3 と同様の結果を導くことができる．つまり， を か置換に対して$e_{i}’$$e_{i}$$-e_{i}$$\sigma\in \mathfrak{S}_{n}$$S_{\sigma}’=co\{O, e_{\sigma(1)}’, e_{\sigma(1)}’+e_{\sigma(2)}’, \ldots, e_{\sigma(1)}’+e_{\sigma(2)}’+\cdots+e_{\sigma(n)}’\}$とおくと，$\{S_{\sigma}’|\sigma\in \mathfrak{S}_{n}\}$$\mathfrak{S}_{n}\}$は co $\{\sum_{j\in J}e_{j}’|J\subset N\}$の単体分割を，$\{S_{\sigma}’+\sum_{e_{j}’=-e_{\dot{2}}}e_{j}|\sigma\in$

は $[0,1]^{n}$ の単体分割を与える．これを平行移動することにより $\Pi_{i=1}^{n}[0, m_{i}]$ 格子を構成する全ての超立方体を分割したものを一般 Freudenthal 分割とよぶ．また，格子点集
合 $\{\sum_{j\in J}e_{j}’|J\subset N\}$ #こ$\sum_{j\in I}e_{j}’\preceq\sum_{j\in J}e_{j}’\Leftrightarrow I\subset J$

により半順序を入れ，格子点$\Pi_{i=1}^{n}\{0,1, \ldots, m_{i}\}$全体に半順序$\preceq$を拡張しておく．

$x\sim x’$ であるための必要十分条件は，比較可能
補題 2 一般 Freudenthal 分割に対し，$(x\preceq x’$

または $x\succeq x’)$ かつ $||x-x’||_{\infty}\leq 1$ が成り立つことである．

145
定理 4

格子の一般 Freudenthal 分割をとるとき，最適応答 $F$ のセレクションが方向保存であるための必要十分条件は，任意の $x\in X$ と任意の $d \in\{\sum_{j\in J}e_{j}’|J\subset N\}$に対して (8) が成立することである．
$\Pi_{i=1}^{n}[0, m_{i}]$

$f$

(8)

$\{\begin{array}{l}f_{i}(x_{-i})\leq f_{i}(x_{-i}+d_{-i})\leq f_{i}(x_{-i})+1 if e_{i}’=e_{i},f_{i}(x_{-i})\geq f_{i}(x_{-i}+d_{-i})\geq f_{i}(x_{-i})-1 if e_{i}’=-e_{i}.\end{array}$

例 1 $n=3$ で $e_{1}’=e_{1},$$e_{2}^{l}=e_{2},$$e_{3}’=-e_{3}$$\{i, j\}=\{1,2\}$ として，不等式 (8) は次のとき，のようになる．
$f_{i}(x_{j}, x_{3})\leq f_{i}(x_{j}+1, x_{3}-1), f_{i}(x_{j}+1, x_{3}))f_{i}(x_{j}, x_{3}-1)\leq f_{i}(x_{j}, x_{3})+1,$.

$f_{3}(x_{1}, x_{2})-1\leq f_{3}(x_{1}+1, x_{2}+1), f_{3}(x_{1}+1, x_{2}), f_{3}(x_{1}, x_{2}+1)\leq f_{3}(x_{1}, x_{2})$4単調写像の不動点定理
本節では，単調写像の不動点定理 (Tarski) を紹介し，それを双行列ゲームに適用して得られる結果と前節の結果を比較する．
半順序集合の最小上界と最大下界が存在すで，任意の $y\in X$ に対してるものを束とよぶ．束 は，任意のが最小上界と最大下界をもつとき，完備で$(X, \preceq)$$x,$$X$あるという．束して，$y\preceq y’$$X$$x,$ $y$$Y\subset X$$x\preceq x’$から $X$ への集合値写像 $F$ は，ならば，任意の $y\in F(x)$ に対なる $y’\in F(x’)$ が存在するとき，単調であるという．

(Tarski [10]) 完備束 $X$ 上の単調な集合値写像 $F$ は不動点をもつ．すなゎち，$x\in F(x)$ なる $x\in X$ が存在する．
定理 5

Tarski の不動点定理を用いて，最適応答が単調性をもつ非協力均衡をもつことを示すことができる．本節でも， や$X_{i}$

定理 6(Topkis [11]) 写像$f_{i}$$X$

人ゲームは純戦略 Nash
は前節のそれと同じとする．
$n$: $X_{-i}arrow X_{i}(i=1, \ldots, n)$ が次の単調性を満たすとする．
(9)$x_{-i}\preceq x_{-i}’ \Rightarrow f_{i}(x_{-i})\preceq f_{i}(x_{-i}’)$$f_{i}(x_{-i})=x_{i}(i=1, \ldots, n)$ なる $x\in X$ が存在する．
このとき，$X=X_{1}\cross X_{2}$ に通常の大小関係で半順序を入れると，条件
プレイヤーが 2 人の場合，(11) は次の (12) になり，最適応答が単調増加であることを意味する (図 7).

$X_{2}\leq x_{2}’\Rightarrow f_{1}(x_{2})\leq f_{1}(x_{2}’) , x_{1}\leq x_{1}’\Rightarrow f_{2}(x_{1})\leq f_{2}(x_{1}’)$

.

(10)

146

$\circ$$\circ$$P_{1}$

図 7: 最適応答が単調増加ならば純戦略 Nash 均衡が存在する．
$x\preceq x’$を

$x_{1}\leq x_{1}’$

かつ $x_{2}\geq x_{2}’$ で定義すると，(11) は次の (13) になり，最適応答が単調減少であることを意味する．
$x_{2}\geq x_{2}’\Rightarrow f_{1}(x_{2})\leq f_{1}(x_{2}’) , x_{1}\leq x_{1}’\Rightarrow f_{2}(x_{1})\geq f_{2}(x_{1}’)$

.

(11)

前節の命題 1 と命題 2 では，増加 (減少) 量が高々 1 の単調な最適応答を説明できたが，本節の (12) と (13) ではより広い範囲の単調な最適応答を説明できる．しかしながら，単調写像の離散不動点定理では，単調でない最適応答を取り扱うことができない．

5ブール代数上の縮小写像に対する離散不動点定理
本節では縮小写像の離散不動点定理について簡単に説明する．ブール代数 {0,1} 上の行列をプール行列とよぶ．行列の和や積は通常の計算規則と同じで，それらの成分の和や積はブール代数に従うものとする．また，固有値 $(\in\{0,1\})$ や固有ベクトルも普通に定義する．写像 : $\{0,1\}^{n}arrow\{0,1\}^{n}$ に対して，関係行列 $B(f)$ $:=(b_{ij})$ を次で定義する．
$f$$b_{ij}:=\{\begin{array}{l}0, f_{i} が x_{j} \#こ依存しない場合 1, その他．\end{array}$

関係行列の最大固有値が$0$のとき， を縮小写像とよぶ．
$f$定理 7 (Robert [7]) 縮小写像 $f$ : $\{0,1\}^{n}arrow\{0,1\}^{n}$ は唯一の不動点をもつ．

Shih-Dong [9] は離散微分を用いて，定理 7 を局所的縮小写像に拡張した．さらに，Richard[8] は Shih-Dong の離散不動点定理を整数区間の直積 $X=\Pi_{i=1}^{n}X_{i}$ 上の写像に拡張した．それらから次の 2 つの定理が容易に導かれる．
定理 8
いても(川崎 [4])$f_{\sigma(i)}$

$X$

上の写像

$f$について，ある置換$\sigma$があって，どの $i=1,$$f$ は唯一の不動点をもつ．
が $x_{\sigma(j)}(j\geq i)$ に依存しなければ，$\ldots n$につ147
定理 9(川崎 [4]) 最適応答 $F$ のセレクション $f=(fi, \ldots, f_{n})$ の変数と関数の番号を適当に並べ替えたとき， が より若い番号のプレイヤーの戦略にしか依存しないならば純戦略 Nash 均衡が存在する．また， が一点集合の場合は，純戦略 Nash 均衡は一意に決$f_{i}$$i$$F$まる．

定理 8 とタイプ (B) やタイプ (M) の離散不動点定理との関係は不明である．また，定理

9 の仮定はかなり強いが，完全情報をもっ展開形ゲームに対する Kuhn の定理を定理 9 で説明できる (川崎他 [5][6]).

参考文献[1] D. GALE, The Game of Hex and the Brouwer Fixed-Point Theorem, The American
Mathematical Monthly, 86, No. 10, (1979) 818-827.
[2] T. IIMURA,
discrete fixed point theorem and its applications, J. Math. Econom.,
39 (2003), 725-742.
$A$[3] T. IIMURA, K. MUROTA AND A. TAMURA, Discrete fixed point theorem reconsidered,J. Math. Econom., 41 (2005), 1030-1036.

[4] 川崎英文，縮小写像の離散不動点定理とその応用，京都大学数理解析研究所講究録 1682$(2010)163-167.$「不確実不確定性下での意思決定過程」，ed. 土肥正，

[5] 川崎英文，吉良知文，縮小写像の離散不動点定理と展開形ゲーム京都大学数理解析研究
所講究録 1726 「最適化モデルとアルゴリズムの新展開」，ed. 梅谷俊治，$(2011)33-38.$[6] H. KAWASAKI, A. KIRA, AND S. KIRA, An application of a discrete fixed point
theorem to a game in expansive form, to appear in Asia-Pacific Journal of Operational
Research.

[7] F. ROBERT, Discrete Itemtions: A Metric Study, Springer, Berlin, (1986).
[8] A. RICHARD, An extension of the Shih-Dong’s combinatorial fixed point theorem,
Advances in Appl. Math., 41 (2008), 620-627.

[9] $M$ .-H. SHIH AND J.-L. DONG, combinatorial analogue of the Jacobian problem inautomata networks, Advances in Appl. Math., 34 (2005), 30-46.
$A$[10] A. TARSKI,
lattice-theoretical fixpont theorem and its applications, PacificMath., 5 (1955), 285-309.
$A$

$J.$

148
[11] D. TOPKIS, Equilibrium points in nonzero-sum -person submodular games, SIAM
J. Control Optim., 17 (1979), 773-787.
$n$[12] Z. YANG, Discrete fixed point analysis and its applications, Joumal of fixed point
theory and applications, 6 (2009) 351-371.