2026/07/27 by Yakov Babichenko, Aviad Rubinstein
paper · doi:10.1137/21m1430042
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 [Formula: see text]. We prove that these problems are equivalent. Our result holds for various explicit descriptions of [Formula: see text], ranging from (almost general) arithmetic circuits to degree-5 polynomials. In particular, this implies that these problems are [Formula: see text]-complete. As a corollary, we also obtain the following equivalence of complexity classes: [Formula: see text]