44 citations · 88 across the 37 of their papers we have counts for
4 papers · 1 filter
The Fine-Grained Complexity of Approximate Nash Equilibrium and Free Games
Noah Golowich
We study the fine-grained complexity of computing approximate Nash equilibria and approximating the value of free games in the regime where the approximation error vanishes. Under…
On the Complexity of Correlated Equilibria Beyond Normal-Form Games
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3
Correlated equilibria are a fundamental solution concept in game theory. However, despite decades of research, the complexity beyond games of polynomial type -- such as extensive-f…
A Lower Bound on Swap Regret in Extensive-Form Games
Constantinos Daskalakis, Gabriele Farina, Noah Golowich +2
Recent simultaneous works by Peng and Rubinstein [2024] and Dagan et al. [2024] have demonstrated the existence of a no-swap-regret learning algorithm that can reach average sw…
Smooth Nash Equilibria: Algorithms and Complexity
Constantinos Daskalakis, Noah Golowich, Nika Haghtalab +1
A fundamental shortcoming of the concept of Nash equilibrium is its computational intractability: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, in…