2026-10-01T07:51:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25529 2026-09-23T23:43:03Z ddc:004 open_access

Maker-Maker Games of Rank 4 Are PSPACE-Complete Galliot, Florian Sénizergues, Jonas Game theory Positional games Combinatorial games Complexity Hypergraphs The Maker-Maker convention of positional games is played on a hypergraph whose edges are interpreted as winning sets. Two players take turns picking a previously unpicked vertex, aiming at being first to pick all the vertices of some edge. Optimal play can only lead to a first player win or a draw, and deciding between the two is known to be PSPACE-complete even for 6-uniform hypergraphs. We establish PSPACE-completeness for hypergraphs of rank 4. As an intermediary, we use the recently introduced achievement positional games, a more general convention in which each player has their own winning sets (blue and red). We show that deciding whether the blue player has a winning strategy as the first player is PSPACE-complete even with blue edges of size 2 or 3 and pairwise disjoint red edges of size 2. The result for hypergraphs of rank 4 in the Maker-Maker convention follows as a simple corollary. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Galliot and Jonas Sénizergues 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.40 urn:nbn:de:0030-drops-255298 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.40 eng https://creativecommons.org/licenses/by/4.0/legalcode