Summary
This paper studies how hard it is to find stable outcomes called Nash equilibria in certain network-based games where players share resources or coordinate actions. The authors show that computing these equilibria is as hard as a class of problems known as CLS-complete. This means finding such equilibria is computationally challenging and unlikely to have easy algorithms. They also relate this complexity result to finding special points called KKT points in certain mathematical problems.
What this means in practice
- •For algorithm designers: Understand limits on algorithmic efficiency for computing equilibria in network routing and coordination scenarios.
- •For optimization engineers: Recognize computational difficulty when solving for KKT points in bilinear optimization problems related to network games.
A theory result. No direct application yet.
Authors
Ioannis Anagnostides, Ioannis Panageas, Jingming Yan
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.