Paper Info
Title
Constrained Existence Problem for Weak Subgame Perfect Equilibria with ω-Regular Boolean Objectives.
Abstract
Abstract We study multiplayer turn-based games played on a finite directed graph such that each player aims at satisfying an ω-regular Boolean objective. Instead of the well-known notions of Nash equilibrium (NE) and subgame perfect equilibrium (SPE), we focus on the recent notion of weak subgame perfect equilibrium (weak SPE), a refinement of SPE. In this setting, players who deviate can only use the subclass of strategies that differ from the original one on a finite number of histories. We are interested in the constrained existence problem for weak SPEs. We provide a complete characterization of the computational complexity of this problem: it is P-complete for Explicit Muller objectives, NP-complete for Co-Buchi, Parity, Muller, Rabin, and Streett objectives, and PSPACE-complete for Reachability and Safety objectives (we only prove NP-membership for Buchi objectives). We also show that the constrained existence problem is fixed parameter tractable and is polynomial when the number of players is fixed. All these results are based on a fine-grained analysis of a fixpoint algorithm that computes the set of possible payoff profiles underlying weak SPEs.
Year
DOI
Venue
2018
10.1016/J.IC.2020.104594
GandALF
DocType
Citations 
PageRank 
Journal
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Thomas Brihaye146035.91
Véronique Bruyère242943.59
Aline Goeminne302.03
Jean-François Raskin41735100.15