Random-player maker-breaker games

Authors Michael Krivelevich, Gal Kronenberg

Publication date 2 November 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.00445, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p9

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

positional games random graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random graphs (graph-theoretic aspects) (05C80) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: In a

(1 : b)

Maker-Breaker game, a primary question is to find the maximal value of

b

that allows Maker to win the game (that is, the critical bias

b^{*}

). ErdH{o}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, "ErdH{o}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

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 sets of

K_{n}

). For each of these games we find or estimate the asymptotic values of

b

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

b

.

Review text

Summary: 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^\ast\)). 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.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Random-player maker-breaker games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q888617)