20 papers
Bicriteria Multidimensional Mechanism Design with Side Information
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm
We develop a versatile methodology for multidimensional mechanism design that incorporates side information about agents to generate high welfare and high revenue simultaneously. S…
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…
Faster Game Solving via Hyperparameter Schedules
Naifeng Zhang, Stephen McAleer, Tuomas Sandholm
Counterfactual regret minimization (CFR) algorithms are a foundational class of methods for solving imperfect-information games, with the time average of their iterates converging…