---
_id: '681'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
- first_name: Emmanuel
  full_name: Filiot, Emmanuel
  last_name: Filiot
- first_name: Jean
  full_name: Raskin, Jean
  last_name: Raskin
citation:
  ama: Chatterjee K, Doyen L, Filiot E, Raskin J. Doomsday equilibria for omega-regular
    games. <i>Information and Computation</i>. 2017;254:296-315. doi:<a href="https://doi.org/10.1016/j.ic.2016.10.012">10.1016/j.ic.2016.10.012</a>
  apa: Chatterjee, K., Doyen, L., Filiot, E., &#38; Raskin, J. (2017). Doomsday equilibria
    for omega-regular games. <i>Information and Computation</i>. Elsevier. <a href="https://doi.org/10.1016/j.ic.2016.10.012">https://doi.org/10.1016/j.ic.2016.10.012</a>
  chicago: Chatterjee, Krishnendu, Laurent Doyen, Emmanuel Filiot, and Jean Raskin.
    “Doomsday Equilibria for Omega-Regular Games.” <i>Information and Computation</i>.
    Elsevier, 2017. <a href="https://doi.org/10.1016/j.ic.2016.10.012">https://doi.org/10.1016/j.ic.2016.10.012</a>.
  ieee: K. Chatterjee, L. Doyen, E. Filiot, and J. Raskin, “Doomsday equilibria for
    omega-regular games,” <i>Information and Computation</i>, vol. 254. Elsevier,
    pp. 296–315, 2017.
  ista: Chatterjee K, Doyen L, Filiot E, Raskin J. 2017. Doomsday equilibria for omega-regular
    games. Information and Computation. 254, 296–315.
  mla: Chatterjee, Krishnendu, et al. “Doomsday Equilibria for Omega-Regular Games.”
    <i>Information and Computation</i>, vol. 254, Elsevier, 2017, pp. 296–315, doi:<a
    href="https://doi.org/10.1016/j.ic.2016.10.012">10.1016/j.ic.2016.10.012</a>.
  short: K. Chatterjee, L. Doyen, E. Filiot, J. Raskin, Information and Computation
    254 (2017) 296–315.
date_created: 2018-12-11T11:47:53Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-02-21T16:06:02Z
day: '01'
department:
- _id: KrCh
doi: 10.1016/j.ic.2016.10.012
ec_funded: 1
external_id:
  arxiv:
  - '1311.3238'
intvolume: '       254'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1311.3238
month: '06'
oa: 1
oa_version: Submitted Version
page: 296 - 315
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
publication: Information and Computation
publication_identifier:
  issn:
  - '08905401'
publication_status: published
publisher: Elsevier
publist_id: '7036'
quality_controlled: '1'
related_material:
  record:
  - id: '10885'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Doomsday equilibria for omega-regular games
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 254
year: '2017'
...