On Biased Positional Games
This paper analyzes a particular subclass of a class of graph games introduced and analyzed by Erdős. A game from this subclass is characterized by three integer parameters: \(N\), \(n\), and \(q\). In this game, two players, Breaker and Maker, play on a complete graph with \(N\) vertices. On each move, the Breaker selects \(q\) (or fewer) previously unselected edges; then, the Maker selects one previously unselected edge. The goal of the Maker is to select a binary tree with \(n\) vertices in the first \(n-1\) moves, the goal of the Breaker is to prevent the Maker from doing it. The authors shows that the existence of a winning strategy for the Maker depends on the relative value of \(q\), with \(q=N/\log(n)\) acting as an asymptotic threshold: when \(n=o(N)\), then for every \(\varepsilon>0\), there exists \(n_0\) such that for all \(n\geq n_0\), the Breaker has a winning strategy if \(q>(1+\varepsilon)\cdot N/\log(n)\) and the Maker has a winning strategy if \(q<(1-\varepsilon)\cdot N/\log(n)\). Attention: there is a confusing typo in the paper's abstract, so that this abstract erroneously claims that the \textit{Maker} selects \(q\) edges.
- Biased positional games on matroids
- A new bound for the Maker-Breaker triangle game
- On the biased \(n\)-in-a-row game
- Allowing two moves in succession increases the game's bias: A theorem
- Biased positional games and the phase transition
- Fast embedding of spanning trees in biased maker-breaker games
- Building spanning trees quickly in maker-breaker games
- Biased Positional Games
- Fast embedding of spanning trees in biased maker-breaker games
- Biased games on random boards
- Chasing the threshold bias of the 3-AP game
- Biased positional games for which random strategies are nearly optimal
- Fast winning strategies in avoider-enforcer games
This page was built for publication: On Biased Positional Games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4238163)
