2019/07/10 by Ander Lamaison, Lamaison, Ander
Decision Sciences · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Applications #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1907.04804
openalex publication_date 2019/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a (1:b) biased Maker-Breaker game, how good a strategy is for a player can be measured by the bias range for which its rival can win, choosing an appropriate counterstrategy. Bednarska and Łuczak proved that, in the H-subgraph game, the uniformly random strategy for Maker is essentially optimal with high probability. Here we prove an analogous result for the H-graph minor game, and we study for which choices of H the random strategy is within a factor of 1+o(1) of being optimal.