2022/09/22 by Lear Bahack, Bahack, Lear
Computer Science · Decision Sciences · Psychology · #Artificial Intelligence in Games #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Gambling Behavior and Treatments #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.2209.11202
openalex publication_date 2022/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A rank-3 Maker-Breaker game is played on a hypergraph in which all hyperedges are sets of at most 3 vertices. The two players of the game, called Maker and Breaker, move alternately. On his turn, maker chooses a vertex to be withdrawn from all hyperedges, while Breaker on her turn chooses a vertex and delete all the hyperedges containing that vertex. Maker wins when by the end of his turn some hyperedge is completely covered, i.e. the last remaining vertex of that hyperedge is withdrawn. Breaker wins when by the end of her turn, all hyperedges have been deleted. Solving a Maker-Breaker game is the computational problem of choosing an optimal move, or equivalently, deciding which player has a winning strategy in a configuration. The complexity of solving two degenerate cases of rank-3 games has been proven before to be polynomial. In this paper, we show that the general case of rank-3 Maker-Breaker games is also solvable in polynomial time.