4 papers · 1 filter
The Complexity of Nash Equilibrium in Network Congestion and Coordination Games
Ioannis Anagnostides, Ioannis Panageas, Jingming Yan
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…
Finding a Positive Index Nash Equilibrium is PPADS-Complete
Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos +1
Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the…
The Computational Complexity of Team Zero-Sum Games
Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm +1
A celebrated consequence of the minimax theorem is that two-player zero-sum games admit a tractable equilibrium characterization. In many central applications, however, each side c…
On the Computational Complexity of Performative Prediction
Ioannis Anagnostides, Rohan Chauhan, Ioannis Panageas +2
Performative prediction captures the phenomenon where deploying a predictive model shifts the underlying data distribution. While simple retraining dynamics are known to converge l…