箱作りゲーム

箱作りゲーム（単に箱ゲームと呼ばれることが多い）は、2人のプレイヤーが交互に、互いに素な集合（「箱」）の族から要素を選ぶ、偏りのあるポジショナルゲームです。最初のプレイヤー（ BoxMaker）は、1つの箱のすべての要素を選ぼうとします。2番目のプレイヤー（BoxBreaker）は、すべての箱から少なくとも1つの要素を選ぼうとします。

ボックスゲームは、ポール・エルデシュとヴァーツラフ・フヴァータルによって初めて発表されました。^[1] その後、ハミドゥーンとラス＝ベルニャスによって解かれました。^[2]

意味

ボックス ゲームは次のように定義されます。

• 異なるサイズのn個の互いに素な集合の族。集合はしばしば「箱」と呼ばれ、要素は「球」と呼ばれる。${\displaystyle A_{1},\ldots ,A_{n}}$
• 2 つの整数pとq。

最初のプレイヤーBoxMaker は、同じ箱または異なる箱からp 個のボールを取ります。次に、2番目のプレイヤーBoxBreakerはq 個の箱を割ります。以下同様に繰り返します。

BoxMakerは、BoxBreakerがこの箱を壊す前に、少なくとも1つの箱の中のすべてのボールを拾うことができれば勝ちです。BoxBreakerは、すべての箱を壊すことができれば勝ちです。

戦略

一般的に、BoxBreakerの最適戦略は、残っている要素の数が最も少ない箱を壊すことです。BoxMakerの最適戦略は、すべての箱のサイズを均等にすることです。これらの戦略をシミュレーションすることで、HamidouneとLas-Vergnas ^[2]は、( p : q )ボックスゲームにおける各プレイヤーの十分条件と必要条件を発見しました。

q =1の特別なケースでは、以下の条件のそれぞれが十分である: ^{[3] : 36–39}

• すべての箱のサイズが同じ k で、 の場合、 BoxBreaker は (p:1) 箱ゲームに勝利します（最小の箱を壊すという明白な戦略を使用）。比較のために、一般的な ( ${\displaystyle p\cdot \sum _{i=1}^{n}{1 \over ik}$ p : q ) バイアスゲーム における Breaker の勝利条件は です。q =1 の場合、これは になります。証明にはポテンシャル関数を使用します。 BoxBreaker のj番目の移動前のゲームのポテンシャルは次のように定義されます。ここで、 は箱iに残っている要素の数です。${\displaystyle n<(q+1)^{k/p}}$ ${\displaystyle p\cdot \log _{2}{n}$ ${\displaystyle {1 \over n-j+1}\sum _{i=j}^{n}c_{i}}$ ${\displaystyle c_{i}}$
• 箱の大きさが、、 と異なる場合、BoxBreaker は (p:1) の箱ゲームに勝利します。${\displaystyle k_{1},\ldots,k_{n}}$ ${\displaystyle \sum _{i=1}^{n}e^{-k_{i}/p}$ 比較のために、一般的な (p:q) バイアスゲームにおける Breaker の勝利条件は です。q =1 の場合、これは となります。${\displaystyle \sum _{i=1}^{n}(1+q)^{-k_{1}/p} は、$ ${\displaystyle \sum _{i=1}^{n}2^{-k_{i}/p}{1 \over 2}}$

参考文献

1. 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. Hamidoune, Yahya Ould; Las Vergnas, Michel (1987-06-01). 「ボックスゲームの解」.離散数学. 65 (2): 157– 171. doi : 10.1016/0012-365X(87)90138-5 . ISSN  0012-365X.
3. ダン・ヘフェッツ;マイケル・クリヴェビッチ;ストヤコビッチ、ミロシュ。ティボル・サボ（2014）。ポジショナルゲーム。オーバーヴォルファッハセミナー。 Vol. 44. バーゼル: Birkhäuser Verlag GmbH。ISBN 978-3-0348-0824-8。