What is the winning strategy for this Game on the Power Set

Given a finite set, players alternately choose proper subsets. Once a subset has been chosen, none of its subsets may be chosen later. The last player to move wins.

I figured out that, with optimal play, Player 1 wins. This is because he can either choose the null set and give away his move, becoming the second player, or not choose the null set and do a "real" move, staying the first player. Because he can choose, and one player wins with optimal play, Player 1 must win. However, I can't figure out a strategy for him, other than choosing/not choosing the null set.

Solution 1:

This game is very well known. Unfortunately, it has many different names, and very few known results.

Names/related games

Chomp is a game usually played on a rectangle where players take bites but cannot eat the top-left square. For the finite set of size $2$, this game is $2\times2$ chomp in this way: $$\begin{array}{|c|c|}\hline \boxed{\{1,2\}}& \{1\} \\ \hline \{2\}& \emptyset \\ \hline\end{array}$$ This can be generalized to high dimensions, using the $n$-cube, so that your game is equivalent to "$n$-dimensional Chomp on a $2\times2\times\cdots\times2$ board".

Andries E. Brouwer has a nice page on Chomp with a lot of information. Your game is mentioned in the section "Chomp on a simplicial complex", although he uses the opposite convention, where the moves are the complements of the moves you describe, so that taking the whole set would be like taking the empty set and taking the empty set would make you lose (taking the whole set is disallowed in your description). He also mentions this game can be called "Schuh's game for square-free $N$" (here players select divisors), "subset takeaway", "hyperchomp" (as used on Jan Draisma's recreational maths page [broken]), and the "superset game".

Results

In Nim-type games by Gale and Neyman, it was conjectured that the winning move to the subset game is always to take the maximal element (in your game's terms, to take $\emptyset$ first). This is shown (after recasting the game so that it starts after that standardized move) for $n=1,2,3$ in Albert Meyer's notes for Mathematics for Computer Science [broken] and $n=4$ in the corresponding solutions [broken]. At Brouwer's page mentioned earlier, and in the paper On Three-rowed Chomp by Brouwer, Horváth, Molnár-Sáska, and Szabó, it is mentioned that this remains true for $n=5,6,7$.

I do not know of any further results, but this superset game was mentioned in Guy and Nowakowski's list of unsolved problems in CGT from More Games of No Chance so that any further progress would have been in the past 15 years or so, but I cannot find anything else.

Edit: The links to Meyer's notes are broken now, but the full textbook has the same thing without the solutions if you search for "game". I have no replacement link for Jan Draisma's page. Also, a lot more information and recent developments can be found at the MO question David Gale's subset take-away game