134

数理解析研究所講究録
第2078巻 2018年 134-140

縮小写像の離散不動点定理と純戦略均衡

Discrete fixed point theorems for contraction

mappings and pure‐strategy equilibria
川崎英文*HIDEFUMI KAWASAKI $\dag er$

九州大学大学院数理学研究院
FACULTY OF MATHEMATICS, KYUSHU UNIVERSITY

Abstract

In [1], the author presented a discrete fixed point theorem for contraction mappings as acorollary of Richard‐Shih‐Dong \mathrm{s} discrete fixed point theorem for local contraction mappings[2]. He also applied thc former theorem to an n‐person strategic gamc. However it didn’t
fully utilize the advantage of the latter theorem. In this paper we directly apply the lattertheorem to the n ‐person strategic game.

1

はじめに

著者は [1] において,Richard‐Shih‐Dong の離散不動点定理の系として整数区間上の縮小写像に対する離散不動点定理を与え,それを n 人戦略形ゲームの最適応答写像に適用することにより,唯一の純戦略 Nash 均衡をもつゲームを提示した.しかしながら,その手法は Richard‐Shih‐Dong の離散不動点定理の長所を十分に生かしていなかった.本稿ではRichard‐Shih‐Dong の離散不動点定理を直接 n 人戦略形ゲームに適用することを図る.

2

Robert の離散不動点定理
プール代数の直積 \{0, 1\}^{n} をブール束という.Robert [3, 1986] はプール束からそれ自身への縮小写像に対して離散不動点定理を与えた.本節ではRobertの離散不動点定理を紹介する.

プール代数 \{0 , 1 \} 上の行列をプール行列とよび,行列の和や積は通常の計算方法である.プール束 \{0, 1\}^{n} 上の写像 f=(f\mathrm{l}, . . . , f_{n}) の各成分ゐが変数紛 に依存するかどうかを表したものが関係行列 B(f) := (bij) である.すなわち,
b_{ij}:=\left\{ begin{ar y}{l 0,f_{i}(x_{j},x_{-j})=f_{i}(y_{j},x_{-j})\foral x\in {0,1\}^{n},\foral y_{j}\in {0,1\}. \ 1,\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}. \end{ar y}\right.

*

kawasaki@math.kyushu‐u.ac.jp$\dag er$

本研究は JSPS 科研費 \mathrm{J}\mathrm{P}16\mathrm{K}05278 の助成を受けている.

(1)

135

0 , 1要素からなる n 次行列 B= (bij)

1 のとき i からに対して,点集合を \{ 1, . . . , n\} とし, b_{ij}へ有向枝を引いて得られる有向グラフをで表す.
をの連結グラフとよぶ.つfj\mathrm{r}(B)\mathrm{r}(B(f))=

まり,ゐが吻 に依存するとき i から j へ有向枝を引いたものが連結グラフである.
縮小という言葉が意味をもつには,距離のようなものが必要である.
縦ベク トルを d(x, y)x,:=x, y \in\{0, 1\}^{n} に対して,(|x_{1} -y_{1}|, \ldots, |x_{n} -y_{n}|)^{T} \in \{0, 1\}^{n} で定義する.このとき,任意のy\in\{0, 1\}^{n} に対し d(f(x), f(y)) \leq B(f)d(x, y) が成立する.
プール行列 B= (bij) に対して,非零ベク トル u\in\{0, 1\}^{n} と $\lambda$\in\{0 , 1 \} が Bu= $\lambda$ u をみたす

とき, u をブール固有ベク トル, $\lambda$ をプール固有値とよぶ.最大固有値をブールスペク トル半径とよび $\rho$(B) と書く.プール行列は固有値をもち, B\leq C ならば $\rho$(B)\leq $\rho$(C) が成立する.
定理1([3]) プール行列 B=(b_{ij}) について,以下の条件は同値である.
0 . (b) どの主小行列も零行をもつ.(c) 置換行列 P が存在して P^{T}BP は強下三(a) $\rho$(B)0 . (e) 任意の巡回置換 (i\mathrm{i}, i2, . . . , i_{k}) に対し,角行列になる.(d) ある k \leq n があって B^{k}==b_{i_{1}i_{2}}b_{i_{2}i_{3}}\cdots b_{i_{k}i_{1}} =0.
プール束 \{0, 1\}^{n} 上の写像 f は, $\rho$(B) =0 なるブール行列が存在して,任意の x, y\in \{0, 1\}^{n}に対して d(f(x), f(y)) \leq Bd(x, y) が成立するとき,縮小写像とよばれる. f が縮小写像であるための必要十分条件は $\rho$(B(f))=0 である.
定理2

(Robert の離散不動点定理) プール束 \{0, 1\}^{n} 上の縮小写像 f は唯一の不動点をもつ.その不動点を a とすると,ある k\leq n が存在して f^{k}(x)\equiv a.

3

Shih‐Dong の離散不動点定理

Shih‐Dong [4, 2005] はプール束 \{0, 1\}^{n} 上の写像 f=(f_{1}, \ldots, f_{n}) に対し,離散微分 (discretederivative) f'(x)(f_{ij}(x)) を(2) で定義し,すべての点 x \in \{0, 1\}^{n} で $\rho$(f'(x)) =0 が成立す:=るとき, f を局所縮小写像とよんだ.ただし,汐 は x の第 j 成分鞠 をその反転賜 で置き換えた点を表す.また, V_{x}:=\{\overline{X}j |j=1, . . . , n\} を x の直近傍とよぶ.
f_{ij}(x):=\left{\begin{ar y}{l 0,&f_{i}(\overlin{x}^j)=f_{i}(x),\ 1,&f_{i}(\overlin{x}^j)\neqf_{i}(x). \end{ar y}\right.

(2)

補題1

(1)

\displaystyle \maxx\in\{0,1\}^{n}f'(x) =B(f) . (2) 縮小写像は局所縮小写像である.(3) 任意の x\in \{0, 1\}^{n} と y\in V_{x}に対して d(f(x), f(y)) =f'(x)d(x, y) .

定理3(Shih‐Dong [4]) 局所縮小写像は唯一の不動点をもつ.
定理2は大域的な仮定 $\rho$(B(f))=0 から大域的な結論 「唯一の不動点の存在」 を導いたものであるが,定理3は局所的な条件 $\rho$(f'(x))\equiv 0 から大域的な結論を導いた深い結果である.

136

4

Richard‐Shih‐Dong の離散不動点定理
X_{i} (i=1, \ldots n) を整数の有限区間で |X_{i}| \geq 2 なるものとし,X :=X_{1} \times\cdots\times X_{n} を整数区間とよぶ.Richard [2, 2008] はShih‐Dong の離散不動点定理を整数区間に拡張した. x\in X の直近
傍を V_{x}:=\{x\pm e_{i} |i=1, . . . , n\}\cap X で定義する.整数区間 X上の写像 f に対しても (1) で関係行列 B(f) を定義し, $\rho$(B(f)) =0 を満たすとき縮小写像とよぶ.プール束の場合の離散微分(2) の自然な拡張として f'[x, v] :=(f_{ij}[x, v])_{i,j} を次の様に定義する.

f_{ij}[x, v] :=\left\{ begin{ar ay}{l} 0,&f_{i}(x+v_{j}e_{j})=f_{i}(x)\ 1,&f_{i}(x+v_{j}e_{j})\neqf_{i}(x). \end{ar ay}\right.
ただし,

(3)

\{\pm 1\}^{n} は x+v が X に留まるようなベク トルである.また,離散微分より精密な離散ヤコビ行列 (discrete Jacobian matrix) f'(x, v) :=(f_{ij}(x, v))_{i,j} を次式で定義する.
v\in

f_{ij}(x, v) :=\left\{ begin{ar y}{l 0,f_{i}(x)\text{と}f_{i}(x+ve)(\text{は}x_{i}+\underline{v}_{2^{\mathrm{A} \text{に関して同じ側にある}\ 1,\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}. \end{ar y}\right.

(4)

すなわち,ん (x, v) が 0 になるのは次のときである.
v_{j}=1,v_{j}=-1,(f_{i}(x) \leq x_{i}, f_{i}(x+e_{j})\leq x_{i}) or (f_{i}(x)>x_{i}, f_{i}(x+e_{j})>x_{i}) ,(f_{i}(x) \geq x_{i}, f_{i}(x+e_{j})\geq x_{i}) or (f_{i}(x) <x_{i}, f_{i}(x+e_{j})<x_{i}) .

(5)(6) を満たす f を局所縮小写像,(7) を満たすものを広義局所縮小写像とよぶ.

$\rho$(f'[x, v])=0

if x+v\in X .

(6)$\rho$(f'(x, v))=0

if x+v\in X ,

(7)

補題2

離散ヤコビ行列 f'(x, v) , 離散微分 f'[x, v] , 関係行列 B(f)=(b_{ij}) }こついて以下のことが成り立つ.
(a) f_{ij}(x, v) \leq f_{ij}[x, v] \leq b_{ij} \forall i, j.
(b) 縮小写像 \Rightarrow 局所縮小写像 \Rightarrow 広義局所縮小写像.
(c) B(f)= \displaystyle \max
f'[x, v] \geq \displaystyle \max f'(x, v) .
x,x+v\in X x,x+v\in X(d) f がプール束 \{0, 1\}^{n} 上の写像のとき, x+v\in \{0, 1\}^{n} を満たす v\in\{\pm 1\} は x に対して一意に決まり, f'(x, v) , f'[x, v], f'(x) は一致する.
Richard [2] は次の定理4を帰納法で証明した.その最初のステップ |X\mathrm{i}|Shih‐Dong の離散不動点定理である.

=\cdots=|X_{n}| =2 が定理4

(Richard‐Shih‐Dong の離散不動点定理) 広義局所縮小写像は唯一の不動点をもつ.
例1

図1 (1) で定義される \{0, 1, 2\}^{2} 上の写像 f は以下の性質をもつ.
1. 広義局所縮小写像である.2. 局所縮小写像ではない.

3. 不動点以外のどの点 x^{0} から始めても,点列♂ +1 =f(x^{k}) は不動点に収束しない.

137

4. Freudenthal 分割で整数格子を三角形分割したとき,方向保存条件も総和方向保存条件も満たさない.

5. f は半順序 \leq に関して単調でない.
(1)(0,2\hat{)(1,2)(}2,2)((0, ))(0,0)(10)(2,0)\vee^{\backslash }(2)(02)|'\rightar ow(1_{\mathrm{i} 2)\rightar ow(2, )\downar ow(0\upar ow_{0)\leftar ow(1}|_{0)-(2}\downar ow_{0)}(0,1)\rightarrow(\mathrm{l},|)-(2,1)

図1: (1): 写像 f. f(1,1)=(1,1) . (2): 次頁で定義する非同期状態グラフ A(f) .

x写像 f の非同期状態グラフを以下のように定義し A(f) で表す.まず,点集合は X とする.点が不動点でなければ f_{i}(x)\neq x_{i} なる成分があるので,
1. f_{i}(x) が現在地 x_{i} より大きければ x から x+e_{i} に有向枝を引く.
2. f_{i}(x) が現在地 x_{i} より小さければ x から x-e_{i} に有向枝を引く.

補題3

写像 f,証明.

gの非同期状態グラフが等しければ,それらの離散ヤコビ行列は等しい.

A げ ) =A(g)ならば,(8) が成立し,それぞれの対偶をとることにより (9) も成立する.
x_{i}<f_{i}(x) \Leftrightarrow x_{i}<g_{i}(x) , x_{i}>f_{i}(x) \Leftrightarrow x_{i}>9i(x)(8)

x_{i}\geq f_{i}(x) \Leftrightarrow x_{i}\geq g_{i}(x) , x_{i}\leq f_{i}(x) \Leftrightarrow x_{i}\leq g_{i}(x) .

(9)

一方,(5) で f_{ij}(x, v)=0 と同値な条件を与えたが,(8) (9) により,それは gij (x, v)=0 と同値である.故に f'(x, v)=g'(x, v) . 1
例2

図2 (1) で定義される \{0, 1, 2\}^{2} 上の写像 g は以下の性質をもつ.
1. 広義局所縮小写像である.2. 局所縮小写像ではない.
3. 不動点以外のどの点 x^{0} から始めても,点列 x^{k+1}=g(x^{k}) は不動点に収束しない.
4. f は半順序 \leq に関して単調でない.
5.

\displaystyle \max_{x,x+v\in X} g'(x, v)=\left(bgin{ary}l 0&1\ mathr{l}&0 \end{ary}\ight) \displaystyle\max_{x,x+v\inX} g'[x, v]=B(g)= \left(\begin{ar y}{l 1& \ 1& \end{ar y}\right).
,

6. 不等式 d(g(x), g(y)) \leq B(g)d(x, y) は成立しない.

138

(1)

—

(2)

((( 2)1))(0_{1^{2)} \rightar ow(12)-(2, )\downar ow'\downar ow(0,0)|\leftar ow(|0)-(2,0)|,\downar ow(0,1)\rightarrow(1.1)-(2,1)(0,0)(|,0)(2,0)\vee

図2: (1): 写像 g. g(1,1) =(1,1) . (2): 非同期状態グラフ A(g) .

5縮小写像の離散不動点定理
定理4を用いて Robert の離散不動点定理を整数区間 X に拡張できる.

定理5([1]) 整数区間 X 上の写像 f=(f\mathrm{l}, . . . , f_{n}) について,(a) f が縮小写像であるための必要十分条件は,ある置換 $\sigma$ が存在して,どの i=1 , . . . n についても f_{ $\sigma$(i)} が x_{ $\sigma$(j)} (j\geq i) に依存しないことである.(このとき f_{ $\sigma$(1)} は定数関数である.)(b) 縮小写像は唯一の不動点をもち,任意の初期点 x^{0}\in X に対し, x^{k}=f(x^{k-1}) は高々 n ステップで不動点に収束する.

これを n 人戦略形ゲームに適用しよう.戦略 x_{-i}\displaystyle \in X_{-i}=\prod_{j\neq i}X_{j} に対するプレイヤー i の最適応答集合を鑑 (x_{-i}) とする.
定理6([1]) 任意の i に対して,ある f_{i}(x_{-i})\in F_{i}(x_{-i}) が i より若い番号のプレイヤーの戦略にしか依存しないならば,純戦略均衡が存在する.また, F_{i}(x_{-i}) が一点集合の場合は,純戦略均衡は一意に定まる.

6

局所縮小な最適応答写像
定理5や定理6はRichard‐Shih‐Dong の離散不動点定理の局所的な仮定を十分に生かしていない.つまり,局所的な条件 $\rho$(f'(x, v))=0 の代わりに大域的な条件 $\rho$(B(f))=0 を仮定している.

本節では,n人戦略形ゲームの最適応答写像 f について局所縮小写像を詳しく調べる.

定理7

f が局所縮小写像であるための必要十分条件は, x+v\in X なる任意の x\in X, v\in \{\pm 1\}^{n} と任意の巡回置換 $\sigma$= (i_{1}, i_{2}, . . . , i_{k}) に対し,\displaystyle \prod_{j=1}^{k}\{f_{i_{j} (X-i_{J}+v_{i_{r+1} e_{i_{j+1} )-f_{i_{j} (x_{-i_{j} )\}=0(10)が成立することである.ただし, i_{k+1}=i_{1} とし,ゐ の値に影響しない変数 x_{i} は省略した.
また, f が局所縮小写像ならば,任意の a\in X と任意の i, j に対し, f_{i}(x, a) と fj瞬,, a_{-i-j} )のどちらかは定数関数である.ただし,a_{-i-j}

は a から第 i 成分と第 j 成分を除いた点を表す.

139

系1

任意の a\in X と任意の巡回置換 $\sigma$= (i\mathrm{i}, i2, . . . , i_{k}) に対し f_{i_{j}}(x_{i_{\mathrm{j}+1}}, a_{-i_{j}-i_{j+1}})(j=1,\ldots,陶 のどれかが定数関数ならば, f は局所縮小写像である.ただし, i_{k+1} =i_{\mathrm{i} とする.このとき唯一の純戦略 Nash 均衡が存在する.
系22人ゲームの最適応答写像 f= (f_{1}, f2) について以下の条件は同値である.

(a) f は縮小写像である.(b) f は局所縮小写像である.(c) f は広義縮小写像である.(d) f_{1} (x2),f2 (x1) の少なくとも一方は定数関数である.
系33人ゲームの最適応答写像 f が局所縮小写像であるための必要十分条件は, x+v\in X を満たす

任意の x\in X, v\in \{\pm 1\}^{3} と任意の \{i, j, k\}=\{1 , 2, 3 \} に対し,f_{i}(x_{j}+v_{j}, x_{k})-f_{i}(x_{j}, x_{k}) , f_{j}(x_{k}+v_{k}, x_{i})-f_{j}(x_{k}, x_{i}) , f_{k}(x_{i}+v_{i}, x_{j})-f_{k}(x_{i}, x_{j})のどれかは 0 であり,さらに, f_{i}(xj+vx)-f_{i}(xx) , f_{j}(x_{i}+v_{i}, x_{k})-f_{j}(x_{i}, x_{k}) のどちらかが 0 になることである.また,任意の a\in X に対し f_{i}(xa) , fj (x_{k}, a_{i}) , f_{k}(x_{i,j}a) のいずれかが定数関数で, f_{i}(x_{j}, a_{k}) , f_{j}(x_{i}, a_{k}) のどちらかが定数関数ならば, f は局所縮小写像である.このとき唯一の純戦略Nash均衡が存在する.

図3で与えられる3人ゲームの最適応答写像 f は局所縮小写像であるが,縮小写像ではない.
(1)(2)21012012

図3: 3人ゲームの最適応答写像. f_{1} は定数関数で, f_{2}(\blacksquare)\neq f_{2}(\square ) . f3(▲) \neq f_{3}(\triangle) .

図4で与えられた3人ゲームの最適応答写像 f は f_{1}, f_{2} , f3の何れも定数関数でない局所縮小写像であるが,縮小写像ではない.
(2)/へ\backslash

2

10 1 2 3 4 0 1 2 3 4

図4: 3人ゲームの最適応答写像. f_{1}\neq f_{1}(\circ) , f_{2}(\blacksquare)\neq f_{2}(\square ) . f_{3}( ▲ )\neq f_{3}(\triangle) .

140

参老文献

[1] H. KAWASAKI, A. KIRA, AND S. KiRA, An application of a discrete fixed point theorem toa game in expansive form, Asia‐Pacific J. of Operational Research, 30, 1340013 (2013).
[2] A. RICHARD, An extension of the Shih‐Dong’s combinatorial fixed point theorem, Advancesin Appl. Math., 41 (2008) 620‐627.
[3] F. ROBERT, Discrete Iterations: A Metric Study, Springer, Berlin, (1986).

[4] M.‐H. SHIH AND J.‐L. DONG, A combinatorial analogue of the Jacobian problem in au‐tomata networks, Advances in Appl. Math., 34 (2005) 30‐46.