用語と補題

以下，用語をいくつか定義し，簡単な補題を証明する。

特に断らない限り，$m = n$ で初期配列は一意性条件を満たすものとする。 $\vec{a},\vec{a'}$, $\vec{b},\vec{b'}$ などのベクトル表示は， $A,B$ の初期配列の成分のいくつか（$0$ 個，および $m$ 個も含む）を $0$ に変えた配列を表す。

$C = A,B$ に対して，$C'$ は $C$ の相手のプレーヤーを表す。したがって，$\{C,C'\} = \{A,B\}$.

用語

指数：配列 $$ {}^t\!\!\left(\vec{a},\vec{b}\right) = \begin{pmatrix} a_1,&\ldots,&a_m\\ b_1,&\ldots,&b_m \end{pmatrix} $$ に対して，値が $0$でない $a_i$ の個数を（残存している $A$ の都市の個数を） $A$ の指数，値が $0$ でない $b_i$ の個数を $B$ の指数と言うことにする。

EX： $A$, $B$ の指数が $0$ の配列，つまり，$\vec{a} = \vec{b} = \vec{0}$ である配列を，$EX$ と呼ぶことにする。

部分配列： $\vec{c} = \vec{a}$，もしくは，$\vec{c} = \vec{b}$ として，配列 $\vec{c} = (c_1,\ldots,c_m)$ の成分のいくつかを $0$ に変えて得られる $\vec{0}$ でない配列 を，$\vec{c}$ の部分配列という。また，$S = {}^t\!\!\left(\vec{a'},\,\vec{b'}\right) $ に対して，$\vec{a'},\vec{b'}$ がそれぞれ $\vec{a},\vec{b}$ の部分配列であるとき，$S' = {}^t\!\!\left(\vec{a'},\,\vec{b'}\right)$ を $S$ の部分配列という。

安定な配列：部分配列 $S$ が次の条件を満たすとき，$S$ は安定な配列であるという：条件： $C$ が $A,B$ のいずれであっても ${}^C_0 S$ からの（配列としての）帰結が $S$ 自身配列 $S$ が安定ならば，任意の $j=0,1,\ldots p$ に対して ${}^C_jS $ からの帰結も $S$ 自身となる。付随する配列が安定な節点を，安定な節点という。

準安定な配列：配列 $S$ が不等式 $\varphi_A > 0,\,\,\varphi_B > 0$ を満たすとき，$S$ は準安定であるという。付随する配列が準安定な節点を，準安定な節点という。

DSP ： $C$ が $A,B$ のいずれであっても ${}^C_0 S$ からの（配列としての）帰結が $EX$ であるとき， $S$ は $DSP$ であるという。

機会のある状態： $j=0,1,\ldots,p-2$ に対しての ${}^C_j S$ を機会のある状態，付随する状態が機会のある状態である節点を機会のある節点ということにする。

$EX$ は部分配列に含めていないので， $EX$ は安定な配列ではない
$S' = {}^t\!\!\left(\vec{a'},\,\vec{b'}\right)$ が $EX$ でないならば，一意性条件により，$S'$ において $\varphi_A \ne 0,\,\varphi_B \ne 0$.
安定，準安定，$DSP$ などは配列に対して定義されているのであり，節に対しての定義は用語の流用に過ぎない。木が固定されている場合，$S$ が初期配列の部分配列であっても，状態 ${}^A_0 S$, ${}^B_0 S$ が付随する節が存在するとは限らない。例えば，根(に付随する状態）が ${}^A_0 S$ の木には，付随する状態が ${}^B_0 S$ の節は存在しない。

補題

合理的な経路

節点 $u$ の帰結を $v$ とする。$v$ から直前の節点を辿ることにより得られる節点の列を $ v=v_0,v_1,v_2,\ldots,v_N=u $ とする：

帰結の定義により $\varphi^{fl}_C(v_{i+1}) = \varphi^{fl}_C(v_i)$ なので，$\varphi^{fl}_C(v_i) = \varphi_C(v),\quad i=0,1,\ldots,N.$
$i=1,2,\ldots,N$ に対して，節点 $v_i$ で手番のプレーヤー $C$ は，相手の配列を $\vec{0}$ に変えて $EX$ に誘導することもできるので，$\varphi_C(v)\, (=\varphi^{fl}_C(v_i)) \geq 0$.
$u$ が機会のある節点ならば，$N\geq 2$ でありプレーヤー $A,\,B$ は節点 $v_1,v_2,\ldots,v_N$ の少なくとも一箇所で手番になるので，$\varphi_A(v)\geq 0,\,\varphi_B(v)\geq 0$.
機会のある節点からの帰結は，一意性条件により，準安定であるか，もしくは，$EX$.
安定な配列は準安定．［証明］： $S$ は安定な配列であるとする。$C = A,B$ に対して，${}^C_0 S$ が付随する節点（を根とする木を考えて，この木の節点としての）$u$ の帰結を$v$ とすると，$S$ は安定なので $u$ と$v$ には同じ配列が付随している。 $u$ は機会のある節点なので，L1-4 により帰結 $v$ は（したがって $u$ は）準安定であるか，もしくは，$EX$ となる。安定な配列は $EX$ ではないので，$u$ は（したがって，それに付随する配列$S$ は），準安定。

$kl$ の不等式

$S_0 = {}^t\!\!\left(\vec{a},\,\vec{b}\right)$ は初期配列であるとする（したがって，一意性条件を満たす）。

$S_0$ の部分配列 $S'$ で準安定なものが存在するならば，$kl < 1$.
$S_0$ の部分配列 $S'$ で $\varphi_A,\,\varphi_B$ が共に負のものが存在するならば，$kl > 1$.
$kl > 1$ のときには，$S_0$ は $DSP$.

［証明］

$S'$ は準安定なので $\sum \vec{a'} - k\sum \vec{b'} > 0,\,\, \sum \vec{b'} - \ell\sum \vec{a'} > 0$ であり，$\sum \vec{a'} > k\sum \vec{b'} > k\left(\ell \sum \vec{a'}\right)$. よって，$kl < 1$.
$\sum \vec{a'} - k\sum \vec{b'} < 0,\,\, \sum \vec{b'} - \ell\sum \vec{a'} < 0$ なので，$kl > 1$.
（L2-1 により）準安定な部分配列が存在しないので，$EX$ 以外は ${}^C_0 S_0$ の帰結となり得ない。したがって，初期配列 $S_0$ は $DSP$.

帰結

Lemma 1. 　 $S_0 = {}^t\!\!\left(\vec{a},\vec{b}\right)$ の部分配列 $S'$ が準安定ならば，付随する配列が $S'$ である節点 $u$ からの帰結は準安定。［証明］

Lemma 2. 　 $S_0$ の部分配列 $S'$ で準安定なものが存在するならば，初期状態からの帰結は準安定。［証明］

Lemma 3. 　 $S_0$ の部分配列 $S'$ で準安定なものが存在するならば，初期状態からの帰結は安定。［証明］

［Lemma 1 の証明］

$u$ での状態を ${}^C_j S'$ とする。$u$ からパスを $p-j$ 回続けて到達する葉を $v$ として，$u$ から $v$ までの経路上の節点を，$v$ から遡って $v = v_0,v_1,\ldots,v_{p-j} = u$ と表しておき，帰納法により節点 $v_i$ からの（したがって，節点 $u = v_{p-j}$ からの）帰結が準安定であることを確かめる：

$i=0$ の場合： $v=v_0$ は葉なので，帰結はそれ自身であり準安定な配列 $S'$ が付随。
$v_i$ の帰結が準安定と仮定する($i < p-j$)：節点 $v_{i+1}$ で手番のプレーヤーが，
1. パスをした場合：結果は節点 $v_i$ であり，仮定により帰結は準安定
2. 攻撃をした場合：どのような攻撃を選んだとしても，攻撃により $j$ の値は$j=0$ にリセットされるので，攻撃の結果は機会のある節点となる。したがって，L1-4 により，そこからの帰結は準安定
したがって，$v_{i+1}$ の直後の節点からの帰結は，すべて準安定。よって，$v_{i+1}$ からの帰結は準安定。

以上により，$u = v_{p-j}$ からの帰結は準安定。

［Lemma 2 の証明］

先手は $A$ であるとして証明する。$B$ の場合も同様。準安定な部分配列のひとつを $S' ={}^t\!\! \left(\vec{a'},\,\vec{b'}\right)$, プレーヤー $A$ が初手で $\vec{b}$ を $\vec{b'}$ に変えた節点を $v_1$，$v_1$ においてプレーヤー $B$ が $\vec{a}$ を $\vec{a'}$ に変えた節点を $v_2$ とする。

$p\geq 3$ であるか，もしくは，$p = 2$ で $\vec{b'} \ne \vec{b}$ の場合： $A$ がパスをした場合（$\vec{b'} = \vec{b}$ の場合）も含めて，$B$ の手番の節点 $v_1$ は機会のある節点となる。したがって，L1-4 により，$v_1$ からの帰結は $EX$ か準安定かのいずれかである。$v_1$ においてプレーヤー $B$ が $\vec{a}$ を $\vec{a'}$ に変えた場合の帰結は，準安定な節点 $v_2$ の帰結として Lemma 1 により準安定なので，節点 $v_1$ においてプレーヤー $B$ は最終的価値関数が正の値になる選択肢を持つ。したがって，$v_1$ からの帰結が $EX$ となることはない。よって，$v_1$ からの帰結は準安定。

初期状態の節点 $u$ は機会のある節点なので，L1-4 により帰結は準安定か$EX$ のいずれかであり，プレーヤー $A$ は初手で$\vec{b}$ を$\vec{b'}$ に変えて $v_1$ からの準安定な帰結に誘導することができるので，$u$ からの帰結が $EX$ となることはない。よって，初期状態からの帰結は準安定。
$\vec{b'} = \vec{b}$ で $p=2$ の場合：プレーヤー $A$ の初手はパスなので，$v_1$ は機会のある節点ではない。プレーヤー $B$ が攻撃を選んだ場合には状態は機会のある状態に変わるので，攻撃の結果からの帰結は L1-4 により $EX$ か準安定。$B$ は，$\vec{a}$ を $\vec{a'}$ に変えて準安定な節点 $v_1$（したがって，Lemma 1 により帰結も準安定）に誘導することができるので，攻撃をするにしても，$EX$ につながる攻撃を選択することはない。

プレーヤー $B$ がパスを選ぶと $p=2$ なので状態は初期配列のままでゲームは終了する。したがって，$B$ がパスを選ぶのは $\sum \vec{b} - \ell \sum \vec{a} > 0$ の場合のみ。また，$\sum \vec{a} - k\sum \vec{b} \geq \sum \vec{a'} - k\sum \vec{b'} > 0$ なので，パスが合理的である場合には，パスからの帰結は準安定。したがって，$B$ がパスを選ぶ場合も含めて $v_1$ からの帰結は準安定。プレーヤー $A$ は初手でパスにより準安定な帰結に誘導することができるので，初期状態からの帰結は準安定。

［Lemma 3 の証明］

Lemma 2 により初期状態からの帰結 $v$ は準安定。初期状態（の節点，木の根）から $v$ までの経路（帰結の定義により合理的経路）を，$v$ から直前の節点を辿ることにより，節点の列 $v=v_0,v_1,v_2,\ldots,v_p,\ldots$ を作ると，$v_p$ から $v_1$ までの最後の$p$ 個の節点では，パスが合理的選択となる。

$v_p$ での手番を $A$ として証明する。つまり，$v_p$ での状態を ${}^A_0 S$ として証明する。$B$ の場合も同様。

$v_0$ での状態を ${}^C_p S$ とおく。したがって，$v_1,\,v_2$ での状態は，それぞれ ${}^{C'}_{p-1} S,\, {}^C_{p-2} S$ となる. $v$ は $v_1$, $v_2$ の帰結なので $$ \varphi^{fl}_{C'}\left({}^{C'}_{p-1} S\right) = \varphi_{C'}\left(S\right),\quad \varphi^{fl}_{C}\left({}^{C}_{p-2} S\right) = \varphi_{C}\left(S\right) $$ となる。 $S',\,S''$ を，それぞれ $C',\,C$ が（パスでなく）なんかの攻撃を行った場合に得られる $S$ の部分配列とする。パスが合理的選択である結果として次の不等式が成り立つ：

$$ \begin{gather} v_1 \mathrm{ で }\, C'\, \mathrm{が攻撃：} & \varphi^{fl}_{C'}\left({}^C_0 S'\right) \leq \varphi^{fl}_{C'}\left({}^{C'}_{p-1} S\right) = \varphi_{C'}(S)\quad \cdots\cdots (1)\\ v_2 \mathrm{ で }\, C\, \mathrm{が攻撃：} & \varphi^{fl}_{C}\left({}^{C'}_0 S'\right) \leq \varphi^{fl}_{C}\left({}^{C}_{p-1} S\right) = \varphi_{C}(S)\quad \cdots\cdots (2) \end{gather} $$

さらに，一意性条件により，不等式が等号となる場合は排除できる。

次に，状態 ${}^B_0 S$ を根とする木を考え，$i=0,1,2,\ldots,p$ に対して $v'_i$ は根からパスを $p-i$ 回繰り返して得られる節点として，節点の列 $v'_0,v'_1,v'_2,\ldots,v'_p$ を作り，これが $v'_p$ からの合理的経路となることを証明する。

$i$ を，$\varphi^{fl}_A(v'_i) = \varphi_A(S),\, \varphi^{fl}_B(v'_i) = \varphi_B(S)$ となる最大の番号とする。したがって，$v'_i$ から $v'_0$ までのパスの繰り返しは，合理的経路となる。 $v'_{i+1}$ で攻撃が合理的かどうかを調べる：

$v'_{i+1}$ で手番のプレーヤーが $C'$ の場合：攻撃が合理的選択となるためには $\varphi^{fl}_{C'}\left({}^{C}_0 S'\right) \geq \varphi^{fl}_{C'}(v'_{i}) = \varphi_{C'}(S)$ となることが必要だが，これは不等式 $(1)$ により不可能。
$v'_{i+1}$ で手番のプレーヤーが $C$ の場合：攻撃が合理的選択となるためには $\varphi^{fl}_{C}\left({}^{C'}_0 S''\right) \geq \varphi^{fl}_{C}(v'_{i}) = \varphi_{C}(S)$ となることが必要だが，これは不等式 $(2)$ により不可能。

いずれの場合でも攻撃は合理的ではなく，$v'_{i+1}$ においても手番のプレーヤーはパスを選択することになる。したがって，$i = p$ であり，状態が ${}^B_0 S$ の節点からの $p$ 回のパスは，合理的経路を作る。よって，状態 ${}^B_0 S$ からの（配列としての）帰結も $S$ であり，$S$ は安定な配列である。