Transitive Avoidance Games

Abstract

Positional games are a well-studied class of combinatorial games. In their usual form, two players take turns to play moves in a set ('the board'), and certain subsets are designated as 'winning': the first person to occupy such a set wins the game. For these games, it is well known that (with correct play) the game cannot be a second-player win.

In the avoidance (or misère) form, the first person to occupy such a set loses the game. Here it would be natural to expect that the game cannot be a first-player win, at least if the game is transitive, meaning that all points of the board look the same. Our main result is that, contrary to this expectation, there are transitive games that are first-player wins, for all board sizes which are not prime or a power of 2.

Further, we show that such games can have additional properties such as stronger transitivity conditions, fast winning times, and 'small' winning sets.