HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Nash and Correlated Equilibria: Some Complexity Considerations

Abstract : This paper deals with the complexity of computing Nash and correlated equilibria for a finite game in normal form. We examine the problems of checking the existence of equilibria satisfying a certain condition, such as "Given a game G and a number r, is there a Nash (correlated) equilibrium of G in which all players obtain an expected payoff of at least r?" or "Is there a unique Nash (correlated) equilibrium in G?" etc. We show that such problems are typically "hard" (NP-hard) for Nash equilibria but "easy" (polynomial) for correlated equilibria.
Complete list of metadata

Contributor : Antoine Haldemann Connect in order to contact the contributor
Submitted on : Sunday, November 18, 2012 - 9:38:55 PM
Last modification on : Sunday, November 18, 2012 - 9:39:36 PM

Links full text




Itzhak Gilboa, Eitan Zemel. Nash and Correlated Equilibria: Some Complexity Considerations. Games and Economic Behavior, Elsevier, 1989, vol. 1, pp. 80-93. ⟨10.1016/0899-8256(89)90006-7⟩. ⟨hal-00753241⟩



Record views