勝利領域と部分勝利領域の生成

本項では分割型到達可能性ゲームDR( A,{X_r}r∈R)における勝利領域と部分勝利 領域を特定するためのアルゴリズムを定義し、そのアルゴリズムによって求めた 領域が勝利領域と分割勝利領域の性質を満たす事を証明する。

4.6.1 ^{プレイヤー} 0 ^{の勝利領域}

分割型到達可能性ゲームDR( A,{X_r}r∈R)のプレイヤー0の勝利領域を求める。分 割型到達可能性ゲームにおいてプレイヤー0が勝利するためにはx ∈ {X_i}i∈Iにトー クンを動かす必要がある。x ∈ {X_i}i∈I にトークンを動かすためにはx ∈vEである ようなvにトークンを動かす必要があり、そのようなvにトークンを動かすため にはv ∈ v^′Eであるようなv^′にトークンを動かす必要がある。このことから、プ レイヤー0の勝利領域は以下のような関数pre : P(V ) → P(V )を用いて帰納的に 定義できると考えられる。

pre0(Y ) = {v ∈V₀|vE∩Y , ϕ} (4.3) pre1(Y ) ={v ∈V₁|vE ⊆ Y} (4.4) pre(Y ) = pre0(Y )∪pre1(Y ) (4.5)

関数pre(Y )によってプレイヤー0が常にY ⊆V に属する状態に到達できるような

状態の集合を出力することが可能である。部分勝利領域を定義する際に利用する ことから、pr e0 :P(V ) → P(V )およびpre1 :P(V ) → P(V )を併せて定義してお く。これらはそれぞれY ⊆ V に属する状態に到達できる状態を出力する関数であ

るが、pr e0はプレイヤー0の手番を意味する状態の集合を、pre1はプレイヤー1

の手番を意味する状態の集合をそれぞれ出力する関数であり、関数preはこの和 集合を出力するような関数である。

X⁰ = {X_i}i∈I として、

X^ν+1= X^ν ∪pre(X^ν) (4.6)

とする。このとき全序数νに対して

X^ξ = ∪

ν<ξ

X^ν (4.7)

とする。ξ をX^ξ = X^ξ+1となるような最小の序数とする時、X_ξ によって定義さ れる領域はプレイヤー0の勝利領域の性質を満たす。これは一般的な到達可能性 ゲームG( A,X )における勝利領域W₀の定義と同じ方法[13]であり、定理4.1より DR( A,{X_r}r∈R)はX = {x ∈V|x ∈ X_r,X_r ∈ {X_r}r∈R}となるようなG( A,X )と同値の ゲームとなるからである。また、このときW₁= V\W₀となることも知られている。

4.6.2 ^{プレイヤー} 0 ^{の部分勝利領域}

分割型到達可能性ゲームDR( A,{X_r}r∈R)のプレイヤー0の部分勝利領域を求める。

プレイヤー0の部分勝利領域は同プレイヤーの勝利領域を帰納的に求める際に同時 に導出する事が可能である。具体的には、関数pre(Y )に属するような状態とその時 点まで求められていた部分勝利領域を入力に取り、その状態が属する部分勝利領域 を出力するような関数を定めることでこれを実現する。この関数は入力に取る状態 がプレイヤー0の手番であるかプレイヤー１の手番であるかによって異なり、それ ぞれpart0 : (V₀,P(P(V ))) → P(P(V ))およびpart1 : (V₁,P(P(V ))) → P(P(V )) とする。

part0を定義する。プレイヤー0の手番では、プレイヤー0は任意の遷移に従っ

てトークンを動かす事が出来る。従って、あるQ ⊆ Rによる勝利領域W_0Qに属す る状態への遷移を持つ。プレイヤー0の手番を意味する状態はQによる勝利領域 W_0Qに常に到達出来るような戦略を持つことができ、そのような状態もまたW_0Q に属すると考えられる。よってプレイヤー0の手番を意味する状態の部分勝利領 域は

part0(v,{YΓ}Γ∈2^R) ={Y_Γ^ν|∃y ∈vE wit h y ∈YΓ,YΓ ∈ {YΓ}Γ∈2^R} (4.8) によって求める事が出来ると考えられる。ここで{Y_Γ}Γ∈2^Rは既に求まっている部 分勝利領域に相当する。

part1を定義する。プレイヤー1の手番では、プレイヤー0はトークンを動かせ

ない事から特定の戦略を取る事が出来ない。従ってそのような状態をプレイヤー 0の勝利領域W₀に含めるためには遷移先の状態のすべてが勝利領域W₀に含まれ ていなければならない。式(3.1)ではちょうどそのようなv ∈V₁を勝利領域W₀に 含めている事が分かる。プレイヤー1の手番を意味する状態v ∈V₁があるP ⊆ R による部分勝利領域W_0Pに含まれる時は、vの遷移先の状態がO ⊆ Rによる部分 勝利領域W_0Oに含まれ、逆に遷移先の状態を含む勝利領域を構成する全てのOの 和集合はPに一致する必要があると考えられる。この時、vの遷移先の状態を含 む部分勝利領域は複数である可能性があることから、vを含む部分勝利領域を構成

2015年度 修士論文

早稲田大学 基幹理工学研究科 情報理工・情報通信専攻 深澤研究室 するPも複数通り考えられ、それはvの遷移先の状態を含む部分勝利領域を構成 するOの組み合わせ通りだけ存在する。そこでまず、そのようなOの組み合わせ を特定する関数sub : (V,P(P(V ))) → P(P(P(R)))を定義する。

sub(v,{YΓ}Γ∈2^R)= ∏

y∈vE

{Γ|y ∈YΓ} (4.9)

次に特定したOの組み合わせを入力として、実際に部分勝利領域を構成するPを 出力する関数conv :P(P(P(R))) → P(P(R))を定義する。

conv({Γ_i}i∈I)= {γ ∈ R|γ ∈Γ,Γ ∈ {Γ_i}i∈I} (4.10) subとconvを利用する事でpart1を定義する。

part1(v,{YΓ}Γ∈2^R) = {YΓ|Γ ∈conv({Z_i}i∈I),{Z_i}i∈I ∈ sub(v,{YΓ}Γ∈2^R)} (4.11)

ただし、part0,part1で出力される領域には部分勝利領域の定義から外れる領域

が存在する。Γ₁ ⊆ Γ₂ ⊆ Rの関係にあるようなY_Γ1とY_Γ2がpart1によって出力され る時、YΓ₂は実際は含まれるべきではない。なぜなら部分勝利領域の定義より、Γ₂ による部分勝利領域からΓ₁による勝利領域は取り除かれたものとなっている必要 があるからである。従って、以下のような関数cut :P(P(V )) → P(P(V ))を定義 する。

cut ({YΓ}Γ∈2^R) ={YΓ|∄Γ^′∈2^Rwit h Γ^′⊆ Γ} (4.12)

part0およびpart1を利用する事で部分勝利領域を帰納的に定義する。まず部分勝

利領域を初期化する。Γ ∈2^Rに対して以下のような集合を用意する。

{X_Γ}⁰_Γ∈2R = {X_Γ⁰|X_Γ⁰= ϕ,Γ ∈2^R\{r}r∈R} ∪ {X_{⁰_r}|X_{⁰_r} = X_r,r ∈R} (4.13) 初期化された部分勝利領域と関数pre0,pre1,part0,part1,cutを用いて、部分勝利 領域を次のように帰納的に定義する。

X_Γ^ν+1= X_Γ^ν ∪ {y ∈ pre1(X^ν)|X_Γ^ν ∈ cut (part1(y,{XΓ}_Γ^ν_∈2R))} ∪

{y ∈pre0(X^ν)|X_Γ^ν ∈cut (part0(y,{XΓ}_Γ^ν_∈2R))} (4.14) ただしX^ν = {v ∈V|v ∈ X_Γ^ν,XΓ ∈ {X_Γ^ν}Γ∈R}である。また、この時の全ての部分勝利 領域の集合を以下のように表現する。

{XΓ}^ν+1_Γ∈2R = ∪

γ∈2^R

X_Γ^ν+1 (4.15)

全序数νに対して

{XΓ}^ξ_Γ∈2R =∪

ν<ξ

{XΓ}_Γ^ν_∈2R (4.16)

とする。ξをX^ξ = X^ξ+1となるような最小の序数とする時、X_Γ^ξ ∈ {XΓ}_Γ^ξ_∈2Rによっ て定義される領域はプレイヤー0のΓによる部分勝利領域となる。これをX_Γ^ξがプ レイヤー0のΓによる部分勝利領域の性質を満たすことを証明することによって 確かめる。

まず|Γ| =1であるような全てのΓ∈ 2^Rに関して、X_Γ^ξがプレイヤー0のΓによ る部分勝利領域である事を証明する。ただし|Γ|はΓの要素数である。|Γ| = 1よ り、r ∈ Rに対してΓ = {r}である。このとき、部分勝利領域の初期化部分より、

X_r ⊆ XΓである。またv ∈ X_Γ^ξ\X_r となるすべてのvに対して、v ∈ X_Γ^ξv+1\X_Γ^ξv を満 たすような単一のξv < ξが存在する。以上を用いることで、X_Γ^ξがΓによる部分勝 利領域の一部であるという事が以下のように帰納的に証明可能である。

ξ = 1のときv ∈ X_Γ^ξ∩V₀はv^′∈ XΓであるようなv^′ ∈vEを持つ。従ってf₀(v) = v^′ とすれば、vを開始状態とし、この戦略に従う任意のプレイπはX_r に属する状態 を含める。また、v ∈ X_Γ^ξ ∩V₁において、式(4.4)より、X_Γ′ ∈ {X_Γ}Γ∈2^Rのいずれに も属さないようなv^′ ∈vEは存在せず、また式(4.11)よりΓ^′,Γを満たすXΓ^′に属 するようなv^′∈ vEは存在しない。すなわち、vはv^′< X_Γであるようなv^′∈vEを 持たない。従ってこのようなvを開始状態とするとき、任意のプレイπはX_r に属 する状態を含む。このようなX_Γ^ξは分割型到達可能性ゲームDR( A,{X_r}r∈Γ)の勝利 領域に含まれる。従ってX_Γ^ξはΓによる部分勝利領域の一部に含まれる。

ξ ≥ 2のとき、X_Γ^ξがΓによる部分勝利領域の一部に含まれる事を仮定する。こ の時、式(4.3)および式(4.8)より、v ∈ {X_Γ^ξ+1\X_Γ^ξ} ∩V₀はv^′∈ X_Γ^ξを満たすような v^′ ∈vEが存在する。従って仮定よりそのようなvに対して戦略 f₀(v) = v^′を持た せる時、vを開始状態とし、この戦略に従い、かつ勝利領域内では勝利戦略に従う ような任意のプレイπはX_r に属する状態を含む。また式(4.4)および式(4.11)よ り、v ∈ {X_Γ^ξ+1\X_Γ^ξ} ∩V₁はv^′< X_Γ^ξであるような状態v^′∈vEを持たない。従ってこ のようなvを開始状態とするとき、勝利領域内の勝利戦略に従う任意のプレイπは X_rに属する状態を含む。このようなX_Γ^ξは分割型到達可能性ゲームDR( A,{X_r}r∈Γ) の勝利領域に含まれる。従ってX_Γ^ξ+1はΓによる部分勝利領域の一部に含まれる。

以上より、全てのξに対してX_Γ^ξはΓによる部分勝利領域の一部に含まれる事が 成り立つ。

一方でξをX^ξ = X^ξ+1となるような最小の序数とする時、X_Γ^ξ = V\X_Γ^ξ を定め、

v ∈ X_Γ^ξを考える。この時、全てのv ∈V₀∩X_Γ^ξにおいて、全てのv^′=vEはv^′< X_Γ^ξ である。なぜならば、もしそうでない場合、vはX_Γ^ξに含まれるからである。同様 にして、全てのv ∈ V₁ ∩ X_Γ^ξにおいてv^′ < X_Γ^ξ を満たすv^′ ∈ vEが存在する。プ レイヤー1の戦略を f₁(v) = v^′とし、X_Γ^ξ に属する状態を開始状態とする時プレ イヤー1の戦略に従う任意のプレイπに含まれる任意の状態は必ずX_Γ^ξに属する。

X_Γ^ξ∩X_Γ^ξ = ϕよりX_Γ^ξ∩X_Γ = ϕなので、πはX_rに属する状態を含まない。このよ うなX_Γ^ξは分割型到達可能性ゲームDR( A,{X_r}r∈Γ)の勝利領域に含まれない。した

2015年度 修士論文

早稲田大学 基幹理工学研究科 情報理工・情報通信専攻 深澤研究室

がって、X_Γ^ξはΓによる部分勝利領域には含まれない。

以上より|Γ|=1の時、X_Γ^ξはΓによる部分勝利領域に一致する。

続いて、|Γ| ≥ 2の時を考える。|Γ| ≤ kの時にX_Γ^ξはΓによる部分勝利領域に一 致すると仮定する。Γ^′ ∈ {Γ ∈2^R||Γ| = k+1}とし、X_Γ^ξ_′ = ϕである最大のξをξϕ

とする。この時、すべてのv ∈ X_Γ^ξ_′に対して、v ∈ X_Γ^ξv_′⁺¹\X_Γ^ξv_′ かつξϕ ≤ ξv < ξを満 たすような単一のξvが存在する。これを用いることで|Γ|= 1の時と同様にX_Γ^ξ_′が Γ^′による部分勝利領域の一部であるということを帰納的に証明する。

ξ = ξϕ+1のとき、X_Γ^ξϕ_′ =ϕなので式(4.3)および式(4.8)から任意のv ∈ pre0(X^ξϕ) に対して X_Γ^ξϕ_′ < part0(v,{X_Γ^ξϕ_′}Γ^′∈2^R)である。従って式(4.14)からX_Γ^ξ_′ ∩V₀ = ϕで ある。一方で式(4.4)および式(4.11)からv ∈ X_Γ^ξ_′ であるならば、全てのv^′ ∈ vE はv^′ ∈ {γ ∈ V|γ ∈ X_Υ^ξϕ,Υ ∈ 2^Γ′}を満たす。従って、vを開始状態とし、Υ ∈ 2^Γ′ による部分勝利領域でそれぞれの勝利戦略に従うような任意のプレイ π は必ず x ∈ {γ ∈V|γ ∈ X_r,r ∈Γ^′}を含む。従ってvはDR( A,{X_r}r∈Γ^′)の勝利領域の性質を 満たす。また、式(4.12)よりv <{γ ∈V|γ ∈ X_Υ^ξϕ,Υ∈2^Γ′}である。従ってX_Γ^ξ_′はΓ^′ による部分勝利領域の性質を満たす。

ξ ≥ ξϕ +2のとき、X_Γ^ξ_′ がΓ^′による部分勝利領域に含まれる事を仮定する。こ の時、v ∈ {X_Γ^ξ+_′¹\X_Γ^ξ_′} ∩V₀はv^′ ∈ X_Γ^ξ_′ を満たすようなv^′ ∈ vEが存在する。従っ て仮定よりそのようなvに対して戦略 f₀(v) = v^′を持たせる時、vを開始状態と し、この戦略に従い、かつ勝利領域内では勝利戦略に従うような任意のプレイπは x ∈ {γ ∈V|γ ∈ X_r,r ∈Γ^′}を含む。一方で式(4.12)よりv<{γ ∈V|γ ∈ X_Υ^ξϕ,Υ ∈2^Γ′} である。従って、vはΓ^′による部分勝利領域の一部に含まれる。また式(4.4)およ び式(4.11)より、v ∈ {X_Γ^ξ+_′¹\X_Γ^ξ_′} ∩V₁はv^′<(X_Γ^ξ_′∪X_{^ξ_r

1}∪X_{^ξ_r

2})であるような状態 v^′ ∈ vEを持たない。従ってこのようなvを開始状態として、(X_Γ^ξ_′∪X_{^ξ_r

1} ∪X_{^ξ_r

2}) に属する状態が持つ勝利戦略に従う任意のプレイπはx ∈ {γ ∈V|γ ∈ X_r,r ∈Γ^′}を 含む。一方で式(4.12)よりv <{γ^′∈V|γ^′∈ X_Υ^ξϕ,Υ ∈ 2^Γ′}である。.従ってX_Γ^ξ+1_′ は Γ^′による部分勝利領域の一部に含まれる。

以上より、ξϕ < ξを満たす全てのξに対してX_Γ^ξ_′はΓ^′による部分勝利領域の一 部に含まれる事が成り立つ。

一方でξ を X^ξ = X^ξ+1となるような最小の序数とする時、|Γ| = 1と同様に X_Γ^ξ = V\{γ^′ ∈V|γ^′ ∈ X_Υ^ξϕ,Υ ∈ 2^Γ′}は分割型到達可能性ゲームDR( A,{X_r}r∈Γ)の勝 利領域に含まれない。したがって、X_Γ^ξはΓによる部分勝利領域には含まれない。

以上より|Γ| ≥2の時も、X^ξ

ΓはΓによる部分勝利領域に一致する。

以上よりX_Γ^ξ ∈ {X_Γ}_Γ^ξ_∈2Rによって定義される領域はプレイヤー0のΓによる部分 勝利領域となることが証明された。