Nash and Correlated Equilibria: Some Complexity Considerations

Itzhak Gilboa and Eitan Zemel
Additional contact information
Eitan Zemel: Northwestern University [Evanston]

Post-Print from HAL

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.

Keywords: Nash; Correlated Equilibria; Complexity Considerations (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (55)

Published in Games and Economic Behavior, 1989, vol. 1, pp. 80-93. ⟨10.1016/0899-8256(89)90006-7⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
Journal Article: Nash and correlated equilibria: Some complexity considerations (1989)
Working Paper: Nash and Correlated Equilibria: Some Complexity Considerations (1988)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-00753241

DOI: 10.1016/0899-8256(89)90006-7

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().