The Game of n-Player White-Black Cutthroat and Its Complexity

摘要

The game of N-player White-Black Cutthroat is an n-player version of White-Black Cutthroat, a two-player combinatorial game played on graphs. Because of queer games, i.e., games where no player has a winning strategy, cooperation is a key-factor in n-player games and, as a consequence, n-player White-Black Cutthroat played on stars is PSPACE-complete.