Abstract | ||
---|---|---|
Two new versions of the so-called Maker-Breaker Positional Games are defined by J\'ozsef Beck in [{\em Combinatorica} {\bf 22}(2) (2002) 169--216]. 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." |
Year | DOI | Venue |
---|---|---|
2011 | 10.1515/integ.2011.113 | Integers |
DocType | Volume | Citations |
Journal | 11 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
András Csernenszky | 1 | 0 | 0.34 |
Ryan R. Martin | 2 | 36 | 10.12 |
András Pluhár | 3 | 89 | 15.12 |