On the Complexity of Chooser–Picker Positional Games

Abstract

Abstract. Two new versions of the so-called Maker–Breaker Positional Games are defined by József Beck. He defines two players, Picker and Chooser. In each round, Picker takes a pair of elements not already selected and Chooser keeps one and returns the other to Picker. In the Picker–Chooser version Picker plays as Maker and Chooser plays as Breaker, while the roles are swapped in the Chooser–Picker version. The outcome of these games is sometimes very similar to that of the traditional Maker–Breaker games. Here we show that both Picker–Chooser and Chooser–Picker games are NP-hard, which gives support to the paradigm that the games behave similarly while being quite different in definition. We also investigate the pairing strategies for Maker–Breaker games, and apply these results to the game called “Snaky”.