  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.
