loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th Annual IEEE Symposium on Logic in Computer Science (LICS'04)
Games with Secure Equilibria
Turku, Finland
July 13-July 17
ISBN: 0-7695-2192-4
Krishnendu Chatterjee, University of California, Berkeley
Thomas A. Henzinger, University of California, Berkeley; EPFL, Switzerland
Marcin Jurdzinski, University of California, Berkeley; University of Warwick, UK
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 w-regular objectives, and we characterize the memory requirements of strategies that achieve the equilibrium.
Citation:
Krishnendu Chatterjee, Thomas A. Henzinger, Marcin Jurdzinski, "Games with Secure Equilibria," lics, pp.160-169, 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.