2024/12/11 by Véronique Bruyère, Bruyère, Véronique, Jean-François Raskin +5
Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2412.08547
openalex publication_date 2024/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies the rational synthesis problem for multi-player games played on graphs when rational players are following subgame perfect equilibria. In these games, one player, the system, declares his strategy upfront, and the other players, composing the environment, then rationally respond by playing strategies forming a subgame perfect equilibrium. We study the complexity of the rational synthesis problem when the players have ω-regular objectives encoded as parity objectives. Our algorithm is based on an encoding into a three-player game with imperfect information, showing that the problem is in 2ExpTime. When the number of environment players is fixed, the problem is in ExpTime and is NP- and coNP-hard. Moreover, for a fixed number of players and reachability objectives, we get a polynomial algorithm.