On the Complexity of Correlated Equilibria Beyond Normal-Form Games

Correlated equilibria are a fundamental solution concept in game theory, introduced in seminal work by Robert Aumann in the 1970s. A textbook fact is that correlated equilibria enjoy more desirable computational properties vis-`a-vis Nash equilibria: they can be computed in polynomial time in normal form games via linear programming, and are also amenable to learning via decentralized no-swap-regret dynamics. However, despite decades of research, the complexity beyond games of polynomial type—such as extensive-form games, congestion or routing games, and more broadly concave games—has remained a major open problem, first highlighted by Papadimitriou and Roughgarden (JACM ’08).

In this paper, we resolve several long-standing questions concerning the complexity of correlated equilibria and swap regret minimization. First, we show that computing a correlated equilibrium in concave quadratic games is as hard as computing the fixed point of a contraction mapping (\(Contr\)), providing the first strong evidence of intractability. Moreover, we establish an unconditional, information-theoretic lower bound ruling out the existence of a strongly sublinear swap regret minimizer: any online learning algorithm requires exponentially many iterations in the dimension \(d\) to guarantee at most \(1/poly(d)\) (average) swap regret.

To circumvent these hardness results, we examine the complexity of Φ-equilibria—tractable relaxations of correlated equilibria. We obtain a fully polynomial-time approximation scheme (FPTAS) for computing poly-dimensional Φ-equilibria in general concave games. We complement this by showing that \(Contr\)-hardness persists even under poly-dimensional swap deviations in the regime where the precision ϵ is exponentially small. Finally, we show that Contr-hardness can be bypassed in the canonical setting of concave <em>quadratic games</em>, for which we provide a \(poly(d,log(1/ϵ))\)-time algorithm for computing poly-dimensional Φ-equilibria. As a byproduct, we obtain an algorithm for computing fixed points of a mapping that is contracting with respect to an unknown Mahalanobis norm, which could be of independent interest