Computing correlated equilibria in multi-player games
Authors:
Open Access
- 1 July 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 55 (3) , 1-29
Abstract
We develop polynomial-time algorithms for finding correlated equilibria—a well-studied notion of rationality that generalizes the Nash equilibrium—in a broad class of succinctly representable multiplayer games, encompassing graphical games, anonymous games, polymatrix games, congestion games, scheduling games, local effect games, as well as several generalizations. Our algorithm is based on a variant of the existence proof due to Hart and Schmeidler, and employs linear programming duality, the ellipsoid algorithm, Markov chain steady state computations, as well as application-specific methods for computing multivariate expectations over product distributions. For anonymous games and graphical games of bounded tree-width, we provide a different polynomial-time algorithm for optimizing an arbitrary linear function over the set of correlated equilibria of the game. In contrast to our sweeping positive results for computing an arbitrary correlated equilibrium, we prove that optimizing over correlated equilibria is NP-hard in all of the other classes of games that we consider.Keywords
Funding Information
- National Science Foundation (CCR-0121555)
This publication has 26 references indexed in Scilit:
- Characterization of pure strategy equilibria in finite anonymous gamesJournal of Mathematical Economics, 2000
- A Simple Adaptive Procedure Leading to Correlated EquilibriumEconometrica, 2000
- Calibrated Learning and Correlated EquilibriumGames and Economic Behavior, 1997
- Congestion Games with Player-Specific Payoff FunctionsGames and Economic Behavior, 1996
- On the computational complexity and geometry of the first-order theory of the reals. Part III: Quantifier eliminationJournal of Symbolic Computation, 1992
- Coherent behavior in noncooperative gamesJournal of Economic Theory, 1990
- Subjectivity and correlation in randomized strategiesJournal of Mathematical Economics, 1974
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973
- An analog of the minimax theorem for vector payoffsPacific Journal of Mathematics, 1956
- Non-Cooperative GamesAnnals of Mathematics, 1951