Back in the typecast last month I promised a simple PSPACE-complete game in a future post. Here it is:
The SET GAME
Given: A collection of finite sets S1,...,Sk.
The Game: Each player takes turns picking a non-empty set Si. Remove the elements of Si from all the sets Sj. The player who empties all the sets wins.
This game came up in a discussion I had with Steve Fenner trying to extend his student's work that Poset Games were PSPACE-complete. The PSPACE-completeness of determining a winner of the SET GAME is an easy reduction from from Poset Games.
An open question: Do we still get PSPACE-completeness if the size of the Si are bounded? I don't even know the answer if the sets have size at most two.