*banner
 

Games with Secure Equilibria
Krishnendu Chatterjee, Tom Henzinger, Marcin Jurdzinski

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.)
Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess