Doomsday equilibria for omega-regular games Journal Article


Author(s): Chatterjee, Krishnendu; Doyen, Laurent; Filiot, Emmanuel; Raskin, Jean F
Article Title: Doomsday equilibria for omega-regular games
Affiliation IST Austria
Abstract: Two-player games on graphs provide the theoretical framework 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. In this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile where 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 ω-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.
Journal Title: Information and Computation
Volume: 254
ISSN: 0890-5401
Publisher: Elsevier  
Date Published: 2017-06-01
Start Page: 296
End Page: 315
URL:
DOI: 10.1016/j.ic.2016.10.012
Notes: Supported by Austrian Science Fund (FWF) Grant No. P23499-N23, FWF NFN Grant No. S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award. Supported by the Belgian National Fund for Scientific Research. Supported by ERC Start grant (279499: inVEST).
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work