Sharp thresholds for half-random games. II

DOI10.1007/S00373-016-1753-4zbMATH Open1368.05102arXiv1602.04628OpenAlexW2963483240MaRDI QIDQ2014222FDOQ2014222

Authors: Jonas Groschwitz, Tibor Szabó 

Publication date: 10 August 2017

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: We study biased Maker-Breaker positional games between two players, one of whom is playing randomly against an opponent with an optimal strategy. In this work we focus on the case of Breaker playing randomly and Maker being "clever". The reverse scenario is treated in a separate paper. We determine the sharp threshold bias of classical games played on the edge set of the complete graph $K_n$, such as connectivity, perfect matching, Hamiltonicity, and minimum degree-$1$. In all of these games, the threshold is equal to the trivial upper bound implied by the number of edges needed for Maker to occupy a winning set. Moreover, we show that the clever Maker can not only win against an asymptotically optimal bias, but can do so very fast, wasting only logarithmically many moves (while the winning set sizes are linear in $n$).

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

Recommendations

• Sharp thresholds for half-random games. I.
• Positional games on random graphs
• Random-player maker-breaker games
• Biased games on random boards
• Biased positional games for which random strategies are nearly optimal

zbMATH Keywords

connectivityrandomized strategypositional gamessharp thresholdHamiltonicityfast win

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Asymptotic random graph intuition for the biased connectivity game
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Biased Positional Games
• On two problems regarding the Hamiltonian cycle game
• Weak and strong \(k\)-connectivity games
• Fast winning strategies in maker-breaker games
• Winning strong games through fast strategies for weak games
• Fast winning strategies in avoider-enforcer games
• Random-player maker-breaker games
• On winning fast in Avoider-Enforcer games
• Sharp thresholds for half-random games. I.

Cited In (6)

• Positional games on random graphs
• Sharp thresholds for half-random games. I.
• Random-player maker-breaker games
• Efficient winning strategies in random-turn maker-breaker games
• Random strategies are nearly optimal for generalized van der Waerden games
• Asymptotic random graph intuition for the biased connectivity game

This page was built for publication: Sharp thresholds for half-random games. II

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