论文标题
解决交通拥堵游戏中纳什均衡的复杂性
Settling the complexity of Nash equilibrium in congestion games
论文作者
论文摘要
我们考虑（i）在拥塞游戏中找到（可能混合的）NASH平衡的问题，以及（ii）找到平滑函数的梯度下降动力学的（指数精度）固定点的问题。我们证明这些问题是等效的。我们的结果适用于$ f $的各种明确描述，范围从（几乎一般）算术电路到$ 5 $多项式。到[Fearnley，Goldberg，Hollender，Savani '20]的最新结果，这意味着这些问题是PPAD $ \ cap $ pls complete。作为推论，我们还获得了以下复杂性类别的等效性：ccls = ppad $ \ cap $ pls。
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 \rightarrow \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.
