Chasing the threshold bias of the 3-AP game

MaRDI QIDQ5869447zbMATH OpenFDO

Authors Albert Cao, Felix Christian, Clemen Sean English, Xiao-Jian Li, Tatum Schmidt, Leeann Xoubi, Weian Yin

Publication date 28 September 2022

Full work available at URL https://arxiv.org/abs/2109.03083, http://ajc.maths.uq.edu.au/pdf/84/ajc_v84_p167.pdf

zbMATH Keywords

games on hypergraphsmaker-breaker game

Mathematics Subject Classification ID

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

Abstract: In a Maker-Breaker game there are two players, Maker and Breaker, where Maker wins if they create a specified structure while Breaker wins if they prevent Maker from winning indefinitely. A $3$-term arithmetic progression, or $3$-AP, is a sequence of three distinct integers $a,b,c$ such that $b-a=c-b$. The $3$-AP game is a biased Maker-Breaker game played on $[n]$ where every round Breaker selects $q$ unclaimed integers for every Maker's one integer. Maker is trying to select points such that they have a $3$-AP and Breaker is trying to prevent this. The main question of interest is determining the threshold bias $q^{\ast }(n)$, that is the minimum value of $q=q(n)$ for which Breaker has a winning strategy. Kusch, Ru'e, Spiegel and Szab'o initially asked this question and proved $sqrtn/12-1/6leq{q}^{\ast }(n)leqsqrt3n$. We find new strategies for both Maker and Breaker which improve the existing bounds to [ (1+o(1))sqrt{frac{n}{5.6}} leq q^*(n) leq sqrt{2n} +O(1). ]

Recommendations

• A new bound for the Maker-Breaker triangle game
• Random strategies are nearly optimal for generalized van der Waerden games
• On Biased Positional Games
• Winning fast in biased maker-breaker games
• On the optimality of the uniform random strategy

Cites work

• A new bound for the Maker-Breaker triangle game
• Biased Positional Games
• Combinatorial Games
• Mini-workshop: Positional games. Abstracts from the mini-workshop held September 30 -- October 6, 2018
• On a combinatorial game
• On the Chvàtal-Erdős triangle game
• On the optimality of the uniform random strategy
• Positional games
• Remarks on positional games. I

Cited in

(1)

• Maker-breaker Rado games for equations with radicals

This page was built for publication: Chasing the threshold bias of the 3-AP game

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