pith. sign in

arxiv: 2509.13819 · v3 · submitted 2025-09-17 · 💻 cs.DM · cs.CC· math.CO

4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete

Florian Galliot This is my paper

Pith reviewed 2026-05-18 16:49 UTC · model grok-4.3

classification 💻 cs.DM cs.CCmath.CO
keywords Maker-Breaker gamesMaker-Maker gamesPSPACE-completenesshypergraph gamespositional gamesuniform hypergraphsbounded degreeC4-game
0
0 comments X

The pith

Deciding whether the first player wins in Maker-Breaker or Maker-Maker games on 4-uniform hypergraphs is PSPACE-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that determining the existence of a winning strategy for the first player is PSPACE-complete in both the Maker-Maker game, where either player wins by fully occupying an edge, and the Maker-Breaker game, where one player seeks to occupy an edge while the other blocks it. This holds even when the underlying hypergraph is restricted to 4-uniform edges and bounded maximum degree. The result tightens earlier complexity thresholds: it matches the known polynomial-time solvability at uniformity 3 for Maker-Breaker while improving the Maker-Maker threshold from general rank-4 hypergraphs. A direct corollary shows the same PSPACE-completeness for the vertex-C4-game on ordinary graphs, where winning sets are the vertex sets of 4-cycles.

Core claim

We prove that deciding whether the first player has a winning strategy remains PSPACE-complete for both the Maker-Breaker and Maker-Maker conventions even when the hypergraph is 4-uniform and has bounded maximum degree. The proof proceeds by reduction from a known PSPACE-complete problem while preserving both 4-uniformity and the degree bound. As a corollary, the same hardness holds for the vertex-C4-game played on arbitrary graphs.

What carries the argument

A degree-bounded, 4-uniformity-preserving reduction from a known PSPACE-complete problem to the first-player win decision problem for these games.

If this is right

  • The complexity gap for Maker-Breaker games closes between polynomial time at rank 3 and PSPACE-completeness at rank 4.
  • Maker-Maker games inherit the same tight bound at uniformity exactly 4.
  • The vertex-C4-game on graphs is PSPACE-complete in both conventions.
  • Any future algorithm for these games must handle at least 4-uniform instances of bounded degree.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar hardness may hold for other small fixed uniformities once the reduction technique is adapted.
  • The bounded-degree restriction suggests that hardness persists even when the game board has linear size relative to the number of winning sets.
  • The C4 corollary implies that cycle-detection winning conditions alone suffice to produce PSPACE-complete game problems.

Load-bearing premise

The reduction from a known PSPACE-complete problem preserves both 4-uniformity and bounded maximum degree without creating higher-rank edges or unbounded degrees.

What would settle it

An explicit polynomial-time algorithm that correctly decides first-player win in 4-uniform bounded-degree Maker-Breaker games on a family of hypergraphs large enough to include the images of the reduction.

Figures

Figures reproduced from arXiv: 2509.13819 by Florian Galliot.

Figure 1
Figure 1. Figure 1: Updating the Maker-Breaker game on a hypergraph [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Updating the Maker-Maker game on the same hypergra [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Left: an example Geography instance. Right: a sche [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of a scenario where Maker wins, pictu [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Schematic representation of the pairing obtained [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The gadget Hv for v ∈ B1,2, as updated after the first five moves of the sequence of regular play on Hv. We can see that Breaker must pick one of y3, y4 or pb, otherwise Maker can win in two moves by picking y3 and then y4 or pb. Similarly, Breaker must pick one of y3, y4 or pc, otherwise Maker can win in two moves. These two facts combined ensure that Breaker must pick either y3 or y4, and both moves are … view at source ↗
Figure 7
Figure 7. Figure 7: The gadget Hv for v ∈ M1,2, as updated after the first four moves of the sequence of regular play on Hv. (a) First, suppose that x ∈ {y3, zb, zc}. That move does not impact any other gadget since x is an interior vertex. Now, Breaker picks z1. Note that {{z2, pc}} is a pairing for (the updated gadget of) v after that move. Denoting by w the out-neighbor of v through the arc c, we should not use pc in the p… view at source ↗
Figure 8
Figure 8. Figure 8: The gadget Hv for v ∈ B1,2, as updated after the first four moves of the sequence of regular play on Hv. (a) First, suppose that x ∈ {y3, y4}. By symmetry, assume that x = y3. Now, Breaker picks y4 (which is forced anyway). Note that {{pb, x3}, {pc, qc}} is a pairing for v after that move. Denoting by w the out-neighbor of v through the arc b, we should not use pb in our pairing for w, so we define: Π = {{… view at source ↗
Figure 9
Figure 9. Figure 9: The gadget Hv for B ∈ M1,2, as updated after the first eight moves of the sequence of regular play on Hv. (a) First, suppose that x = y5. Now, Breaker picks qb (which is forced anyway). Note that {{pc, qc}} is a clean pairing for v after that move. Moreover, denoting by w the out￾neighbor of v through the arc b, we can see that Π′ (w) \ {{pb, qb}} is a clean pairing for w at that point. Indeed, Maker has p… view at source ↗
read the original abstract

We study two positional games played on hypergraphs, whose edges may be interpreted as winning sets. Two players take turns picking a previously unpicked vertex of the hypergraph. We say a player fills an edge if that player has picked all the vertices of that edge. In the Maker-Maker convention, whoever first fills an edge wins, or we get a draw if no edge is filled. In the Maker-Breaker convention, the first player aims at filling an edge while the second player aims at preventing the first player from filling an edge. Our main result is that, for both games, deciding whether the first player has a winning strategy is a PSPACE-complete problem even when restricted to 4-uniform hypergraphs (of bounded maximum degree). For the Maker-Maker convention, this improves on the known PSPACE-completeness result for hypergraphs of rank 4. For the Maker-Breaker convention, this improves on the known PSPACE-completeness result for 5-uniform hypergraphs, and closes the complexity gap since the problem for hypergraphs of rank 3 is known to be solvable in polynomial time. As a corollary of our construction, we actually get a stronger result: deciding whether the first player has a winning strategy for the vertex-$C_4$-game played on arbitrary graphs, where the winning sets are the vertex sets of 4-cycles, is a PSPACE-complete problem for both conventions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper proves that deciding whether the first player has a winning strategy in Maker-Breaker and Maker-Maker games is PSPACE-complete even when restricted to 4-uniform hypergraphs with bounded maximum degree. It improves prior results (rank-4 for Maker-Maker; 5-uniform for Maker-Breaker) and derives a corollary establishing PSPACE-completeness for the vertex-C4 game on arbitrary graphs under both conventions.

Significance. If the central reduction holds, the result is significant: it closes the complexity gap for Maker-Breaker between polynomial-time solvability on rank-3 hypergraphs and PSPACE-completeness on 5-uniform instances, while strengthening the Maker-Maker hardness to uniform bounded-degree instances. The bounded-degree condition makes the hardness more robust. The explicit gadget-based reduction from a standard PSPACE-complete problem (with verification that 4-uniformity and degree bounds are preserved) is the key technical contribution and supports the corollary for C4 games.

major comments (2)
  1. [§4] §4 (Maker-Breaker reduction): the claim that the final hypergraph is 4-uniform with maximum degree bounded by a constant independent of the source instance size is load-bearing. The gadget composition (variable, clause, and auxiliary structures) must be shown not to introduce any edge of cardinality other than 4 or any vertex whose degree grows with the reduction parameter; an explicit degree tally or invariant would confirm this.
  2. [§5] §5 (Maker-Maker reduction and corollary): the transfer from the hypergraph game to the vertex-C4 game on graphs requires that every winning set in the C4 instance corresponds exactly to a 4-edge in the original hypergraph without creating extraneous 4-cycles that alter the winner. The manuscript should verify that the graph construction introduces no spurious C4s whose vertex sets are not images of original edges.
minor comments (3)
  1. [Abstract] The abstract refers to 'hypergraphs of rank 4' for prior Maker-Maker results; clarify that rank denotes maximum edge size while the new result enforces exact 4-uniformity.
  2. [Figure 2] Figure 2 (gadget diagram): add vertex labels that match the textual description of the reduction to improve readability.
  3. [Introduction] Add an explicit citation to the known PSPACE-completeness result for 5-uniform Maker-Breaker games in the introduction when stating the improvement.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, the positive assessment of the significance, and the recommendation for minor revision. The two major comments concern the need for more explicit verification of uniformity/degree bounds in the Maker-Breaker reduction and the absence of spurious C4s in the graph construction for the corollary. We address each point below and will strengthen the manuscript accordingly.

read point-by-point responses

  1. Referee: [§4] §4 (Maker-Breaker reduction): the claim that the final hypergraph is 4-uniform with maximum degree bounded by a constant independent of the source instance size is load-bearing. The gadget composition (variable, clause, and auxiliary structures) must be shown not to introduce any edge of cardinality other than 4 or any vertex whose degree grows with the reduction parameter; an explicit degree tally or invariant would confirm this.

    Authors: We agree that an explicit invariant and degree tally would improve clarity and address the load-bearing nature of the claim. The reduction in Section 4 is built from constant-size gadgets (variable gadget on a fixed number of vertices, clause gadget, and auxiliary 4-edges for connections) where every hyperedge is explicitly defined as a 4-set; no gadget introduces edges of other cardinalities by construction. For the degree bound, each vertex type (e.g., those representing literals or clause auxiliaries) receives a fixed number of incident edges from its local gadget plus at most a constant number from inter-gadget connections, because the reduction employs a bounded-occurrence source problem or local connectors that do not scale with instance size. To make this fully transparent we will add, in the revised Section 4, a short subsection stating the invariant (all edges remain cardinality 4) together with an explicit per-vertex-type degree calculation showing the maximum is at most 7, independent of the number of variables or clauses. This revision will be incorporated. revision: yes

  2. Referee: [§5] §5 (Maker-Maker reduction and corollary): the transfer from the hypergraph game to the vertex-C4 game on graphs requires that every winning set in the C4 instance corresponds exactly to a 4-edge in the original hypergraph without creating extraneous 4-cycles that alter the winner. The manuscript should verify that the graph construction introduces no spurious C4s whose vertex sets are not images of original edges.

    Authors: We thank the referee for highlighting the need to confirm exact correspondence for the corollary. The graph construction in Section 5 replaces each 4-edge of the hypergraph with a dedicated C4 on four fresh vertices, with inter-gadget connections realized by paths or trees of length greater than 2 that cannot participate in any additional 4-cycle. Consequently, any 4-cycle in the resulting graph must use exactly the four vertices of one original hyperedge; cross-gadget 4-cycles are impossible because any path leaving a gadget must traverse at least three edges before re-entering another gadget. We will add a short lemma (or paragraph) in the revised Section 5 that formally proves there are no spurious C4s by case analysis on possible cycle formations within and between gadgets. This will ensure the winning conditions transfer exactly and will be included in the next version. revision: yes

Circularity Check

0 steps flagged

No circularity: PSPACE-completeness via explicit reduction from known problems

full rationale

The paper proves PSPACE-completeness for 4-uniform Maker-Breaker and Maker-Maker games on bounded-degree hypergraphs by constructing an explicit reduction from established PSPACE-complete problems (such as geography or QBF variants). This reduction is claimed to preserve exact 4-uniformity and a fixed degree bound. The derivation chain consists of a standard many-one reduction whose correctness is independent of the target statement; no step defines the result in terms of itself, renames a fitted parameter as a prediction, or relies on a load-bearing self-citation whose justification loops back to the present work. The improvement over prior results for rank-4 or 5-uniform cases is presented as a technical strengthening of an external reduction technique, not as a self-referential normalization. The corollary for vertex-C4 games follows directly from the same construction. This is a self-contained proof against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim depends on a reduction whose explicit steps and base problem are not visible in the abstract; relies on standard complexity-theoretic background results whose details are omitted here.

axioms (1)
  • standard math PSPACE-completeness of positional games or related problems on higher-uniformity hypergraphs
    Serves as the source problem for the reduction to the 4-uniform bounded-degree case.

pith-pipeline@v0.9.0 · 5789 in / 1208 out tokens · 62281 ms · 2026-05-18T16:49:52.979228+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Ahlroth and P

    L. Ahlroth and P. Orponen. Unordered constraint satisfa ction games. In B. Rovan, V. Sassone, and P. Widmayer, editors, Math. Found. Comput. Sci. 2012 , pages 64–75, Berlin, Heidelberg,

    work page 2012

  2. [2]

    doi:10.1007/978-3-642-32589-2_9

    Springer Berlin Heidelberg. doi:10.1007/978-3-642-32589-2_9

    work page doi:10.1007/978-3-642-32589-2_9

  3. [3]

    J. Beck. Combinatorial Games: Tic-Tac-Toe Theory . Academic Press, Cambridge, 2008

    work page 2008

  4. [4]

    J. M. Byskov. Maker-Maker and Maker-Breaker games are PSPA CE-complete. BRICS Report Series, 11(14), 2004. doi:10.7146/brics.v11i14.21839

    work page doi:10.7146/brics.v11i14.21839 2004

  5. [5]

    Chvátal and P

    V. Chvátal and P. Erdős. Biased positional games. Ann. Disc. Math. , 2:221–229, 1978. doi:10.1016/S0167-5060(08)70335-2

    work page doi:10.1016/s0167-5060(08)70335-2 1978

  6. [6]

    Duchêne, A

    E. Duchêne, A. Dumas, M. Hilaire, and A. Parreau. Solving the P5-game on forests (in French). Unpublished. 2024. URL: https://jga2024.sciencesconf.org/579456/document

    work page 2024

  7. [7]

    Erdös and J

    P. Erdös and J. L. Selfridge. On a combinatorial game. J. Combin. Theory Ser. A , 14, 1973. doi:10.1016/0097-3165(73)90005-8

    work page doi:10.1016/0097-3165(73)90005-8 1973

  8. [8]

    Galliot, V

    F. Galliot, V. Gledel, and A. Parreau. The A voider-Enfor cer game on hypergraphs of rank 3. Preprint. 2025. URL: https://arxiv.org/abs/2503.21672

    work page arXiv 2025

  9. [9]

    Galliot, S

    F. Galliot, S. Gravier, and I. Sivignon. Maker-Breaker is solved in polynomial time on hyper- graphs of rank 3. Preprint. 2022. URL: https://arxiv.org/abs/2209.12819

    work page arXiv 2022

  10. [10]

    Galliot and J

    F. Galliot and J. Sénizergues. A unified convention for ac hievement positional games (extended abstract). EuroComb’25: 13th European Conference on Combi natorics, Graph Theory and Applications, 25–29 August 2025, Budapest, Hungary. Procee dings to appear. 2025

    work page 2025

  11. [11]

    Galliot and J

    F. Galliot and J. Sénizergues. Maker-Maker games of ran k 4 are PSPACE-complete. Preprint

    work page

  12. [12]

    URL: https://arxiv.org/abs/2504.14256

    work page arXiv

  13. [13]

    Galliot and J

    F. Galliot and J. Sénizergues. A unified convention for a chievement positional games (full version). 2025. URL: https://arxiv.org/abs/2503.18163

    work page arXiv 2025

  14. [14]

    The game of Hex

    M. Gardner. Hexaflexagons and other mathematical diversions , chapter “The game of Hex”, pages 38–40. University Of Chicago Press, 2 edition, 1959

    work page 1959

  15. [15]

    Recreational topology

    M. Gardner. The second scientific american book of mathematical puzzles and diversions , chap- ter “Recreational topology”, pages 84–87. University Of Ch icago Press, 2 edition, 1961

    work page 1961

  16. [16]

    Gledel and N

    V. Gledel and N. Oijid. A voidance games are PSPACE-comp lete. In 40th International Sym- posium on Theoretical Aspects of Computer Science (STACS 20 23), volume 254 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 34:1–34:19, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2023.34. 24

    work page doi:10.4230/lipics.stacs.2023.34 2023

  17. [17]

    R. K. Guy and J. L. Selfridge. Problem S10: solution by T. G. L. Zetters. The American Mathematical Monthly , 87:575–576, 1980. doi:10.2307/2321433

    work page doi:10.2307/2321433 1980

  18. [18]

    A. W. Hales and R. I. Jewett. Regularity and positional g ames. Trans. Amer. Math. Soc. , 106:222–229, 1963. doi:10.1007/978-0-8176-4842-8_23

    work page doi:10.1007/978-0-8176-4842-8_23 1963

  19. [19]

    F. Koepke. Solving Maker-Breaker games on 5-uniform hyp ergraphs is PSPACE-complete. Preprint. 2025. URL: https://arxiv.org/abs/2502.20271

    work page arXiv 2025

  20. [20]

    A. Lehman. A solution of the Shannon switching game. J. Soc. Indust. Appl. Math. , 12(4):687– 725, 1964. doi:10.1137/0112059

    work page doi:10.1137/0112059 1964

  21. [21]

    Lichtenstein and M

    D. Lichtenstein and M. Sipser. Go is polynomial-space h ard. J. ACM , 27(2):393–401, 1980. doi:10.1145/322186.322201

    work page doi:10.1145/322186.322201 1980

  22. [22]

    M. L. Rahman and T. Watson. Complexity of unordered CNF g ames. ACM Trans. Comput. Theory, 12(3), 2020. doi:10.1145/3397478

    work page doi:10.1145/3397478 2020

  23. [23]

    M. L. Rahman and T. Watson. Tractable unordered 3-CNF ga mes. In LATIN 2020: Theoretical Informatics, proc. Latin American Symposium on Theoretical Informatic s, volume 12118 of Lecture Notes in Comput. Sci. , pages 360–372, Cham, 2020. Springer International Publis hing. doi:10.1007/978-3-030-61792-9_29

    work page doi:10.1007/978-3-030-61792-9_29 2020

  24. [24]

    M. L. Rahman and T. Watson. 6-uniform Maker-Breaker game is PSPACE-complete. In 38th International Symposium on Theoretical Aspects of Compute r Science (STACS 2021) , volume 187 of LIPIcs, pages 57:1–57:15, Dagstuhl, Germany, 2021. Schloss Dagst uhl, Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2021.57

    work page doi:10.4230/lipics.stacs.2021.57 2021

  25. [25]

    T. J. Schaefer. On the complexity of some two-person per fect-information games. J. Comput. Syst. Sci. , 16(2):185–225, 1978. doi:10.1016/0022-0000(78)90045-4

    work page doi:10.1016/0022-0000(78)90045-4 1978

  26. [26]

    L. J. Stockmeyer and A. R. Meyer. Word problems requirin g exponential time (prelimi- nary report). In Proceedings of the Fifth Annual ACM Symposium on Theory of Co mputing, STOC ’73, pages 1––9, New York, NY, USA, 1973. Association fo r Computing Machinery. doi:10.1145/800125.804029. 25

    work page doi:10.1145/800125.804029 1973