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が先攻)
例: 10x10のグリッド点のランダム全域木
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 の場合の戦略

最初に、キーレベルの1つ上のレベル 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-ラウンドボロノイゲームの計算困難性について調
べる。
ダウンロード

発表資料