The SET GAME

Given: A collection of finite sets S

_{1},...,S

_{k}.

The Game: Each player takes turns picking a non-empty set S

_{i}. Remove the elements of S

_{i}from all the sets S

_{j}. 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 S

_{i}are bounded? I don't even know the answer if the sets have size at most two.

Interesting; something to investigate...

ReplyDelete