Misplaced Pages

A box-making game (often called just a box game) is a biased positional game where two players alternately pick elements from a family of pairwise-disjoint sets ("boxes"). The first player - called BoxMaker - tries to pick all elements of a single box. The second player - called BoxBreaker - tries to pick at least one element of all boxes.

The box game was first presented by Paul Erdős and Václav Chvátal. It was solved later by Hamidoune and Las-Vergnas.

Definition

A box game is defined by:

• A family of n pairwise-disjoint sets, ${\displaystyle A_{1},\ldots ,A_{n}}$, of different sizes. The sets are often called "boxes" and the elements are called "balls".
• Two integers, p and q.

The first player, BoxMaker, picks p balls (from the same or different boxes). Then the second player, BoxBreaker, breaks q boxes. And so on.

BoxMaker wins if he has managed to pick all balls in at least one box, before BoxBreaker managed to break this box. BoxBreaker wins if he has managed to break all the boxes.

Strategies

In general, the optimal strategy for BoxBreaker is to break the boxes with the smallest number of remaining elements. The optimal strategy for BoxMaker is to try to balance the sizes of all boxes. By simulating these strategies, Hamidoune and Las-Vergnas found a sufficient and necessary condition for each player in the (p:q) box game.

For the special case where q=1, each of the following conditions is sufficient:

• If all boxes have the same size k, and ${\displaystyle p\cdot \sum _{i=1}^{n}{1 \over i}<k}$, then BoxBreaker wins the (p:1) box game (using the obvious strategy of breaking the smallest boxes). For comparison, the winning condition for Breaker in a general (p:q) biased game is: ${\displaystyle n<(q+1)^{k/p}}$. With q=1 this becomes ${\displaystyle p\cdot \log _{2}{n}<k}$. The proof uses a potential function. The potential of the game before BoxBreaker's j-th move is defined as: ${\displaystyle {1 \over n-j+1}\sum _{i=j}^{n}c_{i}}$ where ${\displaystyle c_{i}}$ is the number of elements remaining in box i.
• If the boxes have different sizes ${\displaystyle k_{1},\ldots ,k_{n}}$, and ${\displaystyle \sum _{i=1}^{n}e^{-k_{i}/p}<{1/e}}$, then BoxBreaker wins the (p:1) box game. For comparison, the winning condition for Breaker in a general (p:q) biased game is: ${\displaystyle \sum _{i=1}^{n}(1+q)^{-k_{1}/p}<{1 \over 1+q}}$. With q=1 this becomes ${\displaystyle \sum _{i=1}^{n}2^{-k_{i}/p}<{1 \over 2}}$.

References

1. Chvátal, V.; Erdös, P. (1978). "Biased Positional Games". 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). "A solution to the Box Game". Discrete Mathematics. 65 (2): 157–171. doi:10.1016/0012-365X(87)90138-5. ISSN 0012-365X.
3. Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Positional Games. Oberwolfach Seminars. Vol. 44. Basel: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.

• Positional games