MIT and CMU Prove Correlated Equilibria Intractable Beyond Polynomial Games

A team of researchers from MIT, CMU, and the University of Patras has resolved long-standing questions about the computational complexity of correlated equilibria—a fundamental solution concept in game theory that models strategic interactions where players coordinate via a mediator. The paper, authored by Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, and Brian Hu Zhang, tackles the class of games beyond normal-form (e.g., extensive-form, congestion, and concave games). The team shows that computing a correlated equilibrium in concave quadratic games is Contr-hard, meaning it is at least as difficult as computing a fixed point of a contraction mapping—a classic problem with no known polynomial-time algorithm. They also prove an unconditional information-theoretic lower bound: any online learning algorithm requires exponentially many iterations in the dimension d to guarantee sublinear (average) swap regret, ruling out efficient minimizers for high-dimensional settings.

To circumvent these negative results, the authors explore a relaxation called Φ-equilibria, which are computationally tractable approximations of correlated equilibria. For general concave games, they provide a fully polynomial-time approximation scheme (FPTAS) for computing poly-dimensional Φ-equilibria. This holds even when the deviation set Φ grows with dimension. However, they show that Contr-hardness persists when the precision ε is exponentially small. As a silver lining, the team develops a poly(d, log(1/ε))-time algorithm for concave quadratic games, bypassing the hardness for practical precision levels. A byproduct of this work is a new algorithm for computing fixed points of a mapping that is contracting with respect to an unknown Mahalanobis norm, which may have independent applications in optimization and economics. This paper supersedes the authors' earlier work (arXiv:2406.13116) and will likely influence future research at the intersection of game theory, online learning, and computational complexity.