{{Other uses|Box game (disambiguation){{!}}Box game}}
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.'''<ref name="Chvátal 1978">{{Cite journal|last=Chvátal|first=V.|last2=Erdös|first2=P.|date=1978|title=Biased Positional Games|url=https://hungary.pure.elsevier.com/en/publications/biased-positional-games|journal=Annals of Discrete Mathematics|language=English|volume=2|issue=C|pages=221–229|doi=10.1016/S0167-5060(08)70335-2|issn=0167-5060|url-access=subscription}}</ref>''' It was solved later by Hamidoune and Las-Vergnas.<ref name="Hamidoune 1987">{{Cite journal|date=1987-06-01|title=A solution to the Box Game|journal=Discrete Mathematics|language=en|volume=65|issue=2|pages=157–171|doi=10.1016/0012-365X(87)90138-5|issn=0012-365X|last1=Hamidoune|first1=Yahya Ould|last2=Las Vergnas|first2=Michel|doi-access=free}}</ref>
== Definition == A box game is defined by:
* A family of ''n'' pairwise-disjoint sets, <math>A_1,\ldots,A_n</math>, 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<ref name="Hamidoune 1987" /> 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:'''<ref name="pg14">{{Cite Positional Games 2014}}</ref>'''{{Rp|36-39}}
* ''If all boxes have the same size k, and <math>p\cdot \sum_{i=1}^n {1\over i} < k</math>, 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: <math>n < (q+1)^{k/p}</math>. With ''q''=1 this becomes <math>p\cdot \log_2{n} < k</math>. The proof uses a potential function. The potential of the game before BoxBreaker's ''j''-th move is defined as: <math>{1\over n-j+1}\sum_{i=j}^n c_i</math> where <math>c_i</math> is the number of elements remaining in box ''i''. * ''If the boxes have different sizes <math>k_1,\ldots,k_n</math>, and <math>\sum_{i=1}^n e^{-k_i/p} < {1/e}</math>, then BoxBreaker wins the (p:1) box game.'' For comparison, the winning condition for Breaker in a general (p:q) biased game is: ''<math>\sum_{i=1}^n (1+q)^{-k_1/p} < {1\over 1+q}</math>''. With q=1 this becomes ''<math>\sum_{i=1}^n 2^{-k_i/p} < {1\over 2}</math>''.
== References == {{reflist}}
Category:Positional games