Games with secure equilibria

K. Chatterjee, T.A. Henzinger, M. Jurdziński, Theoretical Computer Science 365 (2006) 67–82.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
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 ω-regular winning conditions, and we characterize the memory requirements of strategies that achieve the equilibrium.
Publishing Year
Date Published
2006-08-07
Journal Title
Theoretical Computer Science
Volume
365
Issue
1-2
Page
67 - 82
IST-REx-ID

Cite this

Chatterjee K, Henzinger TA, Jurdziński M. Games with secure equilibria. Theoretical Computer Science. 2006;365(1-2):67-82. doi:10.1016/j.tcs.2006.07.032
Chatterjee, K., Henzinger, T. A., & Jurdziński, M. (2006). Games with secure equilibria. Theoretical Computer Science, 365(1–2), 67–82. https://doi.org/10.1016/j.tcs.2006.07.032
Chatterjee, Krishnendu, Thomas A Henzinger, and Marcin Jurdziński. “Games with Secure Equilibria.” Theoretical Computer Science 365, no. 1–2 (2006): 67–82. https://doi.org/10.1016/j.tcs.2006.07.032.
K. Chatterjee, T. A. Henzinger, and M. Jurdziński, “Games with secure equilibria,” Theoretical Computer Science, vol. 365, no. 1–2, pp. 67–82, 2006.
Chatterjee K, Henzinger TA, Jurdziński M. 2006. Games with secure equilibria. Theoretical Computer Science. 365(1–2), 67–82.
Chatterjee, Krishnendu, et al. “Games with Secure Equilibria.” Theoretical Computer Science, vol. 365, no. 1–2, Elsevier, 2006, pp. 67–82, doi:10.1016/j.tcs.2006.07.032.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar