Abstract:

We consider (i) the problem of finding a (possibly mixed) Nash equilibrium in congestion game, and (ii) the problem of finding an (exponential precision) fixed point of the gradient descent dynamics of a smooth function f ∶ [0, 1]^n → R. We prove that these problems are equivalent. Our result holds for various explicit descriptions of f, ranging from (almost general) arithmetic circuits, to degree-5 polynomials. By a very recent result of [FGHS20], this implies that these problems are PPAD ∩ PLS-complete. As a corollary, we also obtain the following equivalence of complexity classes:

CCLS = PPAD∩PLS

Zoom https://technion.zoom.us/j/95592625013