9 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…
Efficient representations for team and imperfect-recall equilibrium computation
Luca Carminati, Brian Hu Zhang, Federico Cacciamani +4
Equilibrium finding in two-player zero-sum games with perfect recall is a well-studied topic that has led to many breakthroughs in computational game theory. This paper aims to gen…
A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm +1
Solving (Stampacchia) variational inequalities (SVIs) is a foundational problem at the heart of optimization. However, this expressivity comes at the cost of computational hardness…
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…
Learning and Computation of -Equilibria at the Frontier of Tractability
Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde +4
-equilibria -- and the associated notion of -regret -- are a powerful and flexible framework at the heart of online learning and game theory, whereby enriching the set of d…