Settling the complexity of Nash equilibrium in congestion games
Settling the complexity of Nash equilibrium in congestion games
复制标题
解决拥塞博弈中纳什均衡的复杂性
DOI：
10.1145/3406325.3451039
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
A. Rubinstein
中科院分区：
文献类型：
--
作者：
Y. Babichenko;A. Rubinstein
我们考虑（i）在拥塞博弈中找到一个（可能是混合的）纳什均衡的问题，以及（ii）找到一个光滑函数f：[0，1]n → n的梯度下降动力学的（指数精度）不动点的问题。我们证明了这些问题是等价的。我们的结果适用于各种明确的描述f，范围从（几乎一般）算术电路，5度多项式。根据[Fearnley等人，STOC 2021]，这意味着这些问题是PPAD完全的。作为推论，我们还得到了以下复杂性类的等价性：CCLS = PPAD <$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 → ℝ. 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 et al., STOC 2021], this implies that these problems are PPAD ∩ PLS-complete. As a corollary, we also obtain the following equivalence of complexity classes: CCLS = PPAD ⋂ PLS.
登录
查看更多内容
塔斯基定理、超模博弈和均衡的复杂性
DOI：
10.4230/lipics.itcs.2020.18
发表时间：
2020
期刊：
11th Innovations in Theoretical Computer Science Conference
影响因子：
--
作者：
Etessami, Kousha;Papadimitriou, Christos H;Rubinstein, Aviad;Yannakakis, Mihalis
通讯作者：
Yannakakis, Mihalis
提高 FLIP 最大割问题的平滑复杂度
影响因子：
1.3
作者：
Bibak, Ali;Carlson, Charles;Chandrasekaran, Karthekeyan
通讯作者：
Chandrasekaran, Karthekeyan
局部最大割和二值最大 CSP 的平滑复杂度
DOI：
10.1145/3357713.3384325
发表时间：
2020
期刊：
Proceedings of the 52th ACM Symposium on Theory of Computing
影响因子：
--
作者：
Chen, Xi;Guo, Chenghao;Vlatakis-Gkaragkounis, Emmanouil V.;Yannakakis, Mihalis;Zhang, Xinzhi
通讯作者：
Zhang, Xinzhi
势线的独特末端
影响因子：
--
作者：
Fearnley, John;Gordon, Spencer;Mehta, Ruta;Savani, Rahul
通讯作者：
Savani, Rahul
模仿游戏的近似纳什均衡：算法和复杂性
DOI：
10.5555/3398761.3398865
发表时间：
2020
期刊：
AAMAS Conference proceedings
影响因子：
--
作者：
Murhekar, Aniket and
通讯作者：
Murhekar, Aniket and