Biased games on random boards

DOI10.1002/RSA.20528zbMATH Open1325.91014arXiv1210.7618OpenAlexW1530612577MaRDI QIDQ5265341FDOQ5265341

Authors: Asaf Ferber, Roman Glebov, Michael Krivelevich, Alon Naor 

Publication date: 23 July 2015

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: In this paper we analyze biased Maker-Breaker games and Avoider-Enforcer games, both played on the edge set of a random board $Gsimgnp$. In Maker-Breaker games there are two players, denoted by Maker and Breaker. In each round, Maker claims one previously unclaimed edge of $G$ and Breaker responds by claiming $b$ previously unclaimed edges. We consider the Hamiltonicity game, the perfect matching game and the $k$-vertex-connectivity game, where Maker's goal is to build a graph which possesses the relevant property. Avoider-Enforcer games are the reverse analogue of Maker-Breaker games with a slight modification, where the two players claim at least 1 and at least $b$ previously unclaimed edges per move, respectively, and Avoider aims to avoid building a graph which possesses the relevant property. Maker-Breaker games are known to be "bias-monotone", that is, if Maker wins the $(1,b)$ game, he also wins the $(1,b-1)$ game. Therefore, it makes sense to define the critical bias of a game, $b^{\ast }$, to be the "breaking point" of the game. That is, Maker wins the $(1,b)$ game whenever $bleq{b}^{\ast }$ and loses otherwise. An analogous definition of the critical bias exists for Avoider-Enforcer games: here, the critical bias of a game $b^{\ast }$ is such that Avoider wins the $(1,b)$ game for every $b>b^{\ast }$, and loses otherwise. We prove that, for every $p=omega(fraclnnn)$, $Gsimgnp$ is typically such that the critical bias for all the aforementioned Maker-Breaker games is asymptotically $b^{\ast }=fracnplnn$. We also prove that in the case $p=Theta(fraclnnn)$, the critical bias is $b^{\ast }=Theta(fracnplnn)$. These results settle a conjecture of Stojakovi'c and Szab'o. For Avoider-Enforcer games, we prove that for $p=Omega(fraclnnn)$, the critical bias for all the aforementioned games is $b^{\ast }=Theta(fracnplnn)$.

Full work available at URL: https://arxiv.org/abs/1210.7618

Recommendations

• scientific article; zbMATH DE number 3946179
• On Biased Positional Games
• Biased positional games for which random strategies are nearly optimal
• A note on biased and non-biased games
• Biased positional games on matroids
• Biased Positional Games
• On the biased \(n\)-in-a-row game
• Trapping games on random boards

zbMATH Keywords

random graphspositional games

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Avoider-Enforcer games
• Asymptotic random graph intuition for the biased connectivity game
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Remarks on positional games. I
• Biased Positional Games
• Combinatorial Games
• A Solution of the Shannon Switching Game
• On two problems regarding the Hamiltonian cycle game
• Weak and strong \(k\)-connectivity games
• Fast winning strategies in maker-breaker games
• Hitting time results for maker-breaker games
• Fast strategies in maker-breaker games played on random boards
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• Positional games on random graphs
• Biased positional games and small hypergraphs with large covers
• Hamilton cycles in highly connected and expanding graphs
• On two Hamilton cycle problems in random graphs

Cited In (23)

• Maker-Breaker games on randomly perturbed graphs
• Random directed graphs are robustly Hamiltonian
• Positional games on random graphs
• Multistage positional games
• On the biased \(n\)-in-a-row game
• Biased positional games and small hypergraphs with large covers
• Creating cycles in walker-breaker games
• Sharp thresholds for half-random games. I.
• Sharp thresholds for half-random games. II
• Avoider-enforcer: the rules of the game
• Biased positional games and the phase transition
• Random-player maker-breaker games
• Connector-breaker games on random boards
• Generating random graphs in biased maker-breaker games
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Galton–Watson games
• Asymptotic random graph intuition for the biased connectivity game
• Avoider-Enforcer: the rules of the game
• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• Biased Positional Games
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• Allowing two moves in succession increases the game's bias: A theorem
• Component games on regular graphs

This page was built for publication: Biased games on random boards

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