Maker Breaker Games on a Budget
Abstract
The Maker Breaker Triangle Game involves two players, Maker and Breaker, who alternately claim 1 and q edges of Kn, 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 ⌈√(2n−2)−3/2⌉ and (√(8/3)+o(1))√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 ⌈√(2n−2)−3/2⌉ 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 (√2+o(1))√n. Furthermore, we study the budget version of other Maker Breaker Games. Specifically, for the K4-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.
Related
- Ramsey-type results for Maker-Breaker games
- Breaker Chains and Splitting of Interval Submodules in Zigzag Modules
- Epidemic Control using Stackelberg Mean Field Game with Budget Constraint
- Low-Budget Active Learning through Entropic Optimal Transport
- Budget-Constrained Multi-Consensus Decentralized Gradient Descent
BibTeX
@misc{luderssen2026maker,
title = {{Maker Breaker Games on a Budget}},
author = {Sebastian Lüderssen and Fabien Nießen and Silas Rathke},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38138},
eprint = {2609.38138},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38138},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Maker Breaker Games on a Budget
AU - Sebastian Lüderssen
AU - Fabien Nießen
AU - Silas Rathke
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.38138
UR - https://arxiv.org/abs/2609.38138
AB - 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 ⌈√(2n−2)−3/2⌉ and (√(8/3)+o(1))√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 ⌈√(2n−2)−3/2⌉ 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 (√2+o(1))√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.
ER -