Maker-Maker games of rank 4 are PSPACE-complete
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912337232920576 |
|---|---|
| author | Galliot, Florian Sénizergues, Jonas |
| author_facet | Galliot, Florian Sénizergues, Jonas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14256 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maker-Maker games of rank 4 are PSPACE-complete Galliot, Florian Sénizergues, Jonas Discrete Mathematics Computational Complexity Combinatorics 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. |
| title | Maker-Maker games of rank 4 are PSPACE-complete |
| topic | Discrete Mathematics Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2504.14256 |