Settling the Complexity of Nash Equilibrium in Congestion Games
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 over the cube. We prove that these problems are equivalent.
Our result holds for various explicit descriptions of the function, ranging from (almost general) arithmetic circuits, to degree-5 polynomials. By a very recent result of [Fearnley, Goldberg, Hollender, Savani 2020], this implies that these problems are PPAD∩PLS-complete. As a corollary, we also obtain the following equivalence of complexity classes: CCLS=PPAD∩PLS.
Remark: The talk will not assume prior knowledge of the complexity classes (PPAD, PLS, CCLS).
Joint work with Aviad Rubinstein
To view the seminar recording, click here
Last Updated Date : 22/12/2020