5 papers · 1 filter
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…
Charting the Shapes of Stories with Game Theory
Constantinos Daskalakis, Ian Gemp, Yanchen Jiang +3
Stories are records of our experiences and their analysis reveals insights into the nature of being human. Successful analyses are often interdisciplinary, leveraging mathematical…
Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
Yang Cai, Constantinos Daskalakis, Haipeng Luo +2
Learning and computation of equilibria are central problems in game theory, theory of computation, and artificial intelligence. In this work, we introduce proximal regret, a new no…
On Tractable -Equilibria in Non-Concave Games
Yang Cai, Constantinos Daskalakis, Haipeng Luo +2
While Online Gradient Descent and other no-regret learning procedures are known to efficiently converge to a coarse correlated equilibrium in games where each agent's utility is co…
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…