CS Paper Radar

Subgame Perfection in Graph Games with $ω$-Recognizable Preference Relations

Véronique Bruyère, Christophe Grandmont, Noémie Meunier, Jean-François Raskin

cs.GT ·submitted 2026-09-19 09:28 UTC · v1

Abstract

This paper investigates the constrained existence problem for subgame perfect equilibria (SPEs) in multiplayer graph games. In the proposed framework, each player has a preference relation over the set of plays, assumed to be $ω$-recognizable. Equivalently, he has a preference relation over a finite set of payoffs, and the set of plays with the same payoff is $ω$-regular, for each payoff. This generic framework avoids the need to focus on specific payoff functions. We show that the constrained SPE existence problem is EXPTIME-complete, as well as for Nash equilibria (NEs).

Closest papers

Nearest neighbours by meaning across the whole index.

The Complexity of Multiplayer Colonel Blotto Games with Player-Specific Values

cs.GT cs.CCecon.TH ·2026-09-24 ·Martin Bichler, Abheek Ghosh
similarity 0.67
Abstract · 64 pages, 3 figures

We study equilibrium computation in discrete multiplayer Colonel Blotto games with player-specific battlefield values. In the two-player model with common battlefield values, equilibria can be computed in polynomial time. We show that this tractability breaks down in the multiplayer model with player-specific values under the standard uniform tie-breaking rule. In particular, computing a $(c/n)$-approximate Nash equilibrium is PPAD-hard for some constant $c>0$, even when every player has three resources, where $n$ is the number of players. The main technical step is PPAD-hardness for computing a constant-approximate well-supported Nash equilibrium. In contrast, under uniform tie-breaking, a pure Nash equilibrium can be computed in polynomial time when every player has one resource. We also prove PPAD membership for computing $\varepsilon$-approximate Nash equilibria for inverse-exponentially small $\varepsilon$. Finally, for non-uniform monotone tie-breaking, we show PPAD-hardness even when every player has one resource and all players have identical battlefield values.

0.25

Individual Rationality in Constrained Hedonic Games: Friends, Enemies, and Neutrals

cs.GT ·2026-08-14 ·Šimon Schierreich, Ildikó Schlotter
publishedtheory similarity 0.62
Abstract

We study constrained coalition formation in games induced by friends, enemies, and neutrals, under the two standard refinements of additively separable preferences: friend-oriented and enemy-oriented. We ask for partitions that are individually rational (IR), while additionally requiring exactly $k$ non-empty coalitions, each satisfying a prescribed lower and upper bound on its size. Although IR alone is trivial to satisfy for any hedonic game, the size constraints make it computationally intractable to decide whether a feasible partition exists. The two models tell strikingly different stories. Under enemy-oriented preferences, the problem collapses to size-constrained graph coloring, and its complexity follows accordingly. Under friend-oriented preferences, however, the picture is far more intricate, and is governed by the enmity structure rather than the friendships. The complexity is further shaped by two factors: how strict the imposed size requirements are, and whether relationships are symmetric or asymmetric, with several cases turning out tractable in the symmetric setting but intractable once asymmetry is allowed. Charting this boundary in terms of both classical and parameterized complexity, we provide a complete understanding of which properties of the friend/enemy structure are responsible for hardness.

0.23

Strategy recovery for Mean-Payoff Games is as hard as solving them from scratch

cs.GT cs.DS ·2026-10-18 ·Dani Dorfman, Uri Zwick
published similarity 0.62
Abstract · To appear in SOSA 2027

Mean-Payoff Games (MPGs) form an interesting family of deterministic, infinite-duration, zero-sum, turn-based games played by two players on a finite weighted directed graph. The goal of the players is to minimize, respectively maximize, the $\textit{limiting average}$ of the costs of the edges on an infinite path constructed by the two players. The complexity of solving MPGs is a long-standing open question. The decision problem associated with these games is known to be in $\text{NP}\cap \text{co-NP}$, and even $\text{UP}\cap \text{co-UP}$, yet the problem is not known to be in $\text{P}$. This is one of the simplest combinatorial problems with such a status. A full solution of an MPG gives the $\textit{value}$ of each vertex of the game, along with a pair of $\textit{optimal strategies}$ for the two players. (Each player has a succinct $\textit{positional}$ optimal strategy.) The problem of finding optimal strategies for the players given the values of all vertices is known as the $\textit{strategy recovery}$ problem. We describe a simple reduction from the problem of solving MPGs to the strategy recovery problem for MPGs. This shows that the strategy recovery problem for MPGs is essentially as hard as solving MPGs from scratch, i.e., without knowing the values. The reduction uses simple $\textit{game transformations}$ and simple $\textit{self-reducibility}$ and $\textit{peeling}$ arguments. This answers a question of Andersson and Miltersen. Mamino obtained a similar result for $\textit{stochastic}$ games with a limiting average objective, but his technique does not extend to deterministic games such as MPGs. We go one step further and show that finding an optimal strategy for one of the players of an MPG remains hard even if an optimal strategy of the second player, and hence all the values, are known.

0.19

Breaking the One-Player Extension Barrier: History-Aware Repair for Multiplayer Approximate Nash Equilibria

cs.GT ·2026-11-04 ·Jinqi Tang, Shihong Ding, Cong Fang
similarity 0.62
Abstract

Computation of Nash equilibria is a central problem in algorithmic game theory, yet exact equilibrium computation is $\mathsf{PPAD}$-complete even for two-player games. This hardness motivates the study of polynomial-time algorithms for approximate Nash equilibria. While substantial progress has been made for two-player and three-player games, existing algorithms for general $m$-player games have largely relied on repeatedly applying one-player extension starting from improved fixed-player algorithms. Such improvements can at best strengthen the classical $1-1/m$ guarantee to $1-1/(m-c)$, for some constant $c$ independent of $m$. We break this long-standing barrier by developing an iterative algorithm that directly tackles general $m$-player games and achieves a $(1-(σ_{\star}-ε)/m)$-approximation for fixed $ε> 0$ and sufficiently large $m$, where $σ_\star\approx1.5867$ is the unique root in $(1,2)$ of $σ_\star^3-19σ_\star^2+27σ_\star+1=0$. Our approach rests on a novel iterative descent-and-repair framework that allows multiple rounds of repair. At the heart of our analysis is a new potential function inspired by continuous-time dynamics, which certifies progress across iterations and ensures polynomial-time termination. Our results highlight the power of history-aware, iterative repair in breaking approximation barriers for multiplayer games.

0.13

On Existence and Computational Complexity of Quasi-strict Equilibria

cs.GT ·2026-11-04 ·Kristoffer Arnsfelt Hansen, Xinhao Nie
similarity 0.62
Abstract

Quasi-strict Nash equilibrium, introduced by Harsanyi in 1973, is the Nash equilibrium refinement that requires every pure best response to be played with positive probability. Norde established that any bimatrix game admits a quasi-strict Nash equilibrium. We give a substantially simpler proof of this result that in particular avoids an intricate limit argument used in the final step of the proof by Norde. Our existence proof allows us to positively resolve the outstanding open question of PPAD membership of the problem of computing a quasi-strict Nash equilibrium, thereby settling its precise complexity. In games with three or more players, a quasi-strict Nash equilibrium is not guaranteed to exist, leading to the natural problem of deciding the existence of a quasi-strict Nash equilibrium in a given strategic form game. We show that this problem is $\exists\mathbb{R}$-complete, strengthening a previous NP-hardness result.

0.07

The Complexity of Computing Nash Equilibria in Colonel Blotto Games

cs.GT cs.CC ·2026-10-05 ·Vasilis Pollatos, Andreas Kontogiannis
theory similarity 0.62
Abstract

We study the complexity of Nash equilibrium computation in discrete Colonel Blotto games. For two-player general-sum Colonel Blotto with monotonic piecewise-constant battlefield payoffs, we show that computing an inverse-polynomial approximate Nash equilibrium is PPAD-hard, even with only two battlefields and a constant number of pieces per battlefield, thereby resolving an open question of [KPF+25]. Allowing more battlefields, the hardness persists when every battlefield payoff is $2$-piecewise constant with respect to either player's allocation. A general PPAD-membership theorem for multiplayer Blotto with arbitrary local reward functions then implies PPAD-completeness for both hardness results. Motivated by fixed-rank bimatrix games, we then identify a tractable frontier within two-player general-sum Colonel Blotto. If the social payoff has rank-$r$ structure, then, for every fixed $r$, an $\varepsilon$-Nash equilibrium can be computed in time polynomial in $B_1,B_2,k$, and $1/\varepsilon$. Thus constant-rank two-player Colonel Blotto remains tractable despite its exponentially large pure strategy spaces. Finally, we study multiplayer winner-takes-all Colonel Blotto with player-specific battlefield values and uncover a sharp tie-breaking frontier. If every highest bidder receives her full battlefield value, an exact pure Nash equilibrium can be computed in polynomial time for arbitrary binary-encoded budgets. In contrast, under ordinary equal splitting among highest bidders, we prove that computing an inverse-polynomial-accuracy Nash equilibrium is PPAD-hard even with only five players. This resolves an open question posed in concurrent work by Bichler and Ghosh [BG26], who established PPAD-hardness in the same player-specific equal-splitting setting when the number of players grows with the instance and asked whether hardness persists for a constant number of players.

0.03

Bidding Games with Rewards: Taming Infinite Configuration Space

cs.GT ·2026-08-31 ·Matan Pinkas
similarity 0.61
Abstract

Bidding games are graph games in which a token is placed on a vertex, each player starts with an initial budget, and a simultaneous auction determines which player moves the token; the players' budgets are then updated accordingly. Motivated by scenarios such as resource-allocation systems in which agents receive periodic rewards (e.g., credits, energy) while competing for control, we introduce and study bidding games with rewards, in which, at each vertex, players may receive additional budget, incentivizing desired behaviors. We focus on reachability discrete poorman bidding games with rewards (DPBGr). The main challenge when compared to discrete bidding games without rewards is that the configuration graph is infinite. To this end we introduce a novel technique to eliminate plays with suboptimal infixes. This enables focusing on a finite part of the infinite configuration graph in order to solve the game via approximation to continuous bidding games with overall complexity in EXP. Finally, we discuss a new type of strategy, usable on a subclass of DPBGr, which guarantee a winning strategy for the reachability player. Membership in this subclass is shown to be in NP.

0.13

Algorithms with Smoothed Polynomial-Time Complexity for Deterministic Discounted-sum and Mean-payoff Games

cs.GT cs.DS ·2026-10-09 ·Ali Asadi, Krishnendu Chatterjee, Ruichen Luo
similarity 0.61
Abstract

Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min Player. The respective player chooses outgoing edges from their vertices. We consider these games with the classical discounted-sum and mean-payoff objectives. The goal of the Max Player is to maximize the objective against the adversarial Min Player. These games lie in NP $\cap$ coNP and are among the rare combinatorial problems that belong to this complexity class, yet the existence of a polynomial-time algorithm is a major open question. All known deterministic algorithms require exponential time in the worst case, while the classical strategy iteration (policy iteration) algorithm is remarkably efficient in practice, which motivates the study of the smoothed complexity of these games. Previous results established a smoothed polynomial-time bound only for the restricted class of ergodic games and presented only a high-probability guarantee. Our main result is a new analysis technique for a variant of the strategy iteration algorithm, and we show these algorithms achieve smoothed polynomial complexity for general game graphs with both high-probability and expected runtime guarantees. In particular, our result removes the ergodicity restriction of prior work and strengthens the high-probability guarantee to the stronger expected-runtime guarantee, thereby resolving the open question on the smoothed complexity of these games.

0.50