Poset Games are PSPACE-complete

Consider the following game on a poset, each player takes turns picking an element x of a finite poset and removes all y ≥ x. First one to empty the poset wins. I posted last March about a high school student, Adam Kalinich, who showed how to flip the winner of a poset game.

Finding the winner of a poset game is in PSPACE by searching the game tree. A corollary of Adam's work showed that poset games were hard for Boolean formula leaving a huge gap in the complexity of finding the winner.

Daniel Grier, an undergrad at the University of South Carolina, has settled the problem and shows that determining the winner of a poset game is PSPACE-complete. His reduction is ridiculously simple (though not obvious) and the proof is not that complicated either.

Grier starts from Node Kayles which is a game on an undirected graph where each player takes turns removing a vertex and all its neighbors. Whomever empties the graph first wins. Thomas Schaefer showed the PSPACE-completeness of Node Kayles back in 1978.

Grier's reduction from Node Kayles to posets is very simple: Let G be the graph. Have one element in the poset for each vertex of G, all incomparable. For each edge e=(u,v) we add two more elements, one above the vertex elements corresponding to u and v, and one below every vertex element other than u and v. That's the whole construction.

Grier shows that if G has an odd number of edges and no immediate win for the first player then the first player wins the Node Kayles game if and only if the first player wins the corresponding poset game.

You can read more details in Grier's short paper. It's really neat seeing high school students and undergrads solving interesting open problems. We need more problems like poset games.