6 citations · 12 across the 16 of their papers we have counts for
5 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…
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…
Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria
Anas Barakat, Ioannis Panageas, Antonios Varvitsiotis
Convex Markov Games (cMGs) were recently introduced as a broad class of multi-agent learning problems that generalize Markov games to settings where strategic agents optimize gener…
(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris +1
Follow the regularized leader FTRL is the premier algorithm for online optimization. However, despite decades of research on its convergence in constrained optimization -- and pote…
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…