偏ったポジショナルゲーム

偏向ポジショナルゲーム[1] [2] : 27–42は、 ポジショナルゲームの変種である。ほとんどのポジショナルゲームと同様に、位置／ポイント／要素の集合（）と、通常勝利集合と呼ばれる部分集合の族（ ）によって記述される。2人のプレイヤーが交代で要素を取り、すべての要素が取られるまでプレイする。標準ゲームでは各プレイヤーは1ターンに1つの要素を取るが、偏向ゲームでは各プレイヤーが異なる数の要素を取る。 X {\displaystyle X} F {\displaystyle {\mathcal {F}}}

より正式には、 2 つの正の整数pとqに対して、 (p:q)-位置ゲームとは、最初のプレイヤーがターンごとにp個の要素を選択し、2 番目のプレイヤーがターンごとにq個の要素を選択するゲームです。

偏りのあるポジショナルゲームに関して興味深い主な疑問は、その閾値バイアスとは何か、つまり、勝者が 1 人のプレイヤーから他のプレイヤーに移るバイアスとは何かということです。

例

例として、三角形ゲームを考えてみましょう。このゲームでは、要素はすべてn頂点の完全グラフの辺であり、勝利セットはすべて三角形（＝3頂点のクリーク）です。これをMaker-Breakerゲームとしてプレイするとします。つまり、Maker（最初のプレイヤー）の目標は三角形を取ることであり、Breaker（2番目のプレイヤー）の目標はMakerが三角形を取るのを阻止することです。簡単なケース分析を用いると、nが6以上の場合は常にMakerが勝利戦略を持っていることが証明できます。したがって、Breakerが1ターンに1つ以上の要素を選択できるようにすることで、この有利性が偏る可能性があるかどうかを尋ねることは興味深いです。

実際、次のことを証明することは可能である: [1]

  • あらゆる に対して、Maker はn頂点の(1: q ) 三角形ゲームに勝ちます。 q ≤ 0.5 n {\displaystyle q\leq 0.5{\sqrt {n}}}
  • あらゆる に対して、Breaker はn頂点の(1: q ) 三角形ゲームに勝ちます。 q ≥ 2 n {\displaystyle q\geq 2{\sqrt {n}}}

ブレイカーの勝利条件

偏りのないメイカー・ブレーカーゲームにおいて、エルデシュ＝セルフリッジ定理はブレーカーの勝利条件を与える。この条件は、偏りのあるゲームにも以下のように一般化できる：[3] [2] : 30–32 

  • の場合、ブレイカーは先攻の(p:q)ゲームで勝利戦略を持ちます。 ∑ E ∈ F （ 1 + q ） − | E | / p < 1 {\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}
  • の場合、Breaker は後手番でも (p:q) ゲームで勝利する戦略を持ちます。 ∑ E ∈ F （ 1 + q ） − | E | / p < 1 1 + q {\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p{1 \over 1+q}}

この戦略は、エルデシュ＝セルフリッジの関数を一般化したポテンシャル関数を用いる。| E | 個の要素が取られていない（壊れていない）勝利集合Eのポテンシャルは と定義される。もしMakerがゲームに勝った場合、| E |=0 となる集合Eが存在するので、そのポテンシャルは 1 となる。したがって、Breakerが勝ったことを証明するには、最終的なポテンシャル和が 1 未満であることを証明すれば十分である。実際、仮定により、Breakerの最初のターンにおけるポテンシャル和は 1 未満であり、Breakerが常にポテンシャルドロップを最大化する要素を選択するならば、ポテンシャル和は常に弱減少することを示すことが可能である。 （ 1 + q ） − | E | / p {\displaystyle (1+q)^{-|E|/p}}

各勝利セットに要素がある場合、ある固定されたkに対して、ブレーカーの勝利条件は次のように単純化されます。 (先攻時) または(後攻時)。この条件は厳密です。つまり、メーカーが勝利するセットを含むk一様セット族が存在するということです。[4] け {\displaystyle k} | F | < （ q + 1 ） け / p {\displaystyle |{\mathcal {F}}|<(q+1)^{k/p}} | F | < （ q + 1 ） け / p − 1 {\displaystyle |{\mathcal {F}}|<(q+1)^{k/p-1}} | F | ＝ （ q + 1 ） け / p − 1 {\displaystyle |{\mathcal {F}}|=(q+1)^{k/p-1}}

メーカーにとっての勝利条件

偏りのないメイカー・ブレーカーゲームにおいて、ベックの定理はメイカーの勝利条件を与える。この定理は、ハイパーグラフのペア次数 - を用いて表される。この条件は、偏りのあるゲームにも以下のように一般化できる。[3] d 2 {\displaystyle d_{2}}

ならば、Maker は (p:q) ゲームで先攻の場合に勝利戦略を持ちます。 ∑ E ∈ F p + q p − | E | > p 2 q 2 （ p + q ） 3 ⋅ d 2 ⋅ | X | {\displaystyle \sum _{E\in {\mathcal {F}}}{p+q \over p}^{-|E|}>{p^{2}q^{2} \over (p+q)^{3}}\cdot d_{2}\cdot |X|}

回避者にとっての勝利条件

バイアスのある回避者-執行者ゲームでは、以下の条件が回避者が勝利戦略を持つことを保証する: [2] : 47–49 

  • ならば、厳密ルールセットと単調ルールセットの両方において、先攻のAvoiderが(p:q)ゲームに勝利する。これはほぼタイトである。つまり、この式が1よりわずかに大きく、Enforcerが勝利する(p:q)ゲームの無限族が存在する。 ∑ E ∈ F （ 1 + 1 / p ） p − | E | < 1 {\displaystyle \sum _{E\in {\mathcal {F}}}(1+1/p)^{p-|E|} [5]特に、偏りのないゲームでは条件は となる。グラフがk一様であれば、条件は となる。この条件がqに全く依存しないことは注目に値する。 ∑ E ∈ F 2 1 − | E | < 1 {\displaystyle \sum _{E\in {\mathcal {F}}}2^{1-|E|} | F | < （ 1 + 1 / p ） け − 1 {\displaystyle |{\mathcal {F}}|<(1+1/p)^{k-1}}
  • 各勝利セットに最大でk個の要素がある場合、 Avoiderが先攻で(p:q)ゲームに勝利する。 ∑ E ∈ F （ 1 + q p け ） p − | E | < 1 {\displaystyle \sum _{E\in {\mathcal {F}}}\left(1+{q \over pk}\right)^{p-|E|}}} [6]

参照

参考文献

  1. ^ ab Chvátal, V.; Erdös, P. (1978). 「バイアス付きポジショナルゲーム」 . Annals of Discrete Mathematics . 2 (C): 221– 229. doi :10.1016/S0167-5060(08)70335-2. ISSN  0167-5060.
  2. ^ abc ヘフェッツ、ダン;マイケル・クリヴェビッチ;ストヤコビッチ、ミロシュ。ティボル・サボ（2014）。ポジショナルゲーム。オーバーヴォルファッハセミナー。 Vol. 44. バーゼル: Birkhäuser Verlag GmbH。ISBN 978-3-0348-0824-8。
  3. ^ ab ベック、J. (1982)。 「位置戦に関する考察・Ⅰ」。Acta Mathematica Academiae Scientiarum Hungaricae。40 ( 1–2 ): 65– 71.土井: 10.1007/bf01897304。ISSN  0001-5954。
  4. ^ Sundberg, Eric Lars (2013-05-02). 「バイアス付きエルデシュ＝セルフリッジ定理のための極値ハイパーグラフ」. The Electronic Journal of Combinatorics . 20 (1). doi : 10.37236/2394 . ISSN  1077-8926.
  5. ^ Hefetz, Dan; Krivelevich, Michael; Szabó, Tibor (2007-07-01). 「回避者-執行者ゲーム」 . Journal of Combinatorial Theory, Series A. 114 ( 5): 840– 853. doi : 10.1016/j.jcta.2006.10.001 . ISSN  0097-3165.
  6. ^ Bednarska-Bzdęga, Małgorzata (2014-01-12). 「小さなランクを持つハイパーグラフ上のAvoider-Forcerゲーム」. The Electronic Journal of Combinatorics . 21 (1): 1– 2. doi : 10.37236/3095 . ISSN  1077-8926.
「https://en.wikipedia.org/w/index.php?title=Biased_positional_game&oldid=1308970540」より取得