Premium
Efficient Winning Strategies in Random‐Turn Maker–Breaker Games
Author(s) -
Ferber Asaf,
Krivelevich Michael,
Kronenberg Gal
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22072
Subject(s) - mathematics , mathematical economics , combinatorics , vertex (graph theory) , combinatorial game theory , repeated game , game tree , sequential game , strategy , set (abstract data type) , game theory , computer science , graph , programming language
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ős 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 that 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.