Graph grabbing gameに関する諸問題

Presentation on theme: "Graph grabbing gameに関する諸問題"— Presentation transcript:

1 Graph grabbing gameに関する諸問題
松本 直己 （慶應義塾大学デジタルメディア・コンテンツ統合研究センター） 大阪組合せ論セミナー （2019年11月9日）

2 略歴 2010年3月： 甲南大学 理工学部 物理学科 卒業 2010年4月： 横浜国立大学大学院 環境情報学府 修士課程 入学
2011年9月： 同上 修了 2011年10月： 横浜国立大学大学院 環境情報学府 博士課程 入学 2013年12月： 同上 修了 2013年4月~12月： 日本学術振興会 特別研究員DC 2014年1月~ 2015年3月： 同　特別研究員PD （横浜国大 所属） 2015年5月~2019年7月： 成蹊大学 理工学部 情報科学科 助教 2019年8月~： 慶應義塾大学 DMC統合研究センター 特任助教

3 組合せゲーム（Combinatorial game）
2人の対局者が交互に手を打ち, 以下の性質を満たすゲームのことを指す． 確定性： サイコロを振るなどの偶然要素を含まない． 完全情報性： ゲームの進行やお互いの手の内が 　　　　　　　　 隠されていない． 組合せゲームの例） 囲碁, 将棋, チェス, ニム 組合せゲームでない例） すごろく, ポーカー 組合せゲームはどちらのプレイヤーが勝つか（引き分けるか）が決まっている

4 組合せゲームの分類 不偏 パルチザン （非不偏） Conway ニム ドミナリング 非Conway クアルト 囲碁, チェス
着手可能な手が同じ 不偏 パルチザン （非不偏） Conway ニム ドミナリング 非Conway クアルト 囲碁, チェス 着手可能な手が なくなったら負け 自分はグラフ理論からこのゲームの研究に入ったので、グラフ理論がどのように組合せゲームの研究に関わっているのかをお話ししたいと思います。

5 例） ゲーム染色数（Game chromatic number） ゲーム支配数（Game domination number）
グラフ上の組合せゲームの分類 1. ゲーム的要素を用いたグラフ不変量 例） ゲーム染色数（Game chromatic number） ゲーム支配数（Game domination number） 2. 盤面としてグラフを用いるゲーム 例） ボロノイゲーム（競争的施設配置問題のモデル） ラムゼーゲーム（Simの一般化） Graph grabbing game（Coins in a rowの一般化） 分類１：グラフの不変量をゲーム的要素を用いた不変量に拡張するための組合せゲーム 分類２：グラフ上で実際に組合せゲームをしている。　それぞれ、代表例として、ゲーム染色数とグラフ・グラビングゲームを紹介する。 分類１はグラフ理論の研究者が多く、分類２はCGTの人はもちろん、アルゴリズムや計算量などを研究している人がいる印象

6 ＊アリス（先手）とボブが交互にコインを取る ＊両端のコインのみ獲得できる ＊すべてのコインを取り終わったとき,
Coins in a row 100 10 50 ルール ＊アリス（先手）とボブが交互にコインを取る ＊両端のコインのみ獲得できる ＊すべてのコインを取り終わったとき, アリスが全体の半分以上の金額を獲得 → アリスの勝ち そうでない場合 → ボブの勝ち 『Mathematical Puzzles』（P. Winkler著 2003年）の 一番初めに記載されているゲーム

7 Coins in a row（コインが偶数枚の場合）
10 10 50 100 100 100 50 100 10 10 100 100 白コインの合計と黒コインの合計のどちらか一方は合計金額の半分以上 アリスは常に多い方の色のコインを取ればよい！

8 「取り除いてもグラフが連結である頂点のみ獲得できる」
Coins in a rowの一般化 100 10 10 50 100 100 50 100 10 100 100 100 「両端のコインのみ獲得できる」 「取り除いてもグラフが連結である頂点のみ獲得できる」

9 Graph grabbing game G：重み付き連結グラフ 1 4 3 5 1 ※重みは0以上の整数 アリス （先手） ボブ （後手）

10 アリスがグラフ全体の重みの半分以上を獲得すれば, アリスの勝ち． そうでない場合, ボブの勝ち．
Graph grabbing game 全体の重み合計 ： 14 1 4 3 5 1 ＊ルール： 頂点を取り除いた後のグラフも連結 アリス （先手） ボブ （後手） アリスがグラフ全体の重みの半分以上を獲得すれば, アリスの勝ち． そうでない場合, ボブの勝ち．

11 アリスがグラフ全体の重みの半分以上を獲得すれば, アリスの勝ち． そうでない場合, ボブの勝ち．
Graph grabbing game 全体の重み合計 ： 14 1 4 3 1 5 ＊ルール： 頂点を取り除いた後のグラフも連結 アリス （先手） ボブ （後手） アリスがグラフ全体の重みの半分以上を獲得すれば, アリスの勝ち． そうでない場合, ボブの勝ち．

12 アリスがグラフ全体の重みの半分以上を獲得すれば, アリスの勝ち． そうでない場合, ボブの勝ち．
Graph grabbing game 全体の重み合計 ： 14 1 4 3 1 5 ＊ルール： 頂点を取り除いた後のグラフも連結 アリス （先手） ボブ （後手） アリスがグラフ全体の重みの半分以上を獲得すれば, アリスの勝ち． そうでない場合, ボブの勝ち．

13 アリスがグラフ全体の重みの半分以上を獲得すれば, アリスの勝ち． そうでない場合, ボブの勝ち．
Graph grabbing game Win ! 全体の重み合計 ： 14 1 3 3 1 1 1 5 4 ＊ルール： 頂点を取り除いた後のグラフも連結 アリス （先手） ボブ （後手） アリスがグラフ全体の重みの半分以上を獲得すれば, アリスの勝ち． そうでない場合, ボブの勝ち．

14 組合せゲームの分類 不偏 パルチザン （非不偏） Conway ニム ドミナリング 非Conway クアルト 囲碁, チェス Graph grabbing game 取り除ける頂点（着手可能な手）は同じ （不偏） ゲームの勝敗は重みに依存する （非Conway）

15 ゲームの計算複雑性 定理1.（Cibulka et al. 2013） 与えられた重み付き連結グラフにおいて，ゲームの 勝利者を判定する問題はPSPACE完全である． 問題. どのように重みが与えられても, アリスがゲームに 勝てる（重み付き）グラフのクラスを決定せよ． ＊任意のグラフにおいて, アリスがゲームに勝てるような重み付けは存在する． ＊以降, “重み付き”は省略．

16 任意の頂点数が偶数の道グラフ, 閉路グラフにおいて, アリスはゲームに勝つことができる．
先行研究 定理2.（Winkler 2003） 任意の頂点数が偶数の道グラフ, 閉路グラフにおいて, アリスはゲームに勝つことができる． 𝐶 6 𝑃 6 ＊どちらも二部グラフなので, 片方の色の頂点を すべて取る戦略により, アリス必勝．

17 アリスがゲームに勝てないグラフ 5頂点の道グラフ 15頂点の閉路グラフ 全体の重み：1 全体の重み： 9 （アリスは高々4しか取れない）
1 1 2 全体の重み：1 1 このようにアリスが勝てないグラフもたくさんあるが、一方で偶数頂点の道グラフであれば勝てるので、それに近い構造をもつグラフについて、 アリスが勝つかどうかを考えるのは自然な研究の流れである 全体の重み： 9 （アリスは高々4しか取れない） 全体の重み：３ （アリスは高々1しか取れない） アリスは全体の4/9以上は 獲得可能（Cibulka et al. 2009）

18 先行研究 定理2.（Winkler 2003） 任意の頂点数が偶数の道グラフ, 閉路グラフにおいて, アリスはゲームに勝つことができる． 定理3.（Seacrest and Seacrest 2012） 任意の頂点数が偶数の木グラフにおいて, アリスは ゲームに勝つことができる．

19 先行研究 定理2.（Winkler 2003） 任意の頂点数が偶数の道グラフ, 閉路グラフにおいて, アリスはゲームに勝つことができる． 定理3.（Seacrest and Seacrest 2012） 任意の頂点数が偶数の木グラフにおいて, アリスは ゲームに勝つことができる． 予想1．(Seacrest and Seacrest 2012) 任意の頂点数が偶数の連結二部グラフにおいて, 　　アリスはゲームに勝つことができる．

20 先行研究 𝐾 3,2 -tree 頂点数 グラフ 偶数 奇数 木グラフ（Tree） ○
（Seacrest & Seacrest, 2012） × 二部グラフ ？（予想1：○） 非二部的グラフ （○：アリスが勝てる　×：アリスが勝てないグラフと重みの組が存在） 予想1について, 𝐾 𝑚,𝑛 -tree に対しては解決済み（Egawa, Enomoto and M. 2018）． アリスにとって都合の悪い部分構造を明らかにしたいと思い、グラフの誘導部分グラフに着目した。 𝐾 3,2 -tree

21 𝐺が 𝐶 2𝑘+1 -corona-フリー（𝑘≥1）ならば, アリスはゲームに勝つことができる．
誘導部分グラフ ＊いくつかの頂点を取り出し, その頂点対の辺の有無が元のグラフと一致するグラフ 𝐶 3 -corona 𝐶 3 -corona-フリー 予想2． 𝐺 ： 頂点数が偶数の連結グラフ 𝐺が 𝐶 2𝑘+1 -corona-フリー（𝑘≥1）ならば, 　　　　　　アリスはゲームに勝つことができる． 部分的に含まれるグラフの種類を限定して、良い構造を見つける研究はグラフ理論でよくなされている。

22 予想・結果 𝑃 5 Bull 頂点数 グラフ 偶数 奇数 木グラフ（Tree） ○ （Seacrest & Seacrest, 2012）
× 二部グラフ ？（予想1：○） 𝐶 2𝑘+1 -corona-free ？（予想2：○） その他 （○：アリスが勝てる　×：アリスが勝てないグラフと重みの組が存在） 予想2に対して, 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーなグラフで部分的解決を得ている（Doki, Egawa and M ）． Bull 𝑃 5

23 rooted graph grabbing game (rooted game)
Win ! 全体の重み合計 ： 9 1 4 root 3 1 4 1 3 ＊追加ルール： ある指定された頂点（root）は最後に取らなければならない 1 アリス （先手） ボブ （後手） (G, v)：頂点vがrootとして指定されたグラフG （根付きグラフ）

24 定理3.（Seacrest and Seacrest 2012） 任意の頂点数が偶数の木グラフにおいて, アリスは
定理3の証明方針 定理3.（Seacrest and Seacrest 2012） 任意の頂点数が偶数の木グラフにおいて, アリスは ゲームに勝つことができる． 𝐺 : 木グラフ 以下, 二人のプレイヤーはどちらも最適にプレイすると仮定する． 𝑁 𝐺,1 : G上のゲームでの先手の取り分 𝑁 𝑅 𝑣 𝐺,1 : (G, v)上のrooted gameにおける先手の取り分 ※ 𝑁 𝐺,2 , 𝑁 𝑅 𝑣 𝐺,2 for 後手

25 定理3.（Seacrest and Seacrest 2012） 任意の頂点数が偶数の木グラフにおいて, アリスは
定理3の証明方針 定理3.（Seacrest and Seacrest 2012） 任意の頂点数が偶数の木グラフにおいて, アリスは ゲームに勝つことができる． 𝐺 : 木グラフ 以下, 二人のプレイヤーはどちらも最適にプレイすると仮定する． 𝑁 𝐺,−1 : G上のゲームでの最後に頂点をとるプレイヤー 　　　　　　 の取り分 𝑁 𝑅 𝑣 𝐺,−1 : (G, v)上のrooted gameにおける 最後に頂点をとるプレイヤーの取り分 ※ 𝑁 𝐺,−2 , 𝑁 𝑅 𝑣 𝐺,−2 for 最後から二番目に頂点をとるプレイヤー

26 定理3.（Seacrest and Seacrest 2012） 任意の頂点数が偶数の木グラフにおいて, アリスは
定理3の証明方針 定理3.（Seacrest and Seacrest 2012） 任意の頂点数が偶数の木グラフにおいて, アリスは ゲームに勝つことができる． 主張1．𝑇 : 木グラフ ∀𝑣∈𝑉 𝑇 , 𝑁 𝑅 𝑣 𝑇,−2 ≤𝑁 𝑇,−2 ．　 主張2．𝑇 : 頂点数が偶数の木グラフ ∀𝑣∈𝑉 𝑇 , 𝑁 𝑇,−1 ≤ 𝑁 𝑅 𝑣 𝑇,1 ． ［定理3の証明］ 主張1, 2より, 𝑁 𝐺,2 ≤ 𝑁 𝑅 𝑣 𝐺,1=−2 ≤𝑁 𝐺,1 ．

27 主張1の証明 主張1,2を同時に頂点数に関する帰納法で証明する． 主張1．𝑇 : 木グラフ
∀𝑣∈𝑉 𝑇 , 𝑁 𝑅 𝑣 𝑇,−2 ≤𝑁 𝑇,−2 ．　 ［主張1の証明］ (i) T の頂点数が偶数の場合 先手の(T, v)上のrooted gameにおける最適な手を𝑎とすると, 𝑁 𝑅 𝑣 𝑇, −1=2 = 𝑁 𝑅 𝑣 𝑇−𝑎,1=−1 ≥𝑁 𝑇−𝑎,1=−1 (by induction) ≥𝑁 𝑇,2=−1

28 主張1の証明 主張1．𝑇 : 木グラフ ∀𝑣∈𝑉 𝑇 , 𝑁 𝑅 𝑣 𝑇,−2 ≤𝑁 𝑇,−2 ． ［主張1の証明つづき］
∀𝑣∈𝑉 𝑇 , 𝑁 𝑅 𝑣 𝑇,−2 ≤𝑁 𝑇,−2 ．　 ［主張1の証明つづき］ (ii) T の頂点数が奇数の場合 先手の最適な手を𝑏とする．𝑏が𝑣と異なるなら, (i)と同様に証明可． よって, 同じ頂点（𝑏=𝑣）とする．このとき, 𝑁 𝑅(𝑣) 𝑇,−2 = 𝑁 𝑅(𝑢) 𝑇−𝑣,−1 ≤𝑁 𝑇−𝑣,1=−2 (by 主張2, 𝑢は𝑣の近傍) =𝑁 𝑇,2=−2 𝑣 𝑇−𝑣 𝑢 主張2．𝑇 : 頂点数が偶数の木グラフ ∀𝑣∈𝑉 𝑇 , 𝑁 𝑇,−1 ≤ 𝑁 𝑅 𝑣 𝑇,1 ．

29 主張2の証明 主張2．𝑇 : 頂点数が偶数の木グラフ ∀𝑣∈𝑉 𝑇 , 𝑁 𝑇,−1 ≤ 𝑁 𝑅 𝑣 𝑇,1 ． 𝑇 2 𝑇 1 𝑢 𝑣
∀𝑣∈𝑉 𝑇 , 𝑁 𝑇,−1 ≤ 𝑁 𝑅 𝑣 𝑇,1 ． 𝑇 2 𝑇 1 𝑢 𝑇： 𝑣 ※ 𝑇 1 ≡ 𝑇 2 ≡1 mod 2 補題1: 𝑁 𝑅 𝑣 𝑇,1 ≥ 𝑁 𝑅 𝑣 𝑇 1 , −2 + 𝑁 𝑅 𝑢 𝑇 2 , −1 ． 補題2: 𝑁 𝑇,−1 ≤ 𝑁 𝑅 𝑣 𝑇 1 , −2 + 𝑁 𝑅 𝑢 𝑇 2 , −1 ．

30 主張2の証明 補題1: 𝑁 𝑅 𝑣 𝑇,1 ≥ 𝑁 𝑅 𝑣 𝑇 1 , −2 + 𝑁 𝑅 𝑢 𝑇 2 , −1 ． 𝑇 2 𝑇 1 𝑣 𝑢
補題1: 𝑁 𝑅 𝑣 𝑇,1 ≥ 𝑁 𝑅 𝑣 𝑇 1 , −2 + 𝑁 𝑅 𝑢 𝑇 2 , −1 ． 𝑇 2 𝑇 1 𝑢 𝑇： 𝑣 後手としてプレイ 先手としてプレイ アリスは 𝑇 1 では後手として（ 𝑁 𝑅 𝑣 𝑇 1 , 2=−2 ）, 　　　　　 　 𝑇 2 では先手として（ 𝑁 𝑅 𝑢 𝑇 2 , 1=−1 ）プレイすればよい．

31 主張2の証明 補題2: 𝑁 𝑇,−1 ≤ 𝑁 𝑅 𝑣 𝑇 1 , −2 + 𝑁 𝑅 𝑢 𝑇 2 , −1 ． 𝑇 2 𝑇 1 𝑣 𝑢 𝑇：
補題2: 𝑁 𝑇,−1 ≤ 𝑁 𝑅 𝑣 𝑇 1 , −2 + 𝑁 𝑅 𝑢 𝑇 2 , −1 ． 𝑇 2 𝑇 1 𝑢 𝑇： 𝑣 先手としてプレイ 後手としてプレイ 木グラフでは、帰納法っぽくないかも。K_m,n-treeではがっつり帰納法を使う。 主張1を用いて, 𝑁 𝑇,−2 ≥ 𝑁 𝑅 𝑢 𝑇, −2 ≥ 𝑁 𝑅 𝑣 𝑇 1 , −1 + 𝑁 𝑅 𝑢 𝑇 2 , −2 を示す．

32 定理3.（Seacrest and Seacrest 2012） 任意の頂点数が偶数の木グラフにおいて, アリスは
定理3の証明方針 定理3.（Seacrest and Seacrest 2012） 任意の頂点数が偶数の木グラフにおいて, アリスは ゲームに勝つことができる． 主張1．𝑇 : 木グラフ ∀𝑣∈𝑉 𝑇 , 𝑁 𝑅 𝑣 𝑇,−2 ≤𝑁 𝑇,−2 ．　 主張2．𝑇 : 頂点数が偶数の木グラフ ∀𝑣∈𝑉 𝑇 , 𝑁 𝑇,−1 ≤ 𝑁 𝑅 𝑣 𝑇,1 ． ［定理3の証明］ 主張1, 2より, 𝑁 𝐺,2 ≤ 𝑁 𝑅 𝑣 𝐺,1=−2 ≤𝑁 𝐺,1 ．

33 任意の頂点数偶数の連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフに おいて, アリスはゲームに勝つことができる．
予想2の部分的解決 定理4.（Doki, Egawa and M ） 任意の頂点数偶数の連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフに おいて, アリスはゲームに勝つことができる． Bull 𝑃 5

34 連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフ𝐺が切断点を1頂点以上含む ならば, 𝐺は admissible partition を持つ．
定理4の証明方針 補題. 連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフ𝐺が切断点を1頂点以上含む ならば, 𝐺は admissible partition を持つ． 𝑉(𝐺) 𝑋 2𝑝 𝑋 2𝑝−2 𝑋 2 𝑋 2𝑝−1 𝑋 2𝑝−3 𝑋 1 𝑉(𝐺)の分割 𝑋 1 , 𝑋 2 ,…, 𝑋 2𝑝 で 1≤𝑖,𝑗≤2𝑝 に対し, (i) 𝑖≤𝑗⇒ 𝑋 2𝑗 の各頂点は 𝑋 2𝑖−1 の全ての頂点と隣接する． (ii) 𝑖>𝑗⇒𝐸 𝑋 2𝑖−1 , 𝑋 2𝑗 =𝐸 𝑋 2𝑖 , 𝑋 2𝑗 =𝐸 𝑋 2𝑖−1 , 𝑋 2𝑗−1 =∅ が成り立つとき, この分割を admissible partition と呼ぶ．

35 連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフ𝐺が切断点を1頂点以上含む ならば, 𝐺は admissible partition を持つ．
定理4の証明方針 補題. 連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフ𝐺が切断点を1頂点以上含む ならば, 𝐺は admissible partition を持つ． 𝑉(𝐺)の分割 𝑋 1 , 𝑋 2 ,…, 𝑋 2𝑝 で 1≤𝑖,𝑗≤2𝑝 に対し, (i) 𝑖≤𝑗⇒ 𝑋 2𝑗 の各頂点は 𝑋 2𝑖−1 の全ての頂点と隣接する． (ii) 𝑖>𝑗⇒𝐸 𝑋 2𝑖−1 , 𝑋 2𝑗 =𝐸 𝑋 2𝑖 , 𝑋 2𝑗 =𝐸 𝑋 2𝑖−1 , 𝑋 2𝑗−1 =∅ が成り立つとき, この分割を admissible partition と呼ぶ． 𝑋 6 𝑋 5 𝑋 4 𝑋 3 𝑋 2 𝑋 1

36 連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフ𝐺が切断点を1頂点以上含む ならば, 𝐺は admissible partition を持つ．
定理4の証明方針 補題. 連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフ𝐺が切断点を1頂点以上含む ならば, 𝐺は admissible partition を持つ． 𝑉(𝐺)の分割 𝑋 1 , 𝑋 2 ,…, 𝑋 2𝑝 で 1≤𝑖,𝑗≤2𝑝 に対し, (i) 𝑖≤𝑗⇒ 𝑋 2𝑗 の各頂点は 𝑋 2𝑖−1 の全ての頂点と隣接する． (ii) 𝑖>𝑗⇒𝐸 𝑋 2𝑖−1 , 𝑋 2𝑗 =𝐸 𝑋 2𝑖 , 𝑋 2𝑗 =𝐸 𝑋 2𝑖−1 , 𝑋 2𝑗−1 =∅ が成り立つとき, この分割を admissible partition と呼ぶ． 𝑋 4 𝑋 5 𝑋 6 𝑋 3 𝑋 8 𝑋 1 𝑋 2 𝑋 7

37 連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフ𝐺が切断点を1頂点以上含む ならば, 𝐺は admissible partition を持つ．
定理4の証明方針 補題. 連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフ𝐺が切断点を1頂点以上含む ならば, 𝐺は admissible partition を持つ． 𝑉(𝐺) 𝑋 2𝑝 𝑋 2𝑝−2 𝑋 2 𝑋 2𝑝−1 𝑋 2𝑝−3 𝑋 1 もし切断点が存在すれば, ・切断点の個数は高々2個 ・切断点は 𝑋 1 or 𝑋 2𝑝 に含まれる 分割の各集合に含まれる頂点の重み（の最大値）を比較し, アリスにとって最も都合の良い頂点を取る．

38 連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフ𝐺が切断点を1頂点以上含む ならば, 𝐺は admissible partition を持つ．
定理4の証明方針 補題. 連結 𝑃 5 , 𝐵𝑢𝑙𝑙 -フリーグラフ𝐺が切断点を1頂点以上含む ならば, 𝐺は admissible partition を持つ． もし切断点が存在すれば, ・切断点の個数は高々2個 ・切断点は 𝑋 1 or 𝑋 2𝑝 に含まれる 分割の各集合に含まれる頂点の重み（の最大値）を比較し, アリスにとって最も都合の良い頂点を取る． 𝑋 8 𝑋 7 2 1 3 5 7 4 6 8 𝑋 6 𝑋 5 𝑋 4 𝑋 3 𝑋 2 𝑋 1

39 重みを0と1のみに制限しても, ゲームの勝者を決めるのはPSPACE完全か？
休憩（まとめ） 頂点数 グラフ 偶数 奇数 木グラフ（Tree） ○ （Seacrest & Seacrest, 2012） × 二部グラフ ？（予想1：○） 𝐶 2𝑘+1 -corona-free ？（予想2：○） その他 （○：アリスが勝てる　×：アリスが勝てないグラフと重みの組が存在） 重みが0,1のみの 𝐶 𝑚 -corona-フリーグラフ（Eoh & Choi 2019+）, 重みが0,1のみの 𝐶 2𝑘 -corona（M.）ではアリスが勝てる． 問題1. (Cibulka et al. 2013)　 重みを0と1のみに制限しても, ゲームの勝者を決めるのはPSPACE完全か？

40 Graph grabbing game から派生したゲーム
(i) Graph sharing game ・・・ 取られた頂点からなる誘導部分グラフが常に連結 (ii) Concurrent graph grabbing/sharing game ・・・ 先手の1手目を除き, その時点で ゲームに負けているプレイヤーがプレイする (iii) Convex grabbing game ・・・ 平面上に配置された点でその凸包上の点のみ取れる

41 ・・・ 取られた頂点からなる誘導部分グラフが常に連結
Graph sharing game Graph sharing game ・・・ 取られた頂点からなる誘導部分グラフが常に連結 ← アリスの初手の後, ボブが獲得できるのはその近傍 ※閉路グラフでは, grabbingもsharingも獲得可能な頂点に変わりがない． 閉路グラフ上のgrabbing/sharing gameはPizza gameとも呼ばれる． ＊grabbingはrule R (remaining vertices) , sharingはrule T (taken vertices) と扱うことも.

42 ・・・ 取られた頂点からなる誘導部分グラフが常に連結
Graph sharing game Graph sharing game ・・・ 取られた頂点からなる誘導部分グラフが常に連結 ← アリスの初手の後, ボブが獲得できるのはその近傍 定理5.（Micek and Walczak 2012） 任意の頂点数が奇数の木グラフ上のgraph sharing game において, アリスは全体の1/4以上の重みを獲得可能． アリスが高々2/5しか獲得できない例が存在する．

43 ・・・ 取られた頂点からなる誘導部分グラフが常に連結
Graph sharing game Graph sharing game ・・・ 取られた頂点からなる誘導部分グラフが常に連結 ← アリスの初手の後, ボブが獲得できるのはその近傍 定理6.（Gągol, Micek and Walczak 2017） 任意の自然数𝑛に対し, 以下を満たす定数 𝑐 𝑛 ∈ 0,1 が存在する. 𝐺を頂点数が奇数の連結グラフとする．もし𝐺が 𝐾 𝑛 の細分を 部分グラフとして含まなければ, 𝐺上のgraph sharing game において, アリスは少なくとも 𝑐 𝑛 𝑤 𝐺 以上の重みを獲得可能． 𝑐 𝑛 = 2 −𝑝𝑜𝑙𝑦 𝑛

44 ・・・ 取られた頂点からなる誘導部分グラフが常に連結
Graph sharing game Graph sharing game ・・・ 取られた頂点からなる誘導部分グラフが常に連結 ← アリスの初手の後, ボブが獲得できるのはその近傍 問題2. (Cibulka et al. 2013)　 Graph sharing gameにおいて, ゲームの勝者を決めるのはPSPACE完全か？

45 Concurrent graph grabbing/sharing game
・・・ 先手の1手目を除き, その時点で ゲームに負けているプレイヤーがプレイする ５ Win ! アリス： 　ボブ： １ ７ ５ ９ １ ９ ７ 重み付けには以下の条件を付加する： 「どの異なる二つの頂点部分集合に対しても, その重みの合計は等しくない」

46 Concurrent graph grabbing/sharing game
・・・ 先手の1手目を除き, その時点で ゲームに負けているプレイヤーがプレイする 定理7.（Chaplick et al. 2016） (i) 任意の連結グラフ上のconcurrent graph sharing gameにおいて, アリスは全体の1/3以上の重みを獲得可能． (ii) 任意の木グラフ上のconcurrent graph sharing gameに　おいて, アリスは全体の1/2以上の重みを獲得可能． grabbing ver.においても, 与えられるグラフが切断点を持たなければ, (i)と同様の事実が成り立つ． 他のグラフでは？（完全グラフ, 完全二部グラフ etc.）

47 P：一般の位置に置かれた重み付き点配置（非負整数）
Convex grabbing game 凸包 1 4 5 1 内点 3 1 P：一般の位置に置かれた重み付き点配置（非負整数） アリス （先手） ボブ （後手） 一般の位置 どの３点も同一直線上にない点配置

48 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能
Convex grabbing game 1 4 5 1 3 1 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能 アリス （先手） ボブ （後手）

49 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能
Convex grabbing game 取り除いた後の凸包 1 4 1 3 1 5 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能 アリス （先手） ボブ （後手）

50 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能
Convex grabbing game 1 4 1 3 1 5 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能 アリス （先手） ボブ （後手） 点集合全体の重みの半分以上を獲得したプレイヤーの勝ち （引き分けの場合, アリスの勝ち）

51 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能
Convex grabbing game 1 4 1 3 1 5 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能 アリス （先手） ボブ （後手） 点集合全体の重みの半分以上を獲得したプレイヤーの勝ち （引き分けの場合, アリスの勝ち）

52 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能
Convex grabbing game 1 1 3 1 5 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能 4 アリス （先手） ボブ （後手） 点集合全体の重みの半分以上を獲得したプレイヤーの勝ち （引き分けの場合, アリスの勝ち）

53 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能
Convex grabbing game Win ! 1 1 3 3 1 1 1 1 5 各プレイヤーは凸包の境界上に現れている頂点のみ獲得可能 4 アリス （先手） ボブ （後手） 点集合全体の重みの半分以上を獲得したプレイヤーの勝ち （引き分けの場合, アリスの勝ち）

54 Graph grabbing game and Convex grabbing game
切断点 1 4 2 2 1 1 2 3 Graph grabbing game ある点を取ると, 直前に獲得可能だった点が 取れなくなることがある（切断点になる） we introduce a rooted version of the graph grabbing game, called a rooted game. The rooted game is a graph grabbing game with one additional rule that the specified root of the given graph is grabbed in the last of the game. For example, in this graph with this root, they play the game, like this, the root is grabbed at the last by ボブ. A graph G with root v is denoted by (G,v). Convex grabbing game 凸包上の任意の点を取っても, 直前に獲得可能 である点は新たな凸包上の点になっている

55 問題 ＊任意の点配置に対して, アリスがゲームに勝つような重み付けは無数に存在する． （∵凸包上の1点のみに1以上の重み, その他をすべて0） 問題．任意の重み付けに対して, アリスがゲームに 　　　　勝てる点配置を特徴付けよ． n点配置： n点からなる点配置 偶数（奇数）点配置： 偶数（奇数）個の点を持つ点配置 以降, 紹介する結果は全て論文 “Convex grabbing game of the point set on the plane” （M., Nakamigawa and Sakuma 2019+） から抜粋．

56 点配置Pの全頂点がその凸包上に全て現れている場合 （Convex position）, アリスはP上のゲームで勝てる．
命題8. 点配置Pの全頂点がその凸包上に全て現れている場合 （Convex position）, アリスはP上のゲームで勝てる． ∵重みの大きい頂点から順に獲得していけばよい． 凸包上の任意の1点を　取り除いても, 凸包上の　　　その他の点は新しい凸包上にも現れている． 1 4 1 1 3

57 Pがconvex positionでなければ, アリスがゲームに 勝てない重み付けが存在する．
偶数点配置 定理9. P：任意の偶数点配置 Pがconvex positionでなければ, アリスがゲームに 勝てない重み付けが存在する． 1

58 補題. Pは点配置Hを部分点配置として含む．
定理9の証明方針 補題. Pは点配置Hを部分点配置として含む． 1 R 点配置H Hに含まれない内点は存在しない

59 ボブの戦略．（凸包上の）最も重い点を取る
定理9の証明方針 ボブの戦略．（凸包上の）最も重い点を取る 主張. アリスは重み100の点がなくなる前にRの点を2点以上はとれない． ∵重み100の点は偶数個存在する． 100 100 R 1 100 100 100 100

60 Pの内点の個数が高々2点ならば, アリスはゲームに勝てる．
奇数点配置 定理10. P：任意の奇数点配置 Pの内点の個数が高々2点ならば, アリスはゲームに勝てる． 内点の個数に関する評価は最善． 10 11 1 アリスは高々21しか獲得できない例

61 アリスがゲームに勝てない奇数点配置 命題11. P：任意の奇数点配置 Pが下記の部分点配置Xを含むならば, アリスがゲームに 勝てない重み付けが存在する． 部分点配置X （外側の四角形の内部にはこの3点以外に点は含まれない）

62 P：内点が高々2個（x, y）の奇数点配置 𝑃 ≥7
定理10の証明方針 ＊点の個数の帰納法により証明する 　 （5点以下の場合は先に証明しておく） P：内点が高々2個（x, y）の奇数点配置 𝑃 ≥7 U(P)： 取り除いても重みがより大きい点が 　　　　新たに現れないようなような点の集合 6 3 5 1 4 7 2 x u y 8 v 左図において, 𝑢∈𝑈 𝑃 , 𝑣∉𝑈 𝑃 ＊𝑈 𝑃 ≠𝐸𝑥 𝑃 としてよい． （そうでなければ帰納法によりアリスがゲームに勝てる）

63 定理10の証明方針 𝑤 𝑣 ：頂点vの重み 𝑁 𝑃,1 (𝑁 𝑃,2 )：点配置Pにおけるゲームの 　　　　　　　　　　　 先手（後手）の最適戦略による取り分 𝑢 :𝑈 𝑃 に含まれる最も重みが大きい点 𝑁 𝑃,2 +𝑤 𝑢 <𝑁 𝑃−𝑢,1 ・・・ (*) としてよい． ＊もし, アリスがゲーム終了時まで, 𝑃−𝑢における先手の最適戦略による点を獲得できるならば, 式(*)より, アリスはゲームに勝てる． （すなわち, ボブが自身の最後の1手に点𝑢を獲得する．）

64 𝑤 1 𝑃−𝑢 ∖𝑃′ ： 𝑃−𝑢 上のゲームにおける𝑃′を除いた先手の取り分
定理10の証明方針 そうでない場合, 以下の二つのどちらかが起こる： Case 1. ボブが最後の1手より前に点𝑢を獲得する． Case 2. アリスが𝑃−𝑢における先手の最適戦略に沿った手を打てない． 𝑤 1 𝑃−𝑢 ∖𝑃′ ： 𝑃−𝑢 上のゲームにおける𝑃′を除いた先手の取り分 【Case 1の証明】 𝑃′：ボブが𝑢を取り除いた直後の奇数点配置 帰納法より, 𝑁 𝑃 ′ ,2 ≤𝑁 𝑃 ′ ,1 ．また, 𝑁 𝑃−𝑢,1 = 𝑤 1 𝑃−𝑢 ∖𝑃′ +𝑁 𝑃 ′ ,2 　(1) ゲーム終了時までにアリスとボブが得た重みはそれぞれ, 𝑤 1 𝑃−𝑢 ∖𝑃′ +𝑁 𝑃 ′ ,1 　 (2) 𝑤 2 𝑃−𝑢 ∖𝑃′ +𝑁 𝑃 ′ ,2 +𝑤 𝑢 　 (3) w1(P)は、P上のゲームで先手が獲得した重み（w2(P)は後手）

65 定理10の証明方針 【Case 1の証明続き】 𝑤 2 𝑃−𝑢 ∖𝑃′ +𝑁 𝑃 ′ ,2 +𝑤 𝑢 ・・・ 式(3) ≤ 𝑤 2 𝑃−𝑢 ∖𝑃′ +𝑁 𝑃 ′ ,1 +𝑤 𝑢 =𝑁 𝑃−𝑢,2 +𝑤 𝑢 ・・・式(1) <𝑁 𝑃, ・・・仮定 = 𝑤 1 𝑃−𝑢 ∖𝑃′ +𝑁 𝑃 ′ ,2 　 ・・・式(1) ≤ 𝑤 1 𝑃−𝑢 ∖𝑃′ +𝑁 𝑃 ′ ,1 　 ・・・ 式(2)

66 定理10の証明方針 Case 2. アリスが𝑃−𝑢における先手の最適戦略に沿った手を打てない． 【Case 2の証明】 アリスの初手の後, 少なくとも1点以上の内点が新たな凸包の境界上に現れる． （その初手は𝑃−𝑢における最適戦略による手） 𝑃′：アリスが最適戦略による手を打てなくなった奇数点配置 𝑃 ′ は内点を丁度1点𝑧のみ含む（𝑧：最適戦略による手）． 𝑃 ′ −𝑢はconvex position （i.e., 互いにgreedyに獲得するのが最適手となる）

67 定理10の証明方針 【Case 2の証明】 𝑐 1 , 𝑐 2 ,…, 𝑐 𝑘 : 𝑃 ′ −𝑢 の点で, 𝑤 𝑐 𝑖 ≥𝑤 𝑐 𝑖+1 を満たす． 𝑍 𝑃′ = 𝑝∈ 𝑃 ′ :𝑧∈𝐸𝑥 𝑃 ′ −𝑝 𝑐 1 =𝑧 𝑢∈𝑍 𝑃′ , 𝑍 𝑃′ ≤2 ＊アリスが𝑁 𝑃−𝑢,1 以上の重みを獲得できることを示す アリスは𝑍 𝑃′ の頂点以外で, 獲得可能な重み最大の点を獲得していけばOK．

68 Pの内点の個数が高々4点ならば, アリスはゲームに勝てる．
重みを0,1に制限した奇数点配置 定理12. P：重みが0か1のみの任意の奇数点配置 Pの内点の個数が高々4点ならば, アリスはゲームに勝てる． 内点の個数に関する評価は最善． アリスが高々1しか獲得できない例（白点が重み1）

69 Observations（重み1の点を白点, 0の点を黒点） 白点は奇数個で, かつ, 3個以上 凸包上には白点は現れない
定理12の証明方針（最小反例を考える） Observations（重み1の点を白点, 0の点を黒点） 白点は奇数個で, かつ, 3個以上 凸包上には白点は現れない 凸包上のどの点を取っても, 白点が現れるとしてよい 内点の種類による場合分け Case 1: 白点3個 Case 2: 白点3個と黒点1個 Case 1, 凸包が4角形の場合 凸包の形による場合分け 三つ目の観察により, 凸包上の点は高々6個． Case 1, 2共に高々9点からなる点配置

70 今後の課題 問題3. 　 アリスがゲームに勝つための禁止部分奇数点配置を特徴づけられるか？（PSPACE完全か？） アリスがゲームに勝てない奇数点配置

71 ボブは1点差でアリスに勝てる例（白点が重み1）
今後の課題 問題4. 以下を満たす最大の正整数𝑘を求めよ： ボブがアリスと重み𝑘以上の差を付けてゲームに勝てる重みが0か1のみの奇数点配置が存在する． ボブは1点差でアリスに勝てる例（白点が重み1）

72 問題5. （Convex grabbing gameの多次元ver.）
今後の課題 問題5. （Convex grabbing gameの多次元ver.） 3次元以上の点配置において, アリスがゲームに勝てる点配置の十分条件（内点の個数）を見つけよ． 次元 奇数 偶数 2 〇 （内点2点以下） × （内点1点以上） 3 ？ 4 4次元の偶数ケースは、4次元正単体（正5胞体）の重心に1点置いた図 n次元点配置での一般の位置とは、同一超平面にn+1点以上含まれない （○：アリスが勝てる ×：アリスが勝てない点配置と重み付けが存在） ご清聴ありがとうございました