Computing correlated equilibria as hard as computing Nash equilibria
Fixed Sets and the Hardness of Computing Correlated Equilibria
Computer Science and Game TheoryComputational ComplexityData Structures and AlgorithmsMachine Learning
Summary
The paper shows that finding approximate correlated equilibria, a type of solution concept in game theory, is just as computationally difficult as finding Nash equilibria, which are traditionally considered harder to compute. The authors introduce a new concept called fixed sets, which generalizes fixed points in mathematics, and prove that calculating these sets is computationally hard. This challenges the usual belief that correlated equilibria are easier to work with than Nash equilibria.
What this means in practice
- •For algorithm designers: Designing algorithms for equilibrium computation must account for the inherent computational hardness of approximating correlated equilibria.
- •For economic modelers: Evaluating strategic behaviors using correlated equilibria should consider this equivalence in computational difficulty with Nash equilibria.
A theory result. No direct application yet.
Authors
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, Brian Hu Zhang
Abstract
We show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, and thus polynomial-time equivalent to finding a Nash equilibrium. This challenges the conventional view in game theory that correlated equilibria are more tractable objects than Nash equilibria. From a conceptual standpoint, we connect correlated equilibria to a natural generalization of fixed points, which we call fixed sets. A fixed set of a continuous function $f$ is a nonempty finite set $S$ such that $S \subseteq \operatorname{conv} f(S)$. Our main technical contribution is to prove that computing a fixed set is PPAD-hard even at inverse polynomial precision.