Citation
Krishnendu Chatterjee, Tom Henzinger, Marcin Jurdzinski. "Games with Secure Equilibria". Theoretica Computer Science, 2006.

Abstract
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 sometimes 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 winning conditions, which include the games that arise in verification, there may be several Nash equilibria, but there is always a unique maximal payoff profile of a secure equilibrium. We show how this equilibrium can be computed in the case of \omega-regular winning conditions, and we characterize the memory requirements of strategies that achieve the equilibrium.

Electronic downloads

• secure-equilibria.ps · application/postscript · 444 kbytes. (Accepted for publication in March 2006.)

• HTML

  Krishnendu Chatterjee, Tom Henzinger, Marcin Jurdzinski.
  <a
  href="http://chess.eecs.berkeley.edu/pubs/83.html"
  >Games with Secure Equilibria</a>,
  <i>Theoretica Computer Science</i>,  2006.

• Plain text

  Krishnendu Chatterjee, Tom Henzinger, Marcin Jurdzinski.
  "Games with Secure Equilibria".
  <i>Theoretica Computer Science</i>,  2006.

• BibTeX

  @article{ChatterjeeHenzingerJurdzinski06_GamesWithSecureEquilibria,
      author = {Krishnendu Chatterjee and Tom Henzinger and Marcin
                Jurdzinski},
      title = {Games with Secure Equilibria},
      journal = {Theoretica Computer Science},
      year = {2006},
      abstract = {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 sometimes 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 winning conditions,
                which include the games that arise in
                verification, there may be several Nash
                equilibria, but there is always a unique maximal
                payoff profile of a secure equilibrium. We show
                how this equilibrium can be computed in the case
                of \omega-regular winning conditions, and we
                characterize the memory requirements of strategies
                that achieve the equilibrium. },
      URL = {http://chess.eecs.berkeley.edu/pubs/83.html}
  }
  

Posted by Krishnendu Chatterjee, PhD on 9 May 2006.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.