Workspaces ---- 337staff act actionwebs actionwebslocal agv apesless apon automotive bcvtb bhc bipeds capecode certafcs cg chess chessadmin chesslocal chessworkshop clotho cosmoi cps cpslab croquet cyphysim dataflow ddosos denso densoeal densosas design dgc3 dgc3exec directors drosonetsim dsc eecs124 eecs149 eecs149lab eecs20 escher gm gsoc handsimdroid hcddes hcssas hilv hybrid hyper iab ieee1588 instructors mast metropolis modelica naomi nes nsferc pa presenters pret pss ptalon ptango ptconf ptdb ptemaf ptesdf ptexternal pthomas ptides ptidesarch ptolemy ptopenmodelica ptpresenters pturing reactable reap researchers scos softdevel softwalls spfsos superb tbd thales triq vw

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.

• 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.