Voronoi Game on Graph and its Complexity 寺本幸生上原隆平 (JAIST) ボロノイゲーム  競争施設配置問題の理想化されたモデル競争施設配置の例 – – – – 競争している2人のチェーン店（コンビニなど）の経営者 B, R が、それぞれ n 個のお店を新たに開店しようと計画している。消費者は最寄のお店を常に利用する。経営者 B, R は交互にお店を開店していく (B が最初にお店を開店）。このとき、相手より多くの収益（商圏の面積）を得るためには、どのような戦略でその n 個のお店を配置すればよいか？目的と関連研究  目的： –  ゲームモデルにおいて、先攻Bと後攻Rのどちらかに優位性があるのかを調べる。もしあるなら、その必勝戦略を与える。関連研究： – 1次元の連続区間（線分，円周）上のボロノイゲーム Ahn らにより、後攻Rの必勝戦略が示されている。また、離散的なモデル（パス，サイクル）では必ず引き分けると結論。必ず引き分けるとは限らない！離散モデルは議論の余地がある – 2次元の連続領域内（矩形領域）のボロノイゲームどちらかに優位性があるかどうかは未解決。木構造のようなグラフ上のボロノイゲームは自然な拡張。（パスやサイクルに対してより2次元に近づいているという意味で）グラフG上のボロノイゲームVG(G, n)  プレイヤーBとRが交互に頂点を占領していき、それぞれ n 個ずつ頂点を占領したらゲーム終了。（Bが先攻）例：１０ｘ１０のグリッド点のランダム全域木 2頂点間の距離：最短路上の辺の個数 50 プレイヤーBが占領した頂点。プレイヤーRが占領した頂点。このとき、各頂点は近接関係により 3つのタイプに分けられる。 • B に支配されている(近い）頂点 • R に支配されている（近い）頂点 • 両プレイヤーに支配されている頂点 44 最終的に、完全に支配している頂点数により勝敗が決まる。グラフ上のボロノイゲームでの目的（1）  Ahnらの主張が成り立たない場合が存在することを示す。  先手が必ず勝つような場合がある。(完全 k 分木を例に) – – ラウンド数の少ない場合と大きな完全 k 分木を例に、先手に対する必勝戦略を示す。完全 k(>1) 分木上のボロノイゲーム  完全 k 分木： – – 全ての内部頂点はちょうど k 個の子を持ち、全ての葉は同じレベルにある根付き木。 k ラウンド数が少ない（k  2n）場合：先攻が有利 k 鳩ノ巣原理より、少なくともひとつは誰にも占領されていない根の子が存在する。 k<2n の場合  k が奇数でかつ kh < 2n < kh+1 を満たすレベルh が存在し、k 分木 T が十分大きいとき、先攻は必勝戦略を持つ。 (実際は、2h 以上のレベルを持つような k 分木を仮定する) 2  グラフ上のボロノイゲームVG(T, n) における必勝戦略  ゲームフィールド T のサイズとラウンド数 n の関係により必要に応じて戦略を変えなければならない。キーレベル戦略  キーレベル h 上の頂点の個数 kh とラウンド数 n の関係式 2n / kh > a (=1 + 2/k – 1/(k–1) ) かどうかにより戦略を変える。 kh と 2n がほぼ等しいかどうかで場合わけを行う。 2n > a kh の場合戦略：レベル h 上の頂点をできるだけ多く取る各家族の少なくとも一つの頂点は占領するレベル h 上の頂点をより多く制した方が勝つ Bはレベル h の半分より多くの頂点を占領できる 2n  a kh の場合、キーレベルに固執すると負ける… 2n  a kh の場合の戦略  最初に、キーレベルの１つ上のレベル h–1 の頂点をできるだけ多くとる。  キーレベルのまだいずれのプレイヤーに取られていない頂点vに関して、その親が後手に取られているなら、v をとる。  レベルh+1の頂点についても、同じような戦略でとっていく。  このとき、先手の利得は後手の利得より少なくとも 2(kh – 1) / (k – 1) より多くなる。 k<2n の場合(2)  k が偶数でかつ kh  2n < kh+1 を満たすレベルh が存在し、 k 分木Tが十分大きいとき、両者が最善を尽くすと必ず引き分ける。  後攻Rは先攻 B の対称手を打てるので、負けることは無い。 Q. 後攻Rは必勝戦略を持つか？ A. No. キーレベル戦略により、Bはレベルh上の頂点を少なくとも半分は占領することができる。  最終的な利得としてRと同数の頂点を支配できる。グラフ上のボロノイゲームでの目的（2）  一般のグラフ上でのボロノイゲーム VG(G, n) において、必勝戦略が存在するかどうかを判定する問題の困難性について.  1-ラウンドボロノイゲーム 1-VG(G, n): 先手が、最初に n 個の点を置き、その後で後手が n 点置くような、制限されたボロノイゲーム。  一般のグラフ上での1-ラウンドボロノイゲームに関して、後手が必勝戦略を持つかどうかの判定問題がNP完全であることを示す。 Cheong et al. や Fekete et al. の2次元の矩形領域内の1-ラウンドゲームについて結果  後手が必ず先手の利得の 1+e 倍の利得を得る。 NP困難性ある与えられた一般のグラフ上での1-ラウンドボロノイゲームに関して、後手が必勝かどうかの判定問題はNP完全である。   – – –  各変数 xi に関してこの問題がNPに属することは自明。 3SATからのリダクションを考える。 xi F : 3和積標準形の論理式 n : 論理式 F の変数の数 m : 論理式 F の項の数 i 各項 cj に関して与えられた論理式 F からボロノイゲーム VG(G, n) の G を構成する。項 cj がリテラル xi を含む xi x i cj x c’j cj 項 cj がリテラル xi を含む c’j つなぐ xi x i cj c’j つなぐリダクションの例    後手は、少なくとも各変数 xi に対応する頂点 xi+, xi- のいずれかを占領しなければならない。先手は、少なくとも 3n + m + 2n – 1 = 5n + m – 1 の利得を得る。後手は、論理式 F を従属させるよう頂点を取ったとき、5n + m の利得を得、かつこのときのみ先手に勝つことができる。まとめと今後の課題まとめ – 十分大きな完全k分木においては先攻 B の優位性を示し、その必勝戦略を与えた。 – 一般のグラフ上の1-ラウンドボロノイゲームにおいて、後手が必勝戦略を持つかどうかの判定問題はNP-完全。今後の課題 – – – グリッド上のボロノイゲームの考察。（より実用的なモデルとして）一般の木や k-tree, partial k-tree への拡張。一般のグラフ上のn-ラウンドボロノイゲームの計算困難性について調べる。