I learned of this problem through Su Gao, who heard of it years ago while a post-doc at Caltech. David Gale introduced this game in the 70s, I believe. I am only aware of two references in print:
- Richard K. Guy. Unsolved problems in combinatorial games. In Games of No Chance, (R. J. Nowakowski ed.) MSRI Publications 29, Cambridge University Press, 1996, pp. 475-491.
- J. Daniel Christensen and Mark Tilford. David Gale's Subset Take-Away Game. The American Mathematical Monthly, Vol. 104, No. 8 (Oct., 1997), pp. 762-766; jstor, arxiv.
The game depends on a finite set $A$, and is played by two players I and II that alternate, with I playing first. Each move is a subset of $A$. We are given a pool of available subsets, and each move should be a set in the pool. At the beginning, the pool consists of all subsets of $A$ except for $A$ and the empty set. Whenever a set is used in a move, it and all its supersets are removed from the pool. The game ends when the pool is empty, and the player that was to move and cannot (because there are no moves left) loses.
For example, if $|A|\le 2$, then II always wins. If $|A|\le 3$, there is an easy winning strategy for II. To see this, list the elements of $A$ as $a,b,c$ in such a way that the first move of I is either $\{a\}$ or $\{b,c\}$, and have II respond the other one. This means that when I comes to move again, only $\{b\}$ and $\{c\}$ remain, and II wins.
One can also check by hand that II has a winning strategy if $|A|\le 5$, and Christensen-Tilford showed the same when $|A|=6$, although they did not include the code used for their computer verification.
The conjecture is that II always has a winning strategy.
My question is whether there have been any further developments towards establishing this, or any additional references. Suggestions or related ideas are also welcome.
Best Answer
The conjecture that this game is always a second player win has recently been disproved by Brouwer and Christensen (already for $n=7$), https://arxiv.org/abs/1702.03018.