5 papers
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…
The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm +1
We consider the problem of computing stationary points in min-max optimization, with a particular focus on the special case of computing Nash equilibria in (two-)team zero-sum game…
The Complexity of Finding Local Optima in Contrastive Learning
Jingming Yan, Yiyuan Luo, Vaggos Chatziafratis +3
Contrastive learning is a powerful technique for discovering meaningful data representations by optimizing objectives based on , often given as a…
Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem
Fivos Kalogiannis, Jingming Yan, Ioannis Panageas
We study the problem of learning a Nash equilibrium (NE) in Markov games which is a cornerstone in multi-agent reinforcement learning (MARL). In particular, we focus on infinite-ho…