Constrained existence problem for weak subgame perfect equilibria with -regular Boolean objectives

DOI10.1016/J.IC.2020.104594MaRDI QIDQ2029600zbMATH OpenOpenAlexFDO

Authors Thomas Brihaye, Véronique Bruyère, Aline Goeminne, Jean-François Raskin

Publication date 3 June 2021

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.03888

zbMATH Keywords

decidability of the constrained existence of an equilibriummultiplayer non zero-sum graph gameomega-regular objectivesweak subgame perfect equilibrium

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Equilibrium refinements (91A11) Games involving graphs (91A43) Games involving topology, set theory, or logic (91A44)

Abstract: We study multiplayer turn-based games played on a finite directed graph such that each player aims at satisfying an omega-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-B"uchi, Parity, Muller, Rabin, and Streett objectives, and PSPACE-complete for Reachability and Safety objectives (we only prove NP-membership for B"uchi 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 analysis of a fixpoint algorithm that computes the set of possible payoff profiles underlying weak SPEs.

Recommendations

• Constrained existence problem for weak subgame perfect equilibria with -regular Boolean objectives
• Constrained existence of weak subgame perfect equilibria in multiplayer Büchi games
• On the existence of weak subgame perfect equilibria
• On the existence of weak subgame perfect equilibria
• scientific article; zbMATH DE number 6767615
• Weak Pareto equilibria for multiobjective constrained games
• On existence of equilibrium pair for constrained generalized games
• On existence of Pareto equilibria for constrained multiobjective games
• Existence of Pareto equilibria for constrained multiobjective games in H-space
• Existence of generalised Pareto equilibria for constrained multiobjective games

Cites work

• Admissibility in Infinite Games
• An Accelerated Algorithm for 3-Color Parity Games with an Application to Timed Games
• Assume-admissible synthesis
• Automata, logics, and infinite games. A guide to current research
• Computer aided synthesis: a game-theoretic approach
• Equilibrium points in n -person games
• Explicit Muller games are PTIME
• Game theory
• Games with secure equilibria
• Generalized Parity Games
• Handbook of model checking
• scientific article; zbMATH DE number 5301288 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 6767615 (Why is no real title available?)
• scientific article; zbMATH DE number 7649921 (Why is no real title available?)
• Modalities for model checking: Branching time logic strikes back
• Non-zero sum games for reactive synthesis
• Number of quantifiers is better than number of tape cells
• On the existence of weak subgame perfect equilibria
• On the synthesis of strategies in infinite games
• Parameterized complexity of games with monotonically ordered \(\omega\)-regular objectives
• Perfect-information games with lower-semicontinuous payoffs
• Pure Nash equilibria in concurrent deterministic games
• Rational Behaviour and Strategy Construction in Infinite Multiplayer Games
• Rational synthesis
• Secure equilibria in weighted games
• Solution concepts and algorithms for infinite multiplayer games
• Subgame perfection for equilibria in quantitative reachability games
• The complexity of admissibility in omega-regular games
• The Complexity of Nash Equilibria in Infinite Multiplayer Games

Cited in

(8)

• Constrained existence of weak subgame perfect equilibria in multiplayer Büchi games
• On the existence of weak subgame perfect equilibria
• On the existence of weak subgame perfect equilibria
• Constrained existence problem for weak subgame perfect equilibria with -regular Boolean objectives
• The complexity of subgame perfect equilibria in quantitative reachability games
• As soon as possible but rationally
• Reachability games and friends: a journey through the Lens of memory and complexity (invited talk)
• The non-cooperative rational synthesis problem for SPEs and -regular objectives

This page was built for publication: Constrained existence problem for weak subgame perfect equilibria with \(\omega \)-regular Boolean objectives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029600)