173

数理解析研究所講究録
第2078巻 2018年 173-179ある特徴を持ったネッ トワーク上の探索ゲーム
兵庫県立大学経営学部

菊田健作

Kensaku KIKUTA

Department of Business Administration
University of Hyogo

1

はじめに

文献 [5] は車輪型ネッ トワークの変形ともいえるハブ スポーク型ネッ トワーク上の探索ゲームを扱っている.文献 [5] ではハブ スポーク型ネッ トワークをbroken wheel と呼んでいるが,ここでは前者の呼称を採用する.本稿の目的は,文献 [5] の内容を紹介し (第2節~第4節) , さらに,今後の課題を述べること (第5節) である.

hider と呼ばれる player が1個の静止目標物を有限連結ネッ トワーク上のノードのどれかに隠す.もう 1人の探索者と呼ばれる player はネッ トワークの辺上を移動しながらノードにある静止目標物を探す.探索者がノードを調べるときに調査費用が,また辺上を移動するときに移動費用が発生する.探索者は hider を見つけるまでの総費用が小さく なるようにノードを探索する順序を決めねばならない.一方,hider は総費用が大きくなるように目標物を隠すノードを選びたい.このような状況が両 player の利得の和をゼロとして行列ゲームモデルとして表現される.

文献 [10] はサイクルを含むノード数が6以下のネッ トワーク上のゲームにおいてhiderの最適戦略を推測している.一方,文献 [11] はゲームを構成する諸要素について述べている.ゲームを解く ことの難易度に関わる要素の一つがネッ トワークの構造である.文献 [8] と [12] は木ネッ トワークの場合を解析している.文献 [9] は円ネッ トワークの場合を分析し,探索諸費用が特殊な条件を満たす場合に成果を得ている.円ネッ トワークと文献 [5] で扱っているハブスポーク型ネッ トワークを比較すると,後者が辺の数が多い分探索者に有利となる.

Alpern /\mathrm{G}\mathrm{a}1 [1] とRuckle [13] は探索ゲームについて解説したテキストである.最近のものとして,報文集[2] がある.Gluss [7] は線ネッ トワークの場合に静止目標物の存在確率を既知として費用最小化問題を扱っている.探索者の移動費用を導入したという点で本報告に関わる初期の論文である.Baston /\mathrm{K}\mathrm{i}\mathrm{k}\mathrm{u}\mathrm{t}\mathrm{a}[3]174

図1: ハブ

スポーク型ネッ トワークの例, S=\{1 , 3, 6, 7 \}は無向ネッ トワークで探索出発ノードが指定されていない場合を扱っている.ただし,移動費用と調査費用を想定している.また,文献 [4] は有向ネッ トワーク上のゲームを扱っている.

2

ハブスポーク型ネツトワーク上のゲーム
本節では,移動費用と調査費用を考慮したハブスポーク型ネッ トワーク上の探索ゲームについてさらに詳しく述べる. \mathcal{G}=(N, S) をハブスポーク型ネッ トワークとする.ここに N=\{0, 1, n\}, n\geq 2,はノー ドの集合, S\subseteq N\backslash \{0\} はノード 0 と辺で直に結ばれているノードの集合である. |s| \geq 1 とする. T=N\backslash (\{0\}\cup S) とおく.辺の集合 E\subseteq N\times N が(1)

E=\{(0, i):i\in S\}\cup\{(i, i+1):1\leq i\leq n-1\}\cup\{(1, nと与えられる (図1参照) . 辺に沿った有限個のノードの列をパスという.

2人の player, つまり hider と探索者がおり,hider は N\backslash \{0\} に含まれるノードのどれか1つを選びそこに静止目標物を隠す.探索者はhiderがどのノードを選んだかを知らずにノ-ド 0 から出発し辺上を移動しながら各ノードを調べて行く.ノードを調べずに通過することもできる.そうする場合はそのノードの調査費用はかからない.静止目標物が見つかった時点で探索は終了する.探索者が静止目標物が存在するノードを調べたときその静止目標物を見逃す確率はどのノードについても 0 である.したがって探索者が同じノードを2度以上調べることはない.ノード i\in N の調査費用は c_{i}>0 である. (i, j)\in Eのとき,ノード i から j への移動費用は d(i, j) である.ネッ トワークは連結であるから (i, j)\not\in E のときでも i から j へのパスが存在する. (i, j)\not\in E のときは i から j へのすべてのパスに対してパス上の辺の移動費用の和を考え,その最小値を d(i, j) とする.また,すべてのノード i に対し d(i, i)=0 とする.

hider の (純粋) 戦略はノード i \in N\backslash \{0\} を選ぶこ とである.探索者の (純粋) 戦略は,探索を開始する前に,探索するノードの順序を決定することである.探索者の戦略を $\sigma$ \equiv $\sigma$(1) , . . . , $\sigma$(n) と175表す.

$\sigma$

は N\backslash \{0\} 上の置換である.また, $\sigma$(0)=0としておく.

$\sigma$の逆順序を $\sigma$^{r} と表す.ここに,$\sigma$^{r}(j)= $\sigma$(n+1-j) , 1\leq j\leq n である.さらに, $\sigma$^{-1} を$\sigma$^{-1}(i)=j\Leftrightarrow $\sigma$(j)=i(2)によって定義する.

hider, 探索者がそれぞれ i, $\sigma$ を選んだとき,探索者が静止日標物を見つけた時点で探索は終了する.
このときの探索費用は

f(i, $\sigma$)\displaystyle\equiv\sum_{x=1}^{$\sigma$^{-1}(i)}[d($\sigma$(x-1), $\sigma$(x) +c_{$\sigma$(x)}](3)となる.これを hider の利得と考え,探索者はこれをできるだけ小さ く,hider はできるだけ大きくするようにそれぞれ i, $\sigma$ を選ぶ,として2人有限ゼロ和ゲームモデル $\Gamma$(N, S) が得られ,n\times n! 型の行列ゲームとして表現される.hider, 探索者の混合戦略をそれぞれ p, q で表して探索者が目標物を発見するまでの期待探索費用を f(p, q) と表す.ここに, p=(p\mathrm{l}, . . . , p_{n}) および q=\{q( $\sigma$)\}_{ $\sigma$} であり,れぞれ hider, 探索者が戦略 i,$\sigma$p_{i}, q_{ $\sigma$} はそを選ぶ確率である.したがって,\displaystyle \sum_{i\in N\backslash \{0\} p_{i}=1, p_{i}\geq 0, \foral i\in N\backslash \{0\}, \sum_{ $\sigma$}q_{ $\sigma$}=1, q_{ $\sigma$}\geq 0, \foral $\sigma$.

(4)

一方のみが,純戦略をとったときの期待費用を f(p, $\sigma$) , f(i, q) と表す.
本稿ではc、を仮定する.次の記号を用いる.
W=n+C ,=\left{bginary}{l c_S}\ c_{T}\end{ary}\ight.

及び $\epsilon$=

if i\in S(5)

if i\in T\displaystyle \frac{ _{S}-c_{T} {2W} , ここに C=\displaystyle \sum_{i=1}^{n}c_{i} .

探索者の次のような戦略は効率的であり,後述の最適戦略の中に現れる.各 i\in S に対し,

(6)

\rightar ow i, \leftar ow i, i\rightar ow,\leftar ow iを\rightarrow i=i, i+1 , . . . , , 1, . . . , i-1\leftarrow i=i, i-1 , . . . , 1, , . . . , i+1

i\rightarrow=i+1, i+2 , . . . , n , 1, . . . , i\leftarrow i=i-1, i-2 , . . . , 1, n , . . . , i.

nn(7)で定義する.さらに,戦略才 と ㌃を確率1/2ずつでとる戦略を㌣ と表す.同様に,戦略 i\rightar ow と豹を確率1/2ずつでとる戦略を \leftar ow i\rightar ow と表す.次の計算は探索者の最適戦略を考察するときに必要である.

176

図2: 定理2の |S|=1 の例 (左) と |S|=4 の例 (右)命題1. ([5]) ノード i\in S に対し,

f(j,\leftrightar owi)=\left\{ begin{ar ay}{l} 1+c_{i}&ifj=i\ (W+2+c_{i}+c_{j})/2&ifj\neqi \end{ar ay}\right.

(8)

命題2. ([5]) ノード i\in S に対し,

f(j,\leftar owi^{\rightar ow})=\left\{ begin{ar ay}{l W+1&ifj=i\ (W+2-c_{\dot{$\eta$}+c_{j})/2&ifj\neqi \end{ar ay}\right.
3(9)

ゲームの値の上界
探索者は移動費用について効率的であるような戦略をとることにより期待探索費用をある値以下にすることができる.定理1はそれを述べている.

定理1. ([5]) ノードの集合 S のどの2つの元もネッ トワーク \mathcal{G}(N, S) において隣接していないと仮定する.探索者は各ノード i\in S を確率 1/|S| で選び,さらに㌣を確率 1/2+ $\epsilon$|S|, \leftar ow i\rightar ow を確率 1/2- $\epsilon$|S|で選ぶことにより,期待探索費用を高々 V とできる.ここに,

V=\displaystyle \frac{W+2+c_{T} {2}+|S|c_{S} $\epsilon$ .

(10)である.

定理1で与えた V は S が1点集合であるときや n=2m かつ |S|=m のときはゲームの値となる (図2参照) . 次の定理2はこれを述べている.

定理2. ([5]) ネッ トワーク \mathcal{G}(N, S) において |S|=1 かまたは n=2m かつ |S|=m であるとする.

このときゲーム $\Gamma$(N, S) の値は (10) の V である.hider の最適戦略は S の各ノードに確率 c_{S}/W で静止目

177

標物を隠し,T の各ノドに確率 (n/|T|+c_{T})/W で静止日標物を隠すことである.探索者の最適戦略-は S の各ノード i を確率 1/|S| で選び,さらに㌣を確率 1/2+ $\epsilon$|S|, \leftar ow i\rightar ow を確率 1/2- $\epsilon$|S| で選ぶことである.

4

S が区間の場合

集合 S のノード番号が連続しているとき,S を区間と呼ぶ.例えば,k<\ell\# こ対し

S=\{i:k\leq i\leq\ell\}

は区間である.これを S=[k, \ell] と表す.本節では,集合 S が区間であるときのゲームの値や最適戦略を考察する.

定理3. ([5]) 集合 S が区間であり, |S| \geq 2 と cs\geq c_{T} を満たすとする.ゲーム $\Gamma$(N, S) の値は次で与えられる.

v_{int}=\displaystyle \frac{W+1+c_{T} {2}+|S|(1+c_{S}) $\epsilon$ .

(11)

集合 S が区間 [ 1, k] であるとして,探索者の最適戦略は \rightar ow k と \displayst le\frac{\ovalbox{\t smal REJ CT}{k-1} のそれぞれを確率 1/2- $\epsilon$ で選び,寸と 芳のそれぞれを確率 で選ぶことである.hider の最適戦略は S の各ノードに確率 (1+cs)/W で静$\epsilon$

止目標物を隠し,T の各ノードに確率 (1+c_{T})/W で静止目標物を隠すことである.

定理4. ([5]) 集合 S が区間 [ 1, k] であり,k\geq 2 かつ c_{T}\geq c_{S} であるとする.戦略 \rightar ow kと \displayst le\frac{\ovalbox{\t smal REJ CT}{k-1} をそれぞれ確率 1/2- $\epsilon$ で選び,戦略 \leftarrow 1 と k\rightarrow をそれぞれ確率 $\epsilon$ で選ぶことによって,探索者は $\Gamma$(N, S) における期待探索費用をV_{INT}=\displaystyle \frac{W+1+c_{T} {2}-[2-k(1+c_{S})] $\epsilon$ .に等しくできる.特に,(12)k=2 のときは V_{iNT} がゲームの値であり,hider の最適戦略は S の各ノードに確率 c_{S}/W で静止目標物を隠し,T の各ノードに確率 (n/(n-2)+c_{T})/W で静止目標物を隠すことである.

5

今後の課題
まず, |S|=sとし,S=\{i_{1}, . . . , i_{s}\}, i\mathrm{i}=1<i_{2}<...

<i_{s} とする.各 1 \leq \ell \leq\mathcal{S}に対し,T_{p}^{s}=\{i:i_{\ell}<i<i_{\ell+1}\} とおく.
I. 上記4つの定理によって次のような成果が得られた.他の場合にゲームを解く ことが課題である.
(1) ゲームを解いた場合(i) |S|=1 または |S|=n/2(定理2)(ii) S=\{1, . . . , k\} , かつ c_{S}\geq c_{T} (定理3)178(\mathrm{i}\mathrm{i}\mathrm{i})S=\{1 , 2 \} , かつ c_{S}\leq c_{T} (定理4)(2) ゲームの値の上界を求めた場合(i) S の異なるどの二つのノードも隣接していない場合,つまり,全ての 1\leq\ell\leq s に対し |T_{\ell}^{S}|\geq 1の場合

(定理1) .

(ii) S=\{1, . . . , k\}, k\geq 3 かつ c_{S}\leq c_{T} (定理4)Ⅱ.上記 I (2) (i) に加えて,さらに次の結果を得る.証明は文献 [6] を参照されたい.
定理5. ([6]) 全ての 1\leq\ell\leq s に対し 1\leq|T_{\ell}^{S}|\leq 2 を仮定する.ゲームの値は \displaystyle \frac{v(S)}{W} である.ここに,v(S)\displaystyle \equiv\frac{n(n+2)}{2}+(n+1)s(c_{S}-c_{T})+n(n+\frac{3}{2})c_{T}+\frac{(sc_{S}+(n-s)c_{T})^{2}+sc_{S}^{2}+(n-s)c_{T}^{2} {2} . (13)hider の最適戦略は p^{s} である.ここに,a_{i}^S}=\left\{ begin{ar y}{l 0,&if\nS;\ \frac{|T_\el}^{S}|+1{|$\tau$_{\el}^{S}|,&if\nT_{p}^{S},\el=1,. ,s. \end{ar y}\right.

p_{i}^{s}=\displaystyle \frac{a_{i}^{S}+c_{i} {W},
探索者の一つの最適戦略は s* である(14)

ここに,各 i\in S に対し, s_{i}* は才 と ㌃をそれぞれ確率 $\beta$/W

でと り ,\mathrm{z}\urcorner_{+} と l\overline{-1}+ をそれぞれ確率 $\gamma$/W でとる戦略である.

s* は各 s_{i}* を確率 1/s でとる戦略であると定義される.さらに,$\beta$\displaystyle \equiv\frac{n+2sc_{S}+(n-2s)c_{T} {4s}, $\gamma$\equiv\frac{n(1+c_{T})}{4s} .
特に,c_{S}=c $\tau$=c のときは,制約(15)|T_{\ell}^{S}|\leq 2 を外すことができる.つまり次を得る.

定理6. ([ó]) 全ての 1 \leq\ell\leq s に対し,1 \leq|T_{\ell}^{S}| を仮定する. c_{S} =c_{T}=c を仮定する.ゲームの値は\displaystyle \frac{n+2}{2}+\frac{n+1}{2}c である.hider の一つの最適戦略は p^{s} である.探索者の一つの最適戦略は s* である.
こに,各 i\in S に対し, s_{i}* は \rightar ow i,i\urcorner_{+}, \leftar ow i, \overline{ $\iota$-1} を等確率でとる戦略であり, s* は各 S_{i}^{*} を 1/s でとる
こ戦略である.

参考文献[1] S. Alpern and S. Gal, The theory of search games and rendezvous, Kluwer International Series inOperations Research and Management Sciences, Kluwer, Boston, (2003).

[2] S. Alpern, R.Fokkink,L.Gasieniec, R.Lindelauf and V.S.Subrahmanian, Search theory: a gametheoretic perspective, Springer, (2013).

179[3] V. Baston and K. Kikuta, Search games on networks with travelling and search costs and witharbitrary searcher starting points, Networks 62 (2013), 72‐79.

[4] V. Baston and K. Kikuta, Search games on a network with travelling and search costs, Interna‐tional Journal of Game Theory 44 (2015), 347‐365.
[5] V. Baston and K. Kikuta, Search games on a broken wheel with traveling and search costs, J.
Oper. Res. Soc. Japan 60 (2017), 379‐392.

[6] V. Baston and K. Kikuta, A search game on a broken wheel, mimeo. (2014).
[7] B. Gluss, Approximately optimal one‐dimensional search policies in which search costs varythrough time, Naval Research Logistics Quarterly 8, (1961) 277‐283.

[8] K. Kikuta, A search game with travelling cost on a tree, J. Oper. Res. Soc. Japan 38 (1995),70‐88.

[9] K. Kikuta, A search game on a cyclic graph. Naval Research Logistics 51 (2004) 977‐993.

[10] K. Kikuta, やや複雑なネットワーク上の探索問題の解析について. R1MS 講究録2044 (2017) 131‐140.

[11] K. Kikuta, ネッ トワーク上の探索ゲーム.オペレーションズ

リサーチ 60 (2015) 288‐293.

[12] K. Kikuta and W. Ruckle, Initial point search on weighted trees, Naval Research Logistics 41(1994) , 821‐831[13] W. Ruckle, Geometric games and their applications, Pitman Research Notes in Mathematics S2,Boston, (1983).