Doomsday equilibria for omega-regular games

DOI10.1007/978-3-642-54013-4_5zbMATH Open1370.68164arXiv1311.3238OpenAlexW2548450637MaRDI QIDQ528193FDOQ528193

Authors: Krishnendu Chatterjee, Laurent Doyen, Emmanuel Filiot, Jean-François Raskin 

Publication date: 12 May 2017

Published in: Lecture Notes in Computer Science, Information and Computation (Search for Journal in Brave)

Abstract: Two-player games on graphs provide the theoretical frame- work for many important problems such as reactive synthesis. While the traditional study of two-player zero-sum games has been extended to multi-player games with several notions of equilibria, they are decidable only for perfect-information games, whereas several applications require imperfect-information games. In this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile such that all players satisfy their own objective, and if any coalition of players deviates and violates even one of the players objective, then the objective of every player is violated. We present algorithms and complexity results for deciding the existence of doomsday equilibria for various classes of omega-regular objectives, both for imperfect-information games, and for perfect-information games. We provide optimal complexity bounds for imperfect-information games, and in most cases for perfect-information games.

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

Recommendations

• Doomsday equilibria for omega-regular games
• Quantitative solution of omega-regular games
• Mean-payoff games with \(\omega\)-regular specifications
• Quantitative solution of \(\omega\)-regular games
• A survey of stochastic \(\omega \)-regular games
• Equilibrium existence and approximation of regular discontinuous games
• Equilibria and approximate equilibria in infinite potential games
• scientific article; zbMATH DE number 1820647
• Epsilon-equilibria of perturbed games
• Tools and Algorithms for the Construction and Analysis of Systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43)

Cites Work

• Equilibrium points in n -person games
• Stochastic Games
• Alternating-time temporal logic
• Borel determinacy
• Title not available (Why is that?)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Automata, logics, and infinite games. A guide to current research
• Supervisory Control of a Class of Discrete Event Processes
• Observations on determinization of Büchi automata
• Reasoning about strategies
• What makes \textsc{Atl}* decidable? A decidable fragment of strategy logic
• On the power of imperfect information
• Rational synthesis
• The complexity of Nash equilibria in stochastic multiplayer games
• From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
• Playing games with boxes and diamonds.
• Games with secure equilibria
• Strategy logic
• Bounded Synthesis
• ATL with strategy contexts: expressiveness and model checking
• Deterministic generators and games for Ltl fragments
• Number of quantifiers is better than number of tape cells
• Generalized Parity Games
• Algorithms for Omega-Regular Games with Imperfect Information
• An Antichain Algorithm for LTL Realizability
• Antichains and compositional algorithms for LTL synthesis
• A Temporal Logic for the Interaction of Strategies
• Definability in the monadic second-order theory of successor
• Formal analysis of multiparty contract signing

Cited In (9)

• Reasoning About Strategies
• A game-theoretic approach for the synthesis of complex systems
• A game-theoretic approach to indistinguishability of winning objectives as user privacy
• On the existence of weak subgame perfect equilibria
• On the Existence of Weak Subgame Perfect Equilibria
• Reasoning about Quality and Fuzziness of Strategic Behaviors
• Assume-admissible synthesis
• Reactive synthesis without regret
• Doomsday equilibria for omega-regular games

This page was built for publication: Doomsday equilibria for omega-regular games

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