Pith. sign in

REVIEW 6 minor 17 references

Maker-Maker games of rank 4 are PSPACE-complete

T0 review · 0 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Maker-Maker games remain PSPACE-complete when all winning sets have at most 4 vertices.

desk verdict Settles the rank-4 threshold for Maker–Maker games with a genuinely new reduction; the proof is intricate but holds up on careful reading. read the letter →

arxiv 2504.14256 v1 pith:ZRH26FQB submitted 2025-04-19 cs.DM cs.CCmath.CO

Florian Galliot , Jonas Sénizergues This is my paper · ORCID
classification cs.DMcs.CCmath.CO MSC 91A4668Q1705C65
keywords Maker-MakergamespositionalachievementPSPACE-completenesshypergraphrank3-QBFcombinatorialcomplexitytheory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that deciding whether the first player has a winning strategy in a Maker-Maker positional game is PSPACE-complete even when the hypergraph has rank 4, meaning every winning set contains at most four vertices; PSPACE-completeness is the standard hardness benchmark for finite games, covering everything solvable with polynomial memory. The previous bound was rank 6, obtained by reducing from Maker-Breaker games, a route that cannot reach rank 4 because rank-3 Maker-Breaker games are polynomial-time solvable. The paper instead passes through achievement positional games, a two-colour convention in which Left and Right chase their own blue and red winning sets, and shows that deciding Left's win is PSPACE-complete when blue edges have size 2 or 3 and red edges are pairwise disjoint of size 2. A two-vertex gadget embeds those achievement games into ordinary rank-4 Maker-Maker games by forcing the first round of play, and the reduction from 3-QBF is carried by a 'regular play' analysis that proves both players' natural moves are optimal. If correct, the result leaves rank 3 as the only open complexity case for Maker-Maker games.

What carries the argument

Two constructions carry the argument. The first is the notion of an achievement positional game $G = (V, E_L, E_R)$, in which Left wins by being first to fill a blue edge and Right by being first to fill a red edge; positions taken in the middle of a Maker-Maker game have exactly this form, which is what lets hardness of achievement games transfer back to Maker-Maker starting positions. The second is the clause gadget, a 'blue butterfly': four blue triples sharing a centre vertex $b_j$ and arranged as two pairs that share a middle vertex, so that once Left holds $b_j$ and the opponent cannot block both wings, Left wins by taking the shared vertex and one of the remaining leaves. Optimality of regular play is controlled by the Pairing Strategy lemma (a complete pairing of all opponent edges yields a non-losing strategy) and the Greedy Move lemma (given a blue edge $\{u, v\}$ such that every edge containing $u$ also contains $v$, the first player optimally picks $v$ and forces the reply $u$), together with trap-edges: blue triples that create an immediate forced winning sequence if Right leaves her appointed path. The reduction to rank 4 is the two-vertex gadget $u, v$ described above, whose effect is that the first round of the Maker-Maker game is optimal rather than arbitrary.

What would settle it

Brute-force the small cases. Take 3-QBF formulas with $n = 2$ and $n = 3$ variables and a handful of clauses, build the achievement game of Section 3.2 and the rank-4 Maker-Maker hypergraph of Corollary 2.4 exactly as specified, and compute the true game values by exhaustive search over all move orders, which is feasible since the vertex sets have only a few dozen elements. Compare with the predicted equivalence: Left wins the achievement game and the first player wins the Maker-Maker game exactly when Falsifier wins the quantified formula. A single mismatch in either direction refutes the reduction; the sharpest probes are the deviation cases of Claim 4, where Left picks a vertex other than $x_i^T$ or $x_i^F$ at a decision round and Right must hold a draw by pairing strategy.

Watch

Extended reading notes

Core claim

The paper's central result is Corollary 2.4: deciding the winner of a Maker-Maker game on a hypergraph of rank 4 is PSPACE-complete. It follows from Theorem 2.3, which states that in an achievement positional game $G = (V, E_L, E_R)$ with blue edges of size 2 or 3 and pairwise disjoint red edges of size 2, deciding whether Left wins as the first player is PSPACE-complete. The hardness proof reduces 3-QBF to these games: each quantified variable $x_i$ or $y_i$ becomes a variable gadget whose key vertices $x_i^T, x_i^F, y_i^T, y_i^F$ are picked in alternation to build a truth assignment, each clause becomes a blue 'butterfly' of four triples that Left can win on if the assignment falsifies the clause, and red destruction edges let Right dismantle the butterflies of satisfied clauses. Trap-edges punish any deviation from the prescribed 'regular play,' and Claims 3 and 4 argue that regular play is optimal for both players using the Pairing Strategy and Greedy Move lemmas, so that Left wins the game exactly when Falsifier wins the quantified formula. The step from achievement games to rank-4 Maker-Maker games adds two fresh vertices $u$ and $v$: every blue edge gains $u$, every red edge gains $v$, and $\{u, v\}$ is itself a winning set, forcing the first player to pick $u$ and the second to pick $v$, after which the position is exactly the original achievement game.

Load-bearing premise

The entire reduction depends on the claim that the prescribed 'regular play' during the first phase is optimal for both players, in the sense that every deviation hands the opponent a win or a draw; the paper's proof of that claim is a long case analysis resting on the pairing and greedy-move lemmas, and it has not been machine-checked.

Editorial extensions

If this is right

  • Rank-4 Maker-Maker games are PSPACE-complete, leaving rank 3 as the only open case; rank-2 games are solvable in polynomial time.
  • Deciding Left's win is PSPACE-complete for achievement games with blue edges of size at most 3 and pairwise disjoint red edges of size 2, and likewise with blue edges of size at most 4, upgrading the previously known NP-hardness of the (3,2) and (4,2) cases.
  • Because rank-3 Maker-Breaker games are tractable, no reduction from Maker-Breaker games can produce rank-4 Maker-Maker hardness; the two-colour achievement framework is what makes the new result possible.
  • The construction makes the first round of Maker-Maker play optimal, which is the property the earlier one-round (3,3) argument lacked; without it, mid-game hardness would not transfer to starting positions.
  • The remaining open cells with blue edges of size at most 4, namely (4,0) and (4,1), are exactly Maker-Breaker games of rank 4, which the authors expect the achievement-game approach cannot settle because Breaker creates no direct threats.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the regular-play analysis holds up, the complexity boundary for Maker-Maker games is at rank 4, and the natural next target is rank 3; because size-3 edges become 'strictly coloured' only after a player has moved inside them, a rank-3 hardness proof would likely need a different engine than the one here.
  • The trap-edge gadget, blue triples that turn any deviation into a forced losing sequence, is a reusable 'threat enforcer' for future reductions in positional games, independent of the 3-QBF application that motivates it here.
  • The same one-round embedding trick may transfer PSPACE-hardness to other two-colour conventions (games with a specified starting player, games with no draws) whenever the first move of the constructed position can be made optimal, which the paper's two-vertex gadget achieves for Maker-Maker games.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. This paper proves that deciding whether the first player has a winning strategy in a Maker-Maker positional game on a hypergraph of rank 4 is PSPACE-complete (Corollary 2.4). The proof goes through the more general framework of achievement positional games: Theorem 2.3 shows PSPACE-completeness for deciding whether the first player (Left) wins in an achievement game with blue edges of size 2 or 3 and pairwise disjoint red edges of size 2. The reduction is from 3-QBF (in the Falsifier-first formulation). The constructed game contains variable gadgets and clause gadgets; the central technical part is a detailed optimality analysis (Claims 1-4) showing that both players may be assumed to follow a prescribed 'regular play' that simulates the quantifier game, after which a second phase decides whether the final valuation satisfies the formula. Corollary 2.4 then embeds this achievement game into a rank-4 Maker-Maker game by adding two new vertices u and v and the edge {u,v}, which forces the first player to take u and the second player to take v, thereby preserving the winner.

Significance. If correct, this is a substantial step: it lowers the rank for which Maker-Maker PSPACE-completeness is known from 6 to 4, leaving only rank 3 open. The paper also strengthens the complexity of the (p,q)=(3,2) and (4,2) cases in the achievement-game table from NP-hardness to PSPACE-completeness. The proof is carefully structured into claims, the reduction is polynomial-time with explicit bounds on the size of the constructed game, and the case analysis is checkable by hand. I found no gap in the optimality analysis, although it is intricate and not machine-checked; the two supporting lemmas from [GS25] (Pairing Strategy and Greedy Move) are applied correctly. The main result is a genuine advance in the complexity of positional games.

minor comments (6)
  1. [Section 2.3, proof of Corollary 2.4] The symbol E_R is used both for the red edges of the original game G and for the red edges of the constructed game G′; in the bullets the intended meaning is the original red edge set, and making this explicit would remove ambiguity.
  2. [Section 3.3, Claim 2] The phrase 'By symmetry, assume u ∉ {b4_j,b5_j,b6_j}' is terse; the two wings of the butterfly are symmetric, and stating the swap explicitly would help the reader verify the argument.
  3. [Section 3.2] The token '/llbracket1, m/rrbracket' appears to be a rendering artifact and should read ⟦1,m⟧.
  4. [Section 3.4, Claim 3] When applying Lemma 2.2 to the greedy move b_r^j, the paper checks that d_r^j is in no blue edge; it should also note explicitly that the pairwise disjointness of red edges ensures the only red edge containing b_r^j is {b_r^j,d_r^j}.
  5. [Section 4] There is a typo: 'wee see' should be 'we see'.
  6. [Section 2.3] Membership in PSPACE is cited from [GS25] without further explanation; a one-sentence justification based on alternating polynomial time would make the paper more self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the PSPACE-hardness reduction from 3-QBF is direct, and the cited lemmas from [GS25] are supporting tools rather than the target result.

full rationale

The paper's central claim is established by a direct polynomial-time reduction from 3-QBF to the achievement game of Theorem 2.3. The equivalence is argued constructively: Claim 2 shows that, under the explicitly defined regular play, Left wins exactly when Falsifier has a winning strategy; Claims 3 and 4 then prove that deviating from regular play cannot improve either player's outcome, with an explicit case analysis over variable-gadget, clause-gadget, and future x-key deviations. Corollary 2.4 is a separate, self-contained embedding of an achievement game into a rank-4 Maker-Maker game using two fresh vertices and the edge {u,v}; its proof does not presuppose the theorem it derives except as the hardness source. The citations to the authors' prior work [GS25] supply the general Pairing Strategy and Greedy Move lemmas, which are stated in full and whose assumptions do not include PSPACE-completeness or the target result; they are used as standard game-theoretic tools inside the case analysis. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors to forbid alternatives, and no construction is defined in terms of the conclusion it is meant to establish. The proof is therefore self-contained in the relevant sense, and the presence of same-author citations does not make the derivation circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters: the reduction is parameter-free. The axioms are external PSPACE-completeness results and two supporting lemmas from the authors' prior work, which are not the target result and are independently stated and proven there. No new entities are postulated.

assumptions (4)
  • standard math 3-QBF is PSPACE-complete (Stockmeyer and Meyer [SM73])
    Used as the source problem for the reduction; assumed without proof.
  • standard math PSPACE = coPSPACE (Immerman [Imm88])
    Used to argue the complement of 3-QBF is also PSPACE-complete; the reduction targets the Falsifier-winning problem.
  • domain assumption Pairing Strategy lemma (Lemma 2.1 from [GS25])
    Taken from the authors' prior paper on achievement games; used to establish that Left can always avoid losing when red edges form a matching.
  • domain assumption Greedy Move lemma (Lemma 2.2 from [GS25])
    Taken from the authors' prior paper; used to justify forced and optimal moves in the gadget.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Maker-Maker games of rank 4 are PSPACE-complete." pith.science (2026). https://pith.science/paper/ZRH26FQB

@misc{pith2026250414256,
  author       = {Pith},
  title        = {Pith review of: Maker-Maker games of rank 4 are PSPACE-complete},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZRH26FQB}},
  note         = {Machine review of arXiv:2504.14256}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2504.14256 by the authors.

Figure 1
Figure 1. A blue butterfly plus a red edge. 2.2 Elementary strategic principles We recall two basic results from [GS25] which will be useful. A complete pairing of a hypergraph H = (V, E) is a set Π of pairwise disjoint pairs of vertices such that, for all e ∈ E, there exists π ∈ Π satisfying π ⊆ e. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The clause gadget associated with the clause cj = x2 ∨ ¬y4 ∨ y7. • Finally, there are trap-edges that go across the different gadgets. For each i ∈ J1, nK, we define Ti as the set of all {ti , τi , u} such that u belongs to some red edge e which is either: a guide-edge in GR k where k ∈ Ji+ 1, nK, a destruction-edge of the form {bj , dj} where j ∈ J1, mK, or a destruction￾edge of the form {b r j , dr j } where j ∈ J… view at source ↗
Figure 3
Figure 3. The updated variable gadget associated with xi and yi at the start of round i of regular play. For clarity, we use a shaded blue edge {u, u′} to represent {u, u′} (i) (so that the left part and the right part are actually connected to each other). (1) Left chooses the value T or F for xi , by picking x T i or x F i respectively. Both options trigger a sequence of forced moves inside the associated variable gadget: 8… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: The updated variable gadget associated with xi and yi after step (1) of round i of regular play (in the case where Left has put xi to T). (2) Right now has no forced move, and uses this window to play greedy moves inside the clause gadgets, with the aim of destroying s…
Figure 5
Figure 5. Figure 5: The clause gadget associated with the clause cj = x2 ∨ ¬y4 ∨y7, before (left) and (after) Right’s greedy move during round 3 of regular play if she had picked x F 2 in the previous round. (3) Right chooses the value T or F for yi , by picking y T i or y F i respectivel…
Figure 6
Figure 6. Figure 6: The clause gadget associated with the clause cj = x2 ∨ ¬y4 ∨y7, before (left) and (after) Left’s greedy move during round 2 of regular play if he had picked x F 2 at the start of the round. Let us state some simple properties of regular play. We say a blue (resp. red) …
Figure 7
Figure 7. Figure 7: The updated variable gadget associated with xk0 and yk0 in the case u = x T k0 after Right has taken care of all the other variable gadgets. – Finally, Right kills all remaining blue guide-edges in GL k0 and trap-edges in Tk0 . She plays the following moves, which kill…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 5 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution isbn issn journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sente...

    work page

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

    work page

  3. [3]

    J. Beck. Combinatorial Games: Tic-Tac-Toe Theory. Academic Press, Cambridge, 2008. ISBN 978-0-521-46100-9

    work page 2008

  4. [4]

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

    doi:10.7146/brics.v11i14.21839 2004

  5. [5]

    Chv\'atal, P

    V. Chv\'atal, P. Erd o s. Biased positional games. Ann. Disc. Math., 2, 1978, pp. 221--229. ://dx.doi.org/10.1016/S0167-5060(08)70335-2

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

  6. [6]

    Erdös, J

    P. Erdös, J. Selfridge. On a combinatorial game . Journal of Combinatorial Theory, Series A, 14, 1973. ://dx.doi.org/10.1016/0097-3165(73)90005-8

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

  7. [7]

    M. Gardner. Hexaflexagons and Other Mathematical Diversions, chap. The Game of Hex. University Of Chicago Press, 2nd ed. ISBN 978-0226282541, 1959. pp. 38--40

    work page 1959

  8. [8]

    Galliot, S

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

    arXiv 2022

Show all 17 references
  1. [9]

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

    1980 doi

  2. [10]

    Galliot, J

    F. Galliot, J. S\'enizergues. A unified convention for achievement positional games. Preprint , 2025. ://arxiv.org/abs/2503.18163

    2025

  3. [11]

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

    1963 doi

  4. [12]

    Immerman

    N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17(5), 1988, pp. 935--938. ://dx.doi.org/10.1137/0217058

    1988 doi

  5. [13]

    F. O. Koepke. Solving Maker-Breaker games on 5-uniform hypergraphs is PSPACE-complete . Preprint, 2025. ://arxiv.org/abs/2502.20271

    2025 arXiv

  6. [14]

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

    2020 doi

  7. [15]

    M. L. Rahman, T. Watson. 6-uniform Maker-Breaker game is PSPACE-complete . In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), vol. 187 of LIPIcs. Schloss Dagstuhl, Leibniz-Zentrum f \"u r Informatik, Dagstuhl, Germany, 2021. pp. 57:1--57:1...

    2021 doi

  8. [16]

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

    1978 doi

  9. [17]

    L. J. Stockmeyer, A. R. Meyer. Word problems requiring exponential time (preliminary report). In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC '73. Association for Computing Machinery, New York, NY, USA, 1973. pp. 1--–9. ://dx.doi.org/10.1145/800125.804029

    1973

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.