6 papers · 1 filter
Improved Hardness Results for Min-Max Optimization with Coupled Constraints
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
We investigate the computational complexity of min-max optimization under coupled constraints. The work of Daskalakis, Skoulakis, and Zampetakis [DSZ21] was the first to study min-…
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…
Single-dimensional Contract Design: Efficient Algorithms and Learning
Martino Bernasconi, Matteo Castiglioni, Andrea Celli
We study a Bayesian contract design problem in which a principal interacts with an unknown agent. We consider the single-parameter uncertainty model introduced by Alon et al. [2021…
Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
Brian Zhang, Gabriele Farina, Andrea Celli +1
We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse cor…
Feature-Based Online Bilateral Trade
Solenne Gaucher, Martino Bernasconi, Matteo Castiglioni +2
Bilateral trade models the problem of facilitating trades between a seller and a buyer having private valuations for the item being sold. In the online version of the problem, the…
Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games
Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides +7
We introduce a new approach for computing optimal equilibria via learning in games. It applies to extensive-form settings with any number of players, including mechanism design, in…