{"id":"4a0f7d8f-5917-4c46-858b-276878eed78b","arxiv_id":"2504.14256","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Maker-Maker games on hypergraphs of rank 4 are PSPACE-complete, via a reduction from 3-QBF through achievement games with disjoint red edges.","lead":"This paper proves that deciding the winner in a Maker-Maker positional game on hypergraphs of rank 4 is PSPACE-complete, improving the known threshold from rank 6. The proof works through the more general achievement games framework, where each player has their own winning sets, and settles the complexity of rank 4 games.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the regular-play optimality proof is intricate but internally consistent, and the reduction checks out.","rationale":"The reader's weakest-assumption analysis correctly identifies the optimality of regular play as the most delicate part of the proof. I examined that part in detail, including the forced-move structure of round i and the three deviation cases in Claim 4. The pairing-strategy invocation is correct: since the red edges are pairwise disjoint, they form a complete pairing of the red hypergraph, so Left can always avoid losing, and the proof only needs to show that non-regular Left moves hand Right a drawing strategy. I verified the exhaustiveness of the cases and the legality of the described responses. The Corollary 2.4 embedding also holds: starting with u, w, or v is handled correctly, and the updated blue/red edge sets are as claimed. No concrete logical error, unhandled deviation, or invalid lemma application surfaced. The remaining concern is epistemic rather than mathematical: the case analysis is long and not machine-checked, so a small slipped subcase would be hard to notice by reading. This is exactly why a brute-force verification on small instances is worthwhile, but it is not a demonstrated flaw in the argument. Therefore I do not find a load-bearing objection and recommend keeping the reader's ACCEPT verdict unchanged.","tokens_in":18260,"tokens_out":33160,"duration_ms":295292,"concrete_test":"Implement the reduction and run an exact exhaustive game-tree solver for all 3-QBF instances with n≤3 and m≤4 (or, if that is too large, with m≤2 and n≤4), comparing the computed outcome on G with the Falsifier/Satisficer outcome on φ; additionally enumerate every non-regular first move at each round for those instances and check that the response prescribed in Claim 4 is legal and holds Left to at most a draw. Any mismatch would localize a failing case in Claims 3–4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim depends on the optimality of regular play in Claims 3 and 4, and the reader is right to flag this as the least secure part of the argument. I traced the case divisions rather than finding a concrete failure. The forced moves in round i are genuine one-move threats: after Left picks xT_i, Right must take xF_i; Left must take w'_i against the red edge {xF_i,w'_i}; Right must take s_i against the updated one-vertex blue edge {s_i} from {w'_i,s_i,xT_i}; Left must then take t_i against {s_i,t_i}. Claim 4's pairing argument is also correctly applied: because the red edges are pairwise disjoint, E'_R is its own complete pairing, so after any Left move Left retains a non-losing pairing strategy, and the task reduces to showing each non-regular move lets Right draw. The three deviation cases (variable-gadget vertex, clause-gadget vertex, future x-key vertex) are exhaustive, and the subcase u=b_j0 correctly uses the standing assumption that no clause is already fully owned by Left. The apparent risk is only that the analysis is hand-written and not machine-checked; I did not find an unhandled deviation or an internal inconsistency.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18492,"tokens_out":31703,"duration_ms":260825,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 2.3, proof of Corollary 2.4"},{"comment":"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.","section":"Section 3.3, Claim 2"},{"comment":"The token '/llbracket1, m/rrbracket' appears to be a rendering artifact and should read ⟦1,m⟧.","section":"Section 3.2"},{"comment":"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}.","section":"Section 3.4, Claim 3"},{"comment":"There is a typo: 'wee see' should be 'we see'.","section":"Section 4"},{"comment":"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.","section":"Section 2.3"}],"recommendation":"accept","confidential_remarks":"The paper relies on two lemmas from the authors' own prior work [GS25]; this is not circular because the lemmas are elementary tools and the target result differs. The editor may wish to confirm that this dependence is acceptable. The paper fits the scope of the journal. No other concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper settles a real open problem: Maker–Maker games on hypergraphs of rank 4 are PSPACE-complete, improving the previous rank-6 threshold. The key step is a new hardness proof for achievement positional games with blue edges of size 2 or 3 and pairwise disjoint red edges of size 2, and the reduction from 3-QBF is not a routine adaptation of earlier Maker–Breaker constructions. The embedding from that achievement game into a rank-4 Maker–Maker game in Corollary 2.4 is clean, and I verified the pairing arguments there: they work, including the case where Left starts at a vertex other than the two added ones.\n\nThe main body is the reduction, and it is well structured. The gadget design is clever: trap edges force Right to stay honest during Phase 1, and the two-phase regular play maps Falsifier/Satisfier strategies to Left/Right strategies in a direct way. The proof is split into claims, and the hard part is Claim 4, the optimality of Left's regular play. That is the load-bearing wall, and it is hand-written case analysis. I traced the case divisions together with the stress-test note and did not find an unhandled deviation: the forced moves are genuine one-move threats, and the three deviation cases for Left's non-regular move are exhaustive. The dependence on the two lemmas from the authors' companion paper [GS25] is fine; those are simple, standard tools (Pairing Strategy and Greedy Move), not the target result.\n\nSoft spots, in proportion: the optimality proof is intricate enough that a referee should spend real time on it, and a machine-checked version would increase confidence, but I did not find a gap. The construction has O(n^2 + nm) blue edges because of the trap-edge definition, but that is still a polynomial reduction. The discussion of open cases (rank 3 in Maker–Maker, 4-uniform hypergraphs) is honest and correctly identifies why the present method does not immediately extend.\n\nThis paper is for the positional-games complexity community. It resolves a specific open question with a technique that may be reusable for the remaining rank-3 and uniformity questions. I would bring it to a reading group and would cite it if I worked in this area.\n\nRecommendation: this deserves a serious referee. If the case analysis in Claims 3 and 4 survives scrutiny, which my own check suggests it will, the paper should be accepted.","headline":"Settles the rank-4 threshold for Maker–Maker games with a genuinely new reduction; the proof is intricate but holds up on careful reading.","tokens_in":19018,"tokens_out":12637,"would_cite":true,"duration_ms":108080,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A46","68Q17","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"Maker-Maker games remain PSPACE-complete when all winning sets have at most 4 vertices.","keywords":["Maker-Maker games","positional games","achievement positional games","PSPACE-completeness","hypergraph rank","3-QBF","combinatorial games","complexity theory"],"falsifier":"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.","tokens_in":18074,"feed_emoji":"♟️","tokens_out":19678,"duration_ms":154494,"temperature":0.7,"pith_summary":"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.","feed_headline":"Deciding Maker-Maker winners stays PSPACE-complete at rank 4","feed_subtitle":"A two-colour 'achievement' reduction from 3-QBF closes the gap between easy rank 2 and known-hard rank 6.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the source problem 3-QBF, shown PSPACE-complete there, from which the paper's reduction starts.","marker":"[SM73]"},{"why":"Justifies reducing from the complement of 3-QBF by proving PSPACE is closed under complementation.","marker":"[Imm88]"},{"why":"Introduced achievement positional games and supplies the Pairing Strategy and Greedy Move lemmas that the optimality arguments of Claims 3 and 4 invoke.","marker":"[GS25]"},{"why":"The earlier reduction from Maker-Breaker rank k to Maker-Maker rank k+1, which gave the previous rank-6 bound and which cannot reach rank 4.","marker":"[Bys04]"},{"why":"Proves 6-uniform Maker-Breaker games PSPACE-complete, the instance that produced the previous best Maker-Maker hardness when combined with the Byskov reduction.","marker":"[RW21]"},{"why":"Shows rank-3 Maker-Breaker games are polynomial-time solvable, the reason the Maker-Breaker route to rank-4 hardness is blocked.","marker":"[GGS22]"}],"fun_headline_variants":["Rank 4 Maker-Maker games are PSPACE-complete","Maker-Maker hardness tightens to rank 4","PSPACE-complete at last: Maker-Maker rank 4","Rank 4 proves Maker-Maker decisively hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Rank 4 Maker-Maker games are PSPACE-complete","Maker-Maker hardness tightens to rank 4","PSPACE-complete at last: Maker-Maker rank 4","Rank 4 proves Maker-Maker decisively hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000198,"raw_usage":{"total_tokens":1421,"prompt_tokens":1054,"completion_tokens":367,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":670,"completion_tokens_details":{"reasoning_tokens":298}},"tokens_in":670,"tokens_out":367,"duration_ms":3663,"temperature":1.0,"reasoning_tokens":298,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:52:24.572537+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}