Metraipolis › archive › dc_88c8aa223e33
Maker Breaker Games on a Budget — arXiv:2609.38138
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.38138
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T18:33:55.856Z
- SHA-256 of the archived text
fcbe21da3627109991ef721a4e1b05f7f1b03bba6f468175ccc5be8db17672af- Stable URL of this page
https://metraipolis.com/documento/dc_88c8aa223e33
How to cite
Maker Breaker Games on a Budget — arXiv:2609.38138 — arXiv (en), https://arxiv.org/abs/2609.38138 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_88c8aa223e33 (Metraipolis archive dc_88c8aa223e33, sha256 fcbe21da3627109991ef721a4e1b05f7f1b03bba6f468175ccc5be8db17672af)
BibTeX
@misc{dc88c8aa223e33,
title = {Maker Breaker Games on a Budget — arXiv:2609.38138},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.38138},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_88c8aa223e33; sha256 fcbe21da3627109991ef721a4e1b05f7f1b03bba6f468175ccc5be8db17672af},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.38138. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Maker Breaker Triangle Game involves two players, Maker and Breaker, who alternately claim 1 and $q$ edges of $K_n$, respectively. Maker's goal is to claim all three edges of any triangle, whereas Breaker's goal is to prevent this. The threshold bias, i.e. the minimum $q$ such that Breaker wins, is known to lie between $\big\lceil\sqrt{2n-2}-\frac{3}{2}\big\rceil$ and $\big(\sqrt{8/3}+o(1)\big)\sqrt{n}$. Determining its exact value is a longstanding open problem. In this paper, we introduce a novel version of the game in which Breaker may claim fewer than $q$ edges per round to build up a budget that he can spend in later rounds. With this additional power for Breaker, we determine the threshold bias to be precisely $\big\lceil\sqrt{2n-2}-\frac{3}{2}\big\rceil$ for all $n$, matching the known lower bound. This is the first version of the Maker Breaker Triangle Game for which the exact threshold bias is known. Even if Breaker is not allowed to use the budget for threats, we prove that the threshold bias is still $\big(\sqrt{2}+o(1)\big)\sqrt{n}$. Furthermore, we study the budget version of other Maker Breaker Games. Specifically, for the $K_4$-Game, we prove the first explicit lower and upper bounds on the threshold bias in both the original and the budget version of the game.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.38138 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T17:59:19.271Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).