---
OA_type: closed access
_id: '3895'
abstract:
- lang: eng
  text: 'In 2-player non-zero-sum games, Nash equilibria capture the options for rational
    behavior if each player attempts to maximize her payoff. In contrast to classical
    game theory, we consider lexicographic objectives: first, each player tries to
    maximize her own payoff, and then, the player tries to minimize the opponent''s
    payoff. Such objectives arise naturally in the verification of systems with multiple
    components. There, instead of proving that each component satisfies its specification
    no matter how the other components behave, it often suffices to prove that each
    component satisfies its specification provided that the other components satisfy
    their specifications. We say that a Nash equilibrium is secure if it is an equilibrium
    with respect to the lexicographic objectives of both players. We prove that in
    graph games with Borel objectives, which include the games that arise in verification,
    there may be several Nash equilibria, but there is always a unique maximal payoff
    profile of secure equilibria. We show how this equilibrium can be computed in
    the case of omega-regular objectives, and we characterize the memory requirements
    of strategies that achieve the equilibrium.'
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Marcin
  full_name: Jurdziński, Marcin
  last_name: Jurdziński
citation:
  ama: 'Chatterjee K, Henzinger TA, Jurdziński M. Games with secure equilibria. In:
    <i>Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science</i>.
    IEEE; 2004:160-169. doi:<a href="https://doi.org/10.1109/LICS.2004.1319610">10.1109/LICS.2004.1319610</a>'
  apa: 'Chatterjee, K., Henzinger, T. A., &#38; Jurdziński, M. (2004). Games with
    secure equilibria. In <i>Proceedings of the 19th Annual IEEE Symposium on Logic
    in Computer Science</i> (pp. 160–169). Turku, Finland: IEEE. <a href="https://doi.org/10.1109/LICS.2004.1319610">https://doi.org/10.1109/LICS.2004.1319610</a>'
  chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Marcin Jurdziński. “Games
    with Secure Equilibria.” In <i>Proceedings of the 19th Annual IEEE Symposium on
    Logic in Computer Science</i>, 160–69. IEEE, 2004. <a href="https://doi.org/10.1109/LICS.2004.1319610">https://doi.org/10.1109/LICS.2004.1319610</a>.
  ieee: K. Chatterjee, T. A. Henzinger, and M. Jurdziński, “Games with secure equilibria,”
    in <i>Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science</i>,
    Turku, Finland, 2004, pp. 160–169.
  ista: 'Chatterjee K, Henzinger TA, Jurdziński M. 2004. Games with secure equilibria.
    Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science. LICS:
    Logic in Computer Science, 160–169.'
  mla: Chatterjee, Krishnendu, et al. “Games with Secure Equilibria.” <i>Proceedings
    of the 19th Annual IEEE Symposium on Logic in Computer Science</i>, IEEE, 2004,
    pp. 160–69, doi:<a href="https://doi.org/10.1109/LICS.2004.1319610">10.1109/LICS.2004.1319610</a>.
  short: K. Chatterjee, T.A. Henzinger, M. Jurdziński, in:, Proceedings of the 19th
    Annual IEEE Symposium on Logic in Computer Science, IEEE, 2004, pp. 160–169.
conference:
  end_date: 2004-07-17
  location: Turku, Finland
  name: 'LICS: Logic in Computer Science'
  start_date: 2004-07-13
date_created: 2018-12-11T12:05:45Z
date_published: 2004-08-09T00:00:00Z
date_updated: 2026-09-11T09:05:35Z
day: '09'
doi: 10.1109/LICS.2004.1319610
extern: '1'
fulldoi: https://doi.org/10.1109/LICS.2004.1319610
language:
- iso: eng
month: '08'
oa_version: None
page: 160 - 169
publication: Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science
publication_identifier:
  isbn:
  - '0769521924'
  issn:
  - 1043-6871
publication_status: published
publisher: IEEE
publist_id: '2262'
status: public
title: Games with secure equilibria
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2004'
...