Efficient winning strategies in random-turn Maker-Breaker games

Abstract

We consider random-turn positional games, introduced by Peres, Schramm, Sheffield and Wilson in 2007. A $p$-random-turn positional game is a two-player game, played the same as an ordinary positional game, except that instead of alternating turns, a coin is being tossed before each turn to decide the identity of the next player to move (the probability of Player I to move is $p$). We analyze the random-turn version of several classical Maker-Breaker games such as the game Box (introduced by Chvátal and Erd\H os in 1987), the Hamilton cycle game and the $k$-vertex-connectivity game (both played on the edge set of $K_n$). For each of these games we provide each of the players with a (randomized) efficient strategy which typically ensures his win in the asymptotic order of the minimum value of $p$ for which he typically wins the game, assuming optimal strategies of both players.

20 pages