Settling the complexity of Nash equilibrium in congestion games

DOI10.1145/3406325.3451039arXiv2012.04327OpenAlexW3166070555MaRDI QIDQ6065264

Yakov Babichenko, Aviad Rubinstein

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.04327

zbMATH Keywords

computational complexitycongestion gamesgradient descentpotential gamesequilibrium computation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy ⋮ Discrete versions of the KKM lemma and their PPAD-completeness ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

This page was built for publication: Settling the complexity of Nash equilibrium in congestion games