The Library
Games with secure equilibria
Tools
Chatterjee, Krishnendu, Henzinger, Thomas A. and Jurdzinski, Marcin (2006) Games with secure equilibria. In: 3rd International Symposium on Formal Methods for Components and Objects, Leiden, Netherlands, 2-05 Nov 2004. Published in: Theoretical Computer Science, 365 (1-2). pp. 67-82. doi:10.1016/j.tcs.2006.07.032 ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.tcs.2006.07.032
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. (c) 2006 Elsevier B.V. All rights reserved.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Theoretical Computer Science | ||||
Publisher: | Elsevier Science BV | ||||
ISSN: | 0304-3975 | ||||
Official Date: | 10 November 2006 | ||||
Dates: |
|
||||
Volume: | 365 | ||||
Number: | 1-2 | ||||
Number of Pages: | 16 | ||||
Page Range: | pp. 67-82 | ||||
DOI: | 10.1016/j.tcs.2006.07.032 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 3rd International Symposium on Formal Methods for Components and Objects | ||||
Type of Event: | Other | ||||
Location of Event: | Leiden, Netherlands | ||||
Date(s) of Event: | 2-05 Nov 2004 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |