数理解析研究所講究録
第 1990 巻 2016 年 204-212204

相互依存型決定過程 $-1$ ステージモデルー
九州工業大学・大学院工学研究院

藤田敏治

Toshiharu Fujita
Graduate School of Engineering, Kyushu Institute of Technology

はじめに

1

相互依存型決定過程 [3, 4, 6, 8] とは，複数の決定過程から構成され，各決定過程の利得関数が他の決定過程問題群の最適値の関数として定まるものである．このような依存構造が再帰的に与えられ，各決定過程における終端状態に対しては，通常の終端利得関数が割り当てられる．状態推移の立場からは，ノンシリアル動的計画 [1, 9] の一つの具体的モデルと考えられる．この種の相互依存構造により，多角形から凸多面体を構成する問題がうまく扱えることは [7] で示している．
本稿では，2 つの決定過程から構成される相互依存型決定過程で，特に 1 ステージの決定過程のみから構成されるモデルを考える．そして，この種のモデルを用いると，組合せゲーム [5] の必勝法を求める問題が，より容易に取り扱えることを示す．

定式化

2

本稿で扱う相互依存型決定は 2 つの決定過程からなるものである．ここでは，その 2 つをそれ
ぞれ主決定過程，副決定過程と呼ぶこととし，ともに加法型評価の最小化問題である場合について考える．最初に一般の多段決定過程の場合について考え，その後，次節の応用例で用いる 1 ス
テージの場合について結果を与える．

主決定過程と副決定過程

2.1

まず，初期状態
主決定過程$x_{0}\in X\backslash T_{X}$$P(x_{0})$に対する主決定過程問題を考える．

minimizesubject to$[r(x0, uo)+r(x_{1}, u_{1})+\cdots+r(x_{N-1}, u_{N-1})+rG(x_{N})]$$x_{n+1}=f_{XX}(x_{n}, u_{n})$$n=0$ , 1,$u_{n}\in U(x_{n})$$n=0$ , 1,

)

$N-1$

. . . , $N-1$$N=N(x0, u_{0}, x_{1}, u_{1}, \ldots)=\max\{n :x_{n}\not\in T_{X}\}+1$

ただし(1) $X$ は有限状態空間をあらわし， $T_{X}\subset X$ は終了状態集合とする．また， $x_{n}\in X$ は時刻おける状態をあらわし， $x_{N}\in T_{X}$ となる時刻 $N$ で推移は終了する．

$n$に(2) $U$ は有限決定空間をあらわし， $u_{n}\in U$ は時刻 における決定をあらわす．以下，一般に与えられた集合 $S$ に対し， $S$ の部分集合全体をで表す．ここで，写像 $U:X\backslash T$ ぐ
は各非終了状態に対し実行可能な決定全体を与えるものとする．
$n$$2^{S}$(3) $fxx$ : $G_{r}(U)arrow X$ は確定的推移法則をあらわす．ただし，$G_{r}(U)=\{(x, u)|u\in U(x), x\in X\backslash T_{X}\}$$arrow 2^{U}\backslash \{\phi\}$205である．ある聴刻において状態へ推移する．

に対し決定

$x$

$u$

を選んだ際，次の時刻で状態 $f_{XX}(x, u)\in X$(4) $r:G_{r}(U)arrow R$ はコスト闘数をあらわし， $r_{G}:T_{X}arrow R$ は終端コスト関数をあらわす．
醗決定過程は，初期状態 $y0$ 欧
副決定過程$Q(y_{0})$$Y\backslash T_{Y}$minimizesubject toに対し，次で与えられる．
$[q(y_{0}, v_{0})+q(y_{1}, v_{1})+\cdots+q(y_{M-1}, v_{M-1})+qG(y_{M})]$$y_{n+1}=f_{YY}(y_{n\}}v_{n})$$v_{n}\in V(y_{n})$$n=0$ , 1, . . . , $M-1$$n=0$ , 1,

. . . , $M-1$$M=M(y_{0}, v_{0}, y_{1}, v_{1}, \ldots)=\max\{n :y_{n}\not\in T_{Y}\}+1$

ただし(1) $Y$ は膚限状態空間をあらわし，は終了状態集合とする．また， $y_{n}\in Y$ は時刻おける状態をあらわし， $y_{M}\in T_{Y}$ となる時刻 $M$ で推移は終了する．
$T_{Y}\subseteq Y$(2) $V$ は有限決定空間をあらわし， $v_{n}\in V$ は時灘$V:Y\backslash T_{Y}arrow 2^{V}\backslash \{\phi\}$ににおける決定をあらわす．ここで，写像は各非終了状態に対し実行可能な決定全体を専えるものとする．
$n$(3) $f_{YY}$ : $G_{r}(V)arrow Y$ は確定的推移法則をあらわす．ある蒔刻において状態選んだ際，次の時刻で状態 $f_{YY}(y,$

(4)

$n$

$v\rangle\in Y$

$y$

に対し決定

$v$

を

へ推移する．

: $G_{r}(V)arrow R$ はコスト関数をあらわし， $q_{G}:T_{Y}arrow R$ は終端コスト関数をあらわす．

また，状態空間 $X$ と $Y$ の問に確定的推移 :$f_{XY}:G_{r}(U)arrow Y, f_{YX}:G_{r}(V)arrow X$を与える．ここで， $f_{XY}$ は，主決定過程の状態 欧 $X$ とその時の決定 $u\in U(x)$ に対し，副決定過程の初期状態 $f_{XY}(x, u)\in Y$ を定め， $f_{YX}$ は，醗決定過程の状態 $y\in Y$ とその時の決定 $v\in V(y)$$x$に対し，主決定過程の初期状態 $f_{YX}(y, v)\in X$ を定める．さらに，霊決定過程 $P(x_{0})$ のコスト関
数 $r(x, u)$ および副決定過程 $Q(y_{0})$ のコスト関数 $q(y, のは，翻決定過程問題 Q(f_{XY}(x, u))$ , 主
決定過程問題 $P(f_{YX}(y, v))$ の最適値の関数としてそれぞれ次のように定まるものとする．なお，$f_{XY}(x, u)$ , $f_{YX}(y, v)$ が終了状態のときは，終端利得関数値の関数となる．

$r(x, u)$$=$$\{\begin{array}{ll}R(q_{G}(y_{0})) y_{0}=f_{XY}(x,u)\in T_{Y}R(\min_{v\in t^{\gamma}(yn}[q_{1}(y_{0}, v_{0})+\cdots+q_{G}(y_{M})])n=0^{n},1,\ldots,M^{\rangle}- y0=f_{XY}(x,u)\not\in T_{Y}\end{array}$$q(y, v)$$=$$\{\begin{array}{ll}Q(r_{C}(xo)) x0=f_{YX}(y, v)\in TxQ(\rangle n=0^{n},1,.,N^{)}-1+\cdots+r_{G}(x_{N}\rangle]) x_{0}=f_{YX}(y, v\rangle\not\in T_{X}\end{array}$

ただし，$R:Rarrow R, Q:Rarrow R$
は，あらかじめ与えられた関数とする．

に対しこのとき，解くべき問題は主決定過程側で与えられ，初期状態と表す．なお，再帰的に生じる爾過程を通じて生成される全状態列に対し有限段での終了を仮定$\overline{x}_{0}\in X\backslash T_{X}$する．

$(P, Q, \overline{x}_{0})$

206
2.2

再帰式

主決定過程および副決定過程の最適値関数 $W,$ $Z$ をそれぞれ次で定義する．
$W(x_{0}) = r_{G}(x_{0}) x_{0}\in T_{X}$$W(x_{0}) = n=0,1,.N-1u_{n} \in U.(.x_{n})\min_{)}[r(x_{0}, u_{0})+r(x_{1}, u_{1})+\cdots+r_{G}(x_{N})] x_{0}\not\in T_{X}$$Z(y_{0}) = q_{G}(y_{0}) y0\in T_{Y}$$Z(y_{0}) = \min [q(y_{0}, v_{0})+q(y_{1}, v_{1})+\cdots+q_{G}(y_{M})] y0\not\in T_{Y}$$n=0,1,..,M-1v_{n}\in V.(yn)$このとき， $W,$ $Z$ に対し，それぞれ次の再帰式が成り立つ [2].

$W(x) = rG(x) x\in Tx$$W(x) = \min[r(x, u)+W(f_{XX}(x, u)\rangle] x\not\in T_{X}$$u\in U(x)$$Z(y) = q_{G}(y) y\in T_{Y}$$Z(y) = \min[q(y, v)+Z(f_{YY}(n, v))] y\not\in T_{Y}$$v\in V(y)$ここで，$r(x, u)=R(Z(f_{XY}(x, u , q(y, v)=Q(W(f_{YX}(y, v)))$と表されることに注意すると，次の関係式を得る．
定理 2.1 最適値関数 $W,$

$Z$に対し，次の相互依存型再帰式が成り立つ．

$W(x) = rc(x) x\in T_{X}$$W(x) = \min_{u\in U(x)}[R(Z(f_{XY}(x, u)))+W(f_{XX}(x, u))] x\not\in T_{X}$(1)$Z(y) = q_{G}(y) y\in T_{Y}$(2)$Z(y) = \min_{v\in V(y)}[Q(W(f_{YX}(y, v)))+Z(f_{YY}(n, v))] y\not\in T_{Y}$, (2) の最求めるべき最適値はである．また，(1) の最小値を与える決定 $u\in U$ をに対が相互依存型決定過程
とおくとき，
小値を与える決定 $v\in V$ をする最適政策を与える．定理 2.1 により最適解を求めるための再帰的解法が与えられる．
$\pi_{X}^{*}(x)$$W(\overline{x}_{0})$2.3$(P, Q, \overline{x}_{0})$$(\pi_{X}^{*}, \pi_{Y}^{*})$$\pi_{Y}^{*}(y)$1 ステーンモデル

相互依存型決定過程において，特に 1 ステージの場合について結果を整理しておく．この場合，問題はそれぞれ
主決定過程$P(x_{0})$minimizesubject to$[r(x_{0}, uo)+rG(x_{1})]$$x_{1}=f_{XX}(x_{0}, u_{0})$$u_{0}\in U(x_{0})$

,

207

$|^{1}||(i\rangle|_{1\#_{1}}\mapsto_{||}^{1}\#_{1}(\ddot{n}\rangle\mapsto^{1}*+*E\phi\mapsto\langle iii)\langle iv\rangle(v)(vi)*|+^{+_{キ 1+*|+\neq+}^{1\neq\neq}}$

図 3.1: ゲームの流れ

副決定過程$Q(yo)$

minimizesubject to$[q(y0, vo\rangle+qG(y_{1})]$$y_{\lambda}=f_{YY}(y_{0},v_{0})$$v_{0}\in V(y_{0})$,ただし$r(x, u)$$q(y, v)$

$=$

$=$

$R(q_{G}(y_{0}))$$y_{0}=f_{XY}(x, u)$ 欧 $T_{Y}$$R(m\mathfrak{i}n[q(y_{0}, vo)+q_{G}(y_{1})])$$y_{0}=f_{XY}(x, u)\not\in T_{Y_{\rangle}}$$\{$$Q(r_{G}(x_{0}))$$x_{0}=f_{YX}(y, v)\in T_{X}$$Q(ft1in[r(x_{0}, u_{0})+rG(x_{1})])$$x_{0}=f_{YX}(y, v)\not\in T_{X}$$\{$となり，したがって再帰式は次で与えられる．
系 2.1$W(x) = rG(x) x\in T_{X}$$W(x) = \min[R(Z(f_{XY}(x, u)))+r_{G}(f_{XX}(x, u))] x\not\in T_{X}$$u\in U(x)$$Z(y) = q_{G}(y) y\in T_{Y}$$Z(y) = \min_{v\epsilon V(y)}[Q(W(f_{YX}(y, v)))+q_{G}(f_{YY}(n, v))] y\not\in T_{Y}$3

ピラミッドゲーム必勝法への応用

3.1

ピラミッドゲームとはここで扱うピラミッドゲームとは，2 人対戦のいわゆる組合せゲームの一種である．最初，縦棒が図 3.1(i) のように配置されており，2 人のプレーヤーが次のルールに従って交互に棒を消していく．

1. 白分の順番では，必ず 1 本以上の棒を消さなければならない．
2. 複数の棒を消す場合，それらは一連の隣接した棒でなければならない．

そして，最後の 1 本を消したほうが負けとなる．図 3.1 は，ゲームの経過について表した例である．まず，先手が第 2 層の 2 本を消し，次いで後手が第 3 層の中央 1 本を消す．その後，先手が第3 層の左端 1 本を消し，後手が第 1 層の 1 本を消す．そして，先手が最後に残った第 3 層の右端 1
本を消さなければならなくなり，後手の勝ちとなる．

208

廿

$I^{\neq_{1}}$$\neq^{+_{I}^{1}+_{I}}$$I^{I^{\neq_{g}}}$廿$=$$II^{\cross 1}||x01_{x1}$I$\ovalbox{\tt\small REJECT}$

図 3.3: 同値な状況

一般に，棒の配置は何層でもよく，第

$n$

層には

$n$

本の縦棒を並べる．この種のゲームが，筆者の所属する大学の学生の間でピラミッドゲームと呼ばれていたので，ここでは，その名前で呼ぶこととする．

本稿での興味は，ピラミッドゲームに必勝法が存在するか否かを知ること，そして存在する場
合は，その必勝法を求めることにある．そこで，相互依存型決定過程の 1 ステージモデルを用いて，先手の必勝法を求める問題を考える．

3.2

定式化

基本的な考え方は，主決定過程と副決定過程でそれぞれ先手と後手の手番を表すこととし，各時点でのゲームの状況を状態，プレーヤーの取る手を決定と考え，目的関数によって勝敗を判断させることである．なお，本節では状態および決定については主副決定過程で共通に取られるため，$Y:=X, T_{X}=T_{Y}:=T, V:=U, f_{XX}=f_{YY}:=f, f_{XY}=f_{YX}:=g$とおき，共通の記号 $X,$ $T,$ $U,$ $f,$ を定める．
一般に 層のピラミッドゲーム (図 3.2) を扱うこととする．
最初に状態および状態空間について考える．図 3.3 に示される 4
$g$

$|$

$p$

$||$

I

tiers
つの状況は，一見異なるものであるが，その後のゲーム展開を考えれば実は同値な状況である．これらは，いずれも 「 本単独で存在する縦棒が 1 か所と 2 本の縦棒が並んで存在する所が1 か所である」 という点で同じなのである．すなわち，ゲームを
図 3.2: 層ゲームの初期配置
考えるうえで必要な情報は，各時点で何本の縦棒が隣接して存在しているか，そして，それらが何か所あるか，である．縦棒が残っている場所についての情報は，本質的に不要なのである．したがって，状態は 次元ベクトルで表現でき，状態の $x_{n}(n=1,2, \ldots,p)$ が本並びの存在する個数を表すとする．状態空間は次で与えられる．
$1$$\ovalbox{\tt\small REJECT}|$

$|$

’

$p$

$|$

$p$

$(x_{1}, x_{2}, \ldots, x_{p})$

$p$

$n$

$X = \{(x_{1}, x_{2}, \ldots, x_{p})|x_{i}=0, 1, 2, \cdots, i=1, 2, p\}.$初期状態は $(1,1, \ldots, 1)$ であり，図 3.3 の状況は $(1,1,0)$ と表される．なお，状態 (1,0,0, . . . , 0)は，1 本単独で存在する縦棒が 1 か所のみとなり，この状況がプレーヤーの手番に回ってきたときは，最後の 1 本を消す以外に選択肢はない．すなわち，負けが決定した状態なのである．このことから，終了状態が定まり$T=\{(1,0,0, \ldots, 0)\}\subset$ $X$ .
$2^{nd}$とおくことができる．

次に決定について考える．図 3.4 は，ある手番における 1 つの縦棒の消し方であるが，このように各プレーヤーが取る手は
3 つの数値で定まる．すなわち，何本並びの縦棒を対象にする$4^{tb}$$\ovalbox{\tt\small REJECT}arrow+11$

–
$6$

bars

のか，そして，その何本昌から何本目を消すのか，で定まる．図 3.4: 棒の消し方 (例)209
よって，決定を 3 次元ベクトル本並びの列においてで表すこととし，これが本目までを消す」 を意味するものとする．例えば，図 3.4 の決定は $(6, 2, 4)$ となる．
以上より，決定空間は次で与えられる．
$(u_{1}, u_{2}, u_{3})$本臼から$r_{u_{1}}$$u_{2}$$u_{3}$$U = \bigcup_{n=1}^{p}U_{n},$ただし$U_{n} = \{(u_{1}, u_{2}, u_{3})|u\leq\leq u_{1}.-.u_{2}+1u_{2},u_{3}=1,2u_{2}<\frac{nn}{u2}+1u1=,\cdot\} i=1, 2, \cdots, p$

は 本並びの列に対する決定全体を表している．また，である．
の定義内には，左右対称
な消し方を除く条件が含まれている．決定 $(6, 2, 4)$ と決定 $(6, 3, 5)$ は，ともに 6 本並びの列を 1 減
少させ，1 本単独および 2 本並びの列を 1 ずつ増加させるという意味で同値であり，簡方を考慮す
る必要はないのである．
さて，決定翻約 (実行可能な決定全体) についてであるが，基本的には$U_{n}$$n$$U_{n}$$U(x)= \bigcup_{n;x_{n}\geq 1}U_{n}, x=(x_{1}, x_{2}, \ldots, x_{l)})\in X$

で与えられることが容易にわかる．ここで注意したいのは，状態 $(0, O, 1)$ に対する実行可能な決
定 $(3, 1, 3)$ は，負ける必要がないときにわざと負ける手になっている点である．このような手を含めることは，問題の性質上，兄長になるため省略したい．よって，状態 $x=(x_{1}, x_{2}, \ldots, x_{p})$ が$x_{1}=0$

かつ $\sum_{i=2}^{p}x_{i}=1$ を満たすとき， $x_{n}=1$ なる $n$ に対しては$U_{n}$

次のように置き換えて考えるものとする．
$U_{n} arrow U_{n}\backslash \{(n, 1, n)\}.$

各決定過程内の状態推移 $f$ については，今回の定式化において終端利得の役劉が不要であることから，ダミーの終了状態への推移を人為的に作っておく．
$f(x, u)=(O, 0, \cdots, 0) , x\in X, u\in U(x)$ .

なお，決定剃約の定め方ににより，必ず状態 $(1, 0, \cdots, 0)$ へたどり着き，この状態で停止するた
め，決定過程間の推移 によって状態 $(0_{\}}0, \cdots, 0)$ を生じることはない．これを終了状態に追舶する．すなわち，改めて$g$$T=\{(1,0, \cdots, 0), \langle 0,0, 0)\}$とおく．また，ゲームのルールにより，決定過程問の状態推移 $g(x, u)=(x_{1}’, x_{2,}’x_{p}’)$ , $(x$ 欧$X,$ $u\in U(x))$

は次のように定まる．

$x_{i}’=\{\begin{array}{ll}x_{i}-1 (i=u_{1})x_{i}+1 [Matrix]x_{i}+2 (i=u_{2}-1=u_{1}-u_{3})x_{i} (その他 ).\end{array}$210
最後に利得関数を定める．ここでは，目的関数の値が，勝ち状態 (必勝法あり) であれば を，負け状態 (必勝法なし) であれば 1 となるようにする．終端利得関数についてはダミー状態に対$0$

しては役割が不要なため

$0$

とし，

$r_{G}(x)=q_{G}(x)$$=$$\{\begin{array}{l}1 x=(1,0, \cdots, 0)0 x=(0,0, \cdots, 0)\end{array}$

とおく．利得関数は$R(\alpha(x, u))$$=$$\{\begin{array}{l}0 \alpha(x, u)=1(=1-\alpha(x, u)) ,\end{array}$1$\alpha(x,u)=0$

ただし$\alpha(x, u) = W(g(x, u))(=Z(g(x, u)))$$=$$\{\begin{array}{ll}rc(x_{0}) x_{0}=g(x, u)\in T\min_{uo\in U(xo)}[r(x_{0}, u_{0})+r_{G}(x_{1})] x_{0}=g(x_{\rangle}u)\not\in T\end{array}$とし， $r(x, u)=q(x, u)=R(x, u)$ とおく．

以上より，相互依存型決定過程を構成する 2 つの決定過程が全く同じものとなるため，再帰式
は共通となり，かつダミー状態に対する終端利得が であることから次で与えられる．
$0$$W(x) = rG(x) x\in T$$W(x) = \min_{u\in U(x)}[R(\alpha(x, u x\not\in T.$

特に， $x\not\in T$ に対しては， $R(\alpha(x, u))=1-\alpha(x, u)=1-W(g(x, u))$ となるため$W(x) = r_{G}(x) x\in T$$W(x) = \min_{u\in U(x)}[1-W(g(x, u x\not\in T$

である．この再帰式を用いて $W(1,1, \ldots, 1)$ を求め，それが

3.3

$0$

のとき，先手に必勝法が存在する．

数値例

例 3.1 (2 段ゲーム) $p=2$ で，初期状態は $(1, 1)$ である．まず，終了状態に対しては $W(1,0)=1$である．次に $U(1,1)=\{(1,1,1\rangle, (2,1,1),$ $(2,1,2)\}$ より$W(1,1)$$=$$\min_{u\in U(1,1)}[1-W(g((1,1), u))]=\min[(1-W(O, 1 (1-W(2,0)),$ $(1-W(1,0))].$

ここで $U(O, 1)=\{(2,1,1 U(2,0)=\{(1,1,1)\}$ より$W(0,1)$$=$$\min_{u\in U(0,1)}[1-W(g((0,1), u))]=1-W(1,0)=1-1=0,$$\pi^{*}(0,1)=(2,1,1)$$W(2,0)$$=$$\min_{u\in U(2,0)}[1-W(g((2,0), u))]=1-W(1,0)=1-1=0,$$\pi^{*}(2,0)=(1,1,1)$

よって$W(1,1)$$=$min[(l–O), (1–0), (1–1)] $=0,$$\pi^{*}(1,1)=(2,1,2\rangle.$

以上より，必勝法は存在し，先手は最初に 2 本並び列において 1 本旨から 2 本目を消せばよい

口

.

211
例 3.2 (3 段ゲーム) $p=3$ で，初期状態は $(1, 1, 1)$ である．一般に $k=2$ , 3, . . . ,$W(O, \ldots, 0,1, 0kt1\backslash \downarrow, .

.

.

, 0)=0, \pi^{*}(0, .

.

.

, 0,1, 0kth\downarrow, .

.

.

$p$

に対し

, 0)=(k, 1, k-1)$$W(1_{r},0, \ldots, 0,\lambda,0, \ldots, 0)ktk\downarrow=0, \pi^{*}(1,0, \ldots,0^{kth}1_{\}}0, \ldots, 0)\downarrow=(k, 1, k)$が成り立ち， $l=1$ , 2,

$p$

に対し

$v(2l+1,0,0, \ldots, 0)=1, v(2l, 0, O_{\}}\ldots, 0)=0, \pi^{*}(2l, 0,0, \ldots,0)=(1,1,1)$が成り立つことを利用する．まず，終了状態に対しては $W(1,0,0)=1$ である．次に $U(1,1,1)=$$\{(1,1,1)$ , $(2,1,1)$ , $(2,1,2)$ , $(3,1,1)$ , $(3,1,2)$ , $(3,1,3)$ , $(3,2,2)\}$ より$W(1,1,1)$$[1-W(g((1,1,1), u))J$$\min$$=$$u\in U(1,1,1)$$\min[(1-W(O_{:}$ l, 1$=$$(1-W(2,0,1$$(1-W(1,0,1$$(1-W(1,2,0)) , (1-W(2,1, O)) , (1-W(1,1, O)) , (1-W(3,1, O))].$
ここで， $W(1,1, O)=W(1,0,1\rangle=0 であり，U(O, 1,1)$$\langle$$=$$\{(2,1, i),$$(2,1,2),$ $(3,1,1),$ $(3,1,2)$ ,3, 1, 3), $(3_{:}2, 2)\}$ より$W( O, 1,1) = \min [1-W(g((0_{\}}1,1), u))]$$u\in(\chi(0,1,1)$$= \min[(1-W(1,0,1 (1-W(O, 0,1 (1-W(O, 2,0))$ ,$(1-W(1,1, O)) , (1-W(O, 1, O (1-W(2,1,0))].$$W(1,1,0)=W(1,0,1)=W(O, 1, O)=W(0,0,1)=0$ で， $U(O, 2,0)=\{(2,1,1)$ , $(2,1,2)\}$
より$W(O, 2,0)$$=$$\min_{u\epsilon U(0,2,0)}[1-W(g(\langle O, 2,0),$$= \min[(1-W(1,1,0$$u$$(1-W(O,$ $1,$

$O$$= m\mathfrak{i}n[(1-O) , (1-0)] =1.$

さらに， $U(2,1,0)=\{(1,1,1)$ , $(2,1,1)$ ,$(2,1,2)\}$ より$W(2,1,0) = \min [1-W(g((2,1, O), u)\rangle]$$u\in U(2,1,0)$$= \min[(1-W(1,1,0)) , (1-W(3, O, 0)) , (1-W(2,0,0$$\min[(1-0)$ , (1–1), $(1-0)]$

$=$

$=0,$

$\pi^{*}(2,1,0)=(2,1,1)$.

よって$W(0,1,1)$$=$$\min[(1-0)$ , (

$i$

–

$O$

), (1–1), (1–0), (1–0), $(1-0)]$ $=0,$$2r^{*}(0,1,1)=(3,1,1)$.

同様に$W(2,1,0)=0,$$\pi^{*}(2,1,0)=(2,1,1)$ ,$W(O, 1,1)=0,$$\pi^{*}(0,1,1)=(3,1,1)$ ,212$W(2,0,1)=0,$$\pi^{*}(2,0,1)=(3,1,2)$ ,$W(1,2,0)=0,$$\pi^{*}(1,2,0)=(1,1,1)$ ,$W(3,1,0)=0, \pi^{*}(3,1,0)=(2,1,2)$ .
したがって$W(1,1,1)$$=$$\min[(1-0)$ , (1–0), (1–0), (1–0), (1–0), (1–0), $(1-0)]$$=1.$

以上より， $p=3$ のとき，先手に必勝法は存在しない．口

なお，計算機による数値計算の結果， $p=4$ , 5, 6, 8, 9, 10, 12, 13, 14, 16 のとき，先手に必勝法が存在することを確認した．

謝辞
本研究は科研費 $15K05004$ の助成を受けたものである．

参考文献[1] U. Bertel\’e and F. Brioschi, Nonserial Dynamic Programming, Academic Press, New York,1972.
[2] T. Fujita, $R$ -examination of Markov policies for additive decision process, Bulletin ofInformatics Cybernetics, 29, No.1, 51-65, 1997.
[3] T. Fujita, 結合型評価をもつ相互依存型決定過程，京都大学数理解析研究所講究録 1802, 78-84,

2012.
[4] T. Fujita, Associative Criteria in Mutually Dependent Markov Decision Processes, Proceedings of IIAI International Conference on Advanced Applied Informatics (IIAI AAI 2014),
147-150, 2014.
[5] T. Fujita, Sure Ways to Win a Game
Nondeterministic Dynamic Programming Approach–, Bulletin of the Kyushu Institute of Technology. Pure and applied mathematics, 62, 1-14,–

2015.
[6] T. Fujita, 相互依存型マルコフ決定過程 –結合型評価 –, 京都大学数理解析研究所講究録
1939, 189-195, 2015。
[7] 藤田敏治，長友健太郎，折り紙ユニットを用いた凸多面体の構成 –相互依存型決定過程によるアプローチー，京都大学数理解析研究所講究録，1912, 17-25, 2014.

[8] T. Fujita and A. Kira, Mutually Dependent Markov Decision Processes, Journal of Advanced Computational Intelligence and Intelligent Informatics, 18(6), 2014, 992-968.
[9] G. L. Nemhauser, Introduction to Dynamic Programming, Wiley, New York, 1966.