Chasing the threshold bias of the 3-AP game

zbMATH Open1497.05175arXiv2109.03083MaRDI QIDQ5869447FDOQ5869447

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

Publication date: 28 September 2022

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). ]

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

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

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)

Cites Work

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

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)