2 citations · 6 across the 31 of their papers we have counts for
4 papers · 1 filter
CLS Hardness of 2D Min-Max Optimization with Product Constraints
Alkis Kalavasis, Panagiotis Patsilinakos, Stratis Skoulakis +1
We study the complexity of computing approximate first-order Nash equilibria in min-max optimization problems with one dimensional min and max players and product constraints. For…
Computational Lower Bounds for Regret Minimization in Normal-Form Games
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm
A celebrated connection in the interface of online learning and game theory establishes that players minimizing swap regret converge to correlated equilibria (CE) -- a seminal game…
Barriers to Welfare Maximization with No-Regret Learning
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm
A celebrated result in the interface of online learning and game theory guarantees that the repeated interaction of no-regret players leads to a coarse correlated equilibrium (CCE)…
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm +1
Characterizing the performance of no-regret dynamics in multi-player games is a foundational problem at the interface of online learning and game theory. Recent results have reveal…