pipette
ESEspañol

Fixed Sets and the Hardness of Computing Correlated Equilibria

Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, Brian Hu Zhang

Preprint

In the authors' words

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 is a nonempty finite set such that . Our main technical contribution is to prove that computing a fixed set is PPAD-hard even at inverse polynomial precision.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.