5 papers
Polynomial-time computation of -contraction fixed points for even
Constantinos Daskalakis, Gabriele Farina, Brian Hu Zhang
We give a -time algorithm that computes an -approximate fixed point of any -nonexpansive map , where $\m…
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…
Steering No-Regret Learners to a Desired Equilibrium
Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides +7
A mediator observes no-regret learners playing an extensive-form game repeatedly across rounds. The mediator attempts to steer players toward some desirable predetermined equil…
Hidden-Role Games: Equilibrium Concepts and Computation
Luca Carminati, Brian Hu Zhang, Gabriele Farina +2
In this paper, we study the class of games known as hidden-role games in which players are assigned privately to teams and are faced with the challenge of recognizing and cooperati…
Efficient -Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
Brian Hu Zhang, Ioannis Anagnostides, Gabriele Farina +1
Recent breakthrough results by Dagan, Daskalakis, Fishelson and Golowich [2023] and Peng and Rubinstein [2023] established an efficient algorithm attaining at most swap regret…