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.
Type de document :
Article dans une revue
Games and Economic Behavior, Elsevier, 1989, vol. 1, pp. 80-93. 〈10.1016/0899-8256(89)90006-7〉
Liste complète des métadonnées

https://hal-hec.archives-ouvertes.fr/hal-00753241
Contributeur : Amaury Bouvet <>
Soumis le : dimanche 18 novembre 2012 - 21:38:55
Dernière modification le : dimanche 18 novembre 2012 - 21:39:36

Lien texte intégral

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

133