Subgame perfect equilibrium problem shown EXPTIME-complete in graph games
Subgame Perfection in Graph Games with $ω$-Recognizable Preference Relations
Computer Science and Game Theory
Summary
This paper looks at how players' preferences in multiplayer games on graphs can be modeled in a very general way using recognizable patterns over infinite plays. The researchers consider situations where each player has clear preferences, but without focusing on any particular way of scoring outcomes. They show that deciding whether players can follow strategies that form stable patterns, called subgame perfect equilibria, is a problem that is computationally very hard — specifically, it lies in a complexity class called EXPTIME-complete. The same difficulty applies to the related concept of Nash equilibria.
What this means in practice
- •For game designers: Determine the computational limits of verifying stable strategies in multiplayer games with complex preferences.
- •For automated verification engineers: Understand complexity bounds when synthesizing strategies ensuring stable outcomes in system models with infinite behaviors.
A theory result. No direct application yet.
Authors
Véronique Bruyère, Christophe Grandmont, Noémie Meunier, Jean-François Raskin
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).