paper
arXiv cs.LG
November 18th, 2026 at 5:00 AM

Fixed Sets and the Hardness of Computing Correlated Equilibria

arXiv:2610.28141v3 Announce Type: replace-cross 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.

#ai

Get stories like this every Monday

The week's most important AI news in one email. Free, unsubscribe anytime.

Score: 3.12

Engagement proxy: 0

Canonical link: https://arxiv.org/abs/2610.28141