pipette
ENEnglish

Fixed Sets and the Hardness of Computing Correlated Equilibria

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

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.