Voronoi Game on Graph and its Complexity 寺本 幸生 上原 隆平 (JAIST)

Presentation on theme: "Voronoi Game on Graph and its Complexity 寺本 幸生 上原 隆平 (JAIST)"— Presentation transcript:

1 Voronoi Game on Graph and its Complexity 寺本 幸生 上原 隆平 (JAIST)

2 ボロノイゲーム 競争施設配置問題の理想化されたモデル 競争施設配置の例 – 競争している 2 人のチェーン店（コンビニなど）の経営者 B, R が、 それぞれ n 個のお店を新たに開店しようと計画している。 – 消費者は最寄のお店を常に利用する。 – 経営者 B, R は交互にお店を開店していく (B が最初にお店を開 店）。 – このとき、相手より多くの収益（商圏の面積）を得るためには、 どのような戦略でその n 個のお店を配置すればよいか？

3 目的と関連研究 目的： – ゲームモデルにおいて、先攻 B と後攻 R のどちらかに優位性がある のかを調べる。もしあるなら、その必勝戦略を与える。 関連研究： – 1 次元の連続区間（線分，円周）上のボロノイゲーム Ahn らにより、後攻 R の必勝戦略が示されている。 また、離散的なモデル（パス，サイクル）では必ず引き分けると 結論。 必ず引き分けるとは限らない！ 離散モデルは議論の余地がある – 2 次元の連続領域内（矩形領域）のボロノイゲーム どちらかに優位性があるかどうかは未解決。 木構造のようなグラフ上のボロノイゲームは自然な拡張。 （パスやサイクルに対してより 2 次元に近づいているという意味で）

4 グラフ G 上のボロノイゲーム VG(G, n) 例： １０ｘ１０のグリッド点のランダム全域木 プレイヤー R が占領した頂点。 このとき、各頂点は近接関係により 3 つのタイプに分けられる。 B に支配されている ( 近い）頂点 R に支配されている（近い）頂点 両プレイヤーに支配されている頂点 最終的に、完全に支配している頂点数 により勝敗が決まる。 50 44 プレイヤー B と R が交互に頂点を占領していき、それぞれ n 個ずつ頂 点を占領したらゲーム終了。（ B が先攻） プレイヤー B が占領した頂点。 2 頂点間の距離：最短路上の辺の個数

5 グラフ上のボロノイゲームでの目的 （ 1 ） Ahn らの主張が成り立たない場合が存在することを示す。  先手が必ず勝つような場合がある。 ( 完全 k 分木を例 に ) – ラウンド数の少ない場合と – 大きな完全 k 分木を例に、先手に対する必勝戦略を示す。

6 完全 k(>1) 分木上のボロノイゲーム 完全 k 分木： – 全ての内部頂点はちょうど k 個の子を持ち、 – 全ての葉は同じレベルにある根付き木。 k k 鳩ノ巣原理より、少なくともひとつは 誰にも占領されていない根の子が 存在する。 ラウンド数が少ない（ k  2n ）場合： 先攻が有利

7 k<2n の場合 k が奇数でかつ k h < 2n < k h+1 を満たすレベル h が存在し、 k 分木 T が十分大きいとき、先攻は必勝戦略を持つ。 ( 実際は、 2h 以上のレベルを持つような k 分木を仮定する ) グラフ上のボロノイゲーム VG(T, n) における必勝戦略  ゲームフィールド T のサイズとラウンド数 n の関係により 必要に応じて戦略を変えなければならない。 2

8 キーレベル戦略 キーレベル h 上の頂点の個数 k h と ラウンド数 n の関係式 2n / k h >  (=1 + 2/k – 1/(k–1) ) かどうかにより戦略を変える。 k h と 2n がほぼ等しいかどうかで場合わけを行う。

9 2n >  k h の場合 戦略： レベル h 上の頂点をできるだけ多く取る 各家族の少なくとも一つの頂点は占領する レベル h 上の頂点をより多く制した方が勝つ B はレベル h の半分より多くの頂点を占領できる 2n   k h の場合、キーレベルに固執すると負ける …

10 2n   k h の場合の戦略 最初に、キーレベルの１つ上のレベル h–1 の頂点をできるだけ多く とる。 キーレベルのまだいずれのプレイヤーに取られていない頂点 v に関し て、その親が後手に取られているなら、 v をとる。 レベル h+1 の頂点についても、同じような戦略でとっていく。 このとき、先手の利得は後手の利得より少なくとも 2(k h – 1) / (k – 1) より多くなる。

11 k<2n の場合 (2) k が偶数でかつ k h  2n < k h+1 を満たすレベル h が存在し、 k 分木 T が十分大きいとき、 両者が最善を尽くすと必ず引き分ける。 後攻 R は先攻 B の対称手を打てるので、負けることは無 い。 Q. 後攻 R は必勝戦略を持つか？ A. No. キーレベル戦略により、 B はレベル h 上の頂点 を 少なくとも半分は占領することができる。  最終的な利得として R と同数の頂点を支配 できる。

12 グラフ上のボロノイゲームでの目的 （ 2 ） 一般のグラフ上でのボロノイゲーム VG(G, n) において、 必勝戦略が存在するかどうかを判定する問題の困難性について. 1- ラウンドボロノイゲーム 1-VG(G, n): 先手が、最初に n 個の点を置き、その後で後手が n 点置くような、 制限されたボロノイゲーム。  一般のグラフ上での 1- ラウンドボロノイゲームに関して、後手が 必勝戦略を持つかどうかの判定問題が NP 完全であることを示す。 Cheong et al. や Fekete et al. の 2 次元の矩形領域内の 1- ラウンドゲーム について結果  後手が必ず先手の利得の 1+e 倍の利得を得る。

13 NP 困難性 この問題が NP に属することは自明。 3SAT からのリダクションを考える。 – F : 3 和積標準形の論理式 – n : 論理式 F の変数の数 – m : 論理式 F の項の数 与えられた論理式 F からボロノイゲー ム VG(G, n) の G を構成する。 ある与えられた一般のグラフ上での 1- ラウンドボロノイゲームに関して、 後手が必勝かどうかの判定問題は NP 完全である。 各変数 x i に関して xixi xixi 各項 c j に関して cjcj c’ j 項 c j がリテラル x i を含 む xixi xixi cjcj c’ j つなぐ 項 c j がリテラル x i を含む xixi xixi cjcj c’ j つなぐ

14 リダクションの例

15 後手は、少なくとも各変数 x i に 対応する頂点 x i +, x i - のいずれか を占領しなければならない。 先手は、少なくとも 3n + m + 2n – 1 = 5n + m – 1 の利得を得る。 後手は、論理式 F を従属させるよう頂点を取ったとき、 5n + m の利 得を得、かつこのときのみ先手に勝つことができる。

16 まとめと今後の課題 まとめ – 十分大きな完全 k 分木においては先攻 B の優位性を示し、その必 勝戦略を与えた。 – 一般のグラフ上の 1- ラウンドボロノイゲームにおいて、後手が必 勝戦略を持つかどうかの判定問題は NP- 完全。 今後の課題 – グリッド上のボロノイゲームの考察。（より実用的なモデルとし て） – 一般の木や k-tree, partial k-tree への拡張。 – 一般のグラフ上の n- ラウンドボロノイゲームの計算困難性につい て調べる。