Settling the complexity of Nash equilibrium in congestion games

Abstract

We consider (i) the problem of finding a (possibly mixed) Nash equilibrium in congestion games, and (ii) the problem of finding an (exponential precision) fixed point of the gradient descent dynamics of a smooth function $f:[0,1{]}^n\to \mathbb{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 [Fearnley, Goldberg, Hollender, Savani '20] this implies that these problems are PPAD$\cap$PLS-complete. As a corollary, we also obtain the following equivalence of complexity classes: CCLS = PPAD$\cap$PLS.