Nash and Correlated Equilibria: Some Complexity Considerations

Preprint
Publisher Website
Google Scholar
    • preprint
      • Published in RePEc
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. (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.)

This publication has 0 references indexed in Scilit: