CS Paper Radar

The Two-Level Poset Game is PSPACE-Complete

Kengo Hashimoto

cs.CC cs.DMcs.GTmath.CO ·submitted 2026-10-14 04:18 UTC · v1

Abstract

Poset games form a fundamental class of combinatorial games that includes classical games such as Nim and Chomp. Determining the outcome of a poset game is known to be PSPACE-complete even for posets of height at most three. However, the exact computational complexity of Two-Level Poset Game, played on posets of height at most two, has remained an open problem for over a decade. We resolve this problem by proving that Two-Level Poset Game is PSPACE-complete via a polynomial-time reduction from Avoid True on positive CNF formulas.

Closest papers

Nearest neighbours by meaning across the whole index.

Sowing the Seeds of Intractability: Kalah is PSPACE-complete

cs.CC cs.GTmath.CO ·2026-11-12 ·Ethan Dickey, Ethan Mader
similarity 0.65
Abstract · 55 pages, 6 figures, 5 tables

Kalah is a classic two-player game in the mancala family of sowing games. Computers have solved several standard-size starting positions, but the complexity of the game on boards of growing size has remained open. We study the natural generalization in which the number of pits per side is part of the input and an arbitrary position is given, with the stone counts given in unary. We show that deciding whether a designated player can force a win from such a position is PSPACE-complete. The hard positions have Alice to move first and both stores initially empty. The same positions are hard under either common convention for capture opposite an empty pit, and with or without the bonus rule, which gives a player another turn when the last stone is sown into their own store. We introduce Line Kalah as an intermediate problem, a game on a line in which stones that leave the line effectively disappear and Alice must save each of her target pits before Bob captures it, and we reduce quantified Boolean formulas to it. The reduction uses a set of sequential timer piles whose last stones approach a group of targets, forcing Alice to choose between two captures in order to set the truth value of a variable, and a final capture gadget to test a clause chosen by Bob (only one is needed adversarially). Since either player may move any pile at any time, the stages are placed so that premature timer firings protect earlier potential targets. For a true formula, Alice's strategy against arbitrary opposing play either gains enough time to save the remaining targets (after Bob deviates from the intended play) or reaches the final test with a correctly encoded, protected input. Finally, the line positions are embedded in Kalah with both stores empty. A separate Bob pit holds the score adjustment, so the winner takes a strict majority of the stones.

0.24

Antichains for Concurrent Parameterized Games

cs.LO ·2026-10-08 ·Nathalie Bertrand, Patricia Bouyer, Gaëtan Staquet
published similarity 0.63
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898. A full version of this paper, containing all proofs, appears at arXiv:2505.13460

Concurrent parameterized games involve a fixed yet arbitrary number of players. They are described by finite arenas in which the edges are labeled with languages that describe the possible move combinations leading from one vertex to another (n players yield a word of length n). Previous work showed that, when edge labels are regular languages, one can decide whether a distinguished player, called Eve, has a strategy to ensure a reachability objective, against any strategy profile of her arbitrarily many opponents. This decision problem is known to be PSPACE-complete. A basic ingredient in the PSPACE-membership proof is the reduction to the exponential-size knowledge game, a 2-player game that reflects the knowledge Eve has on the number of opponents. In this paper, we provide a symbolic approach, based on antichains, to compute Eve's winning region in the knowledge game. In words, it gives the minimal knowledge Eve needs at every vertex to win the concurrent parameterized reachability game. More precisely, we propose two fixed-point algorithms that compute, as an antichain, the maximal elements of the winning region for Eve in the knowledge game. We implemented these two algorithms in C++, as well as the one initially proposed, and report on their relative performances on various benchmarks.

0.46

Solving Streett and Emerson-Lei Games with Universal Trees

cs.GT cs.LO ·2026-08-17 ·Daniel Hausmann, Marcin Jurdzinski, Nir Piterman
similarity 0.62
Abstract

Nearly a decade ago, Calude et al. showed that parity games can be solved in quasi-polynomial time. This result is now understood in terms of universal trees. By reduction to parity games, the quasi-polymonial result can benefit all omega-regular games. However, beyond such reductions, and with the exception of Rabin games, our understanding of the role of universal trees in direct solutions is still quite limited. In this work, we refute the common view that universal trees are relevant only for games that admit memoryless winning strategies. We contribute a full understanding of how universal trees interact with Zielonka trees for the solution of Streett and Emerson-Lei games. As a consequence, we show that winning regions and strategies in Streett games with $n$ vertices, $m$ edges, and $k$ pairs can be computed in time $O(mk\log(k)k!|U(n,k)|)$, where $U(n,k)$ is a universal tree for $n$ leaves and depth $k$. This improves upon the best previously known complexity result for Streett games, which relied on reduction to parity games and their quasi-polynomial solution. Furthermore, we show that winning regions and strategies for Emerson-Lei games with $n$ vertices, $m$ edges, and $c$ colors can be computed in time $O(mc\log(c)c!|U(n,c/2)|)$, again improving over reductions to parity games. Notably, our approach yields memory-optimal strategies, in contrast to those obtained via reductions to parity games. Finally, we show how universal trees can be used to bound the recursion tree of the Zielonka-McNaughton algorithm for Emerson-Lei games. This leads to a symbolic algorithm that replaces the factor $n^c$ in the time complexity of existing symbolic approaches with $|U(n,c)|$.

0.18

Puzznic is PSPACE-Complete

cs.CC cs.CG ·2026-10-16 ·Jake Anderson, Lars Magnus Hvattum, András Z. Salamon
theory similarity 0.62
Abstract · 15 pages

We prove that deciding solvability of Puzznic, a falling-block puzzle game originally developed by Taito, is PSPACE-complete. To show hardness we construct a self-closing door gadget using Puzznic's game mechanics. For membership, we show that the configuration space is exponentially bounded and apply Savitch's theorem. We also improve an existing NP-completeness proof for a simpler version of the game known as Cubic, showing that this game is NP-complete even when restricted to only two kinds of blocks.

0.33

Planar PArcK is PSPACE-complete

cs.CC cs.DMmath.CO ·2026-11-15 ·Craig Tennenhouse, Kanae Yoshiwatari
similarity 0.60
Abstract · 9 pages

Partizan Arc Kayles, or PArcK, is a partizan combinatorial game on edge colored graphs, and is a generalization of the game Domineering. Previously, PArcK was shown to be PSPACE-complete on bipartite graphs. In this paper we show that PArcK is PSPACE-complete even when restricted to planar graphs of degree at most three by a reduction from Generalized Hex.

0.24

Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces

cs.GT cs.CCmath.COmath.OC ·2026-09-21 ·Michel Grabisch and. Hans Raj Tiwary
similarity 0.59
Abstract

We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

0.27

The Complexity of Undirected Partizan Edge Geography

cs.DS math.CO ·2026-09-16 ·Yuto Okada
similarity 0.58
Abstract · 9 pages, 6 figures

Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge. Two player alternately move their tokens and the first player who cannot move loses the game. Fraenkel and Simonson (TCS, 1993) showed that the winner determination of this game is PSPACE-complete on directed graphs, given a graph and token positions. This paper resolves its complexity on undirected graphs by showing the PSPACE-completeness on bipartite undirected graphs of maximum degree 3. The same reduction also works for a variant where two tokens cannot be placed on the same vertex.

0.53

The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness

cs.GT cs.CC ·2026-11-12 ·Ethan Dickey, Athina Terzoglou
theory similarity 0.58
Abstract · 51 pages, 11 figures

The tournament equilibrium set (TEQ), proposed by Schwartz in 1990, is a classical voting rule based on pairwise majority comparisons. Its definition is recursive: an alternative is judged by the alternatives that beat it, called its dominators, and by which of those dominators TEQ itself selects. Deciding whether a given alternative belongs to TEQ was known to be NP-hard and to lie in PSPACE. We close this gap by proving that the problem is PSPACE-complete. To our knowledge, this is the first PSPACE-completeness result for membership in a tournament solution. The hardness persists even when every nonempty subtournament has a unique minimal retentive set, the property conjectured by Schwartz to hold for all tournaments. Moreover, every such subtournament in our hard instances contains an alternative with at most three dominators. We prove that a single alternative with at most four dominators suffices both to guarantee uniqueness and to find a TEQ winner in $O(N^2)$ time. Thus, on our hard instances, finding one winner is efficient even though recognizing a specified winner is PSPACE-complete. We also study how the complexity changes with the dominator bound. If every nonempty subtournament has an alternative with at most one dominator, the entire TEQ can be computed in quadratic time; allowing two dominators makes membership NP-hard. Under the same condition with four dominators, all $t$ winners can be computed in $O(2^t N^2)$ time, where $N$ is the number of alternatives.

0.24