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⊆convf(S). Our main technical contribution is to prove that computing a fixed set is PPAD-hard even at inverse polynomial precision.
Figures & tables
Figure 1: A fixed point, a periodic-3 orbit, and a fixed set supported on 3 points.
Figure 2: Top row. The original rotation f and three scaled maps fα , with common fixed point x∗=0 . Gray curves depict the displacement flow, and black arrows show fα(x)−x . Teal points form approximate fixed sets with the same transition matrix and equal error across the three scales. Bottom row. A different map f and its three scaled maps. Teal points form regular 12 -gons; hollow orange points are their images under fα . Each support point is the midpoint of the images of its two neighbors, as illustrated by the orange chord. Thus, P(i,i−1)=P(i,i+1)=1/2 works at all three scales, with uniform stationary distribution.
Figure 3: The piecewise-linear interpolants p1 and p2 relative to x2 . Each successive refinement doubles the number of pieces and divides the maximum error by four.