The Complexity of Nash Equilibrium in Network Congestion and Coordination Games
arXiv:2609.33225
Abstract
We show that computing a Nash equilibrium is CLS-complete for linear network congestion and network coordination games. As a result, finding a KKT point of a bilinear polynomial is CLS-complete.