Random-player maker-breaker games

Michael Krivelevich¹ ; Gal Kronenberg¹

¹Tel Aviv university

The electronic journal of combinatorics, Tome 22 (2015) no. 4

Résumé

In a $(1:b)$ Maker-Breaker game, one of the central questions is to find the maximal value of $b$ that allows Maker to win the game (that is, the critical bias $b^*$). Erdős conjectured that the critical bias for many Maker-Breaker games played on the edge set of $K_n$ is the same as if both players claim edges randomly. Indeed, in many Maker-Breaker games, "Erdős Paradigm" turned out to be true. Therefore, the next natural question to ask is the (typical) value of the critical bias for Maker-Breaker games where only one player claims edges randomly. A random-player Maker-Breaker game is a two-player game, played the same as an ordinary (biased) Maker-Breaker game, except that one player plays according to his best strategy and claims one element in each round, while the other plays randomly and claims $b$ (or $m$) elements. In fact, for every (ordinary) Maker-Breaker game, there are two different random-player versions; the $(1:b)$ random-Breaker game and the $(m:1)$ random-Maker game. We analyze the random-player version of several classical Maker-Breaker games such as the Hamilton cycle game, the perfect-matching game and the $k$-vertex-connectivity game (played on the edge set of $K_n$). For each of these games we find or estimate the asymptotic values of the bias (either $b$ or $m$) that allow each player to typically win the game. In fact, we provide the "smart" player with an explicit winning strategy for the corresponding value of the bias.

Détail

DOI : 10.37236/5032

Classification : 05C57, 05C80, 91A43, 91A24
Mots-clés : random graphs, positional games