A Regret Minimization Perspective on Bilateral Trade

Details

This is an EC 2025 tutorial and will take place virtually on Wednesday, June 18, 2025, at 11am-1pm ET. Access to the tutorial is free, but please make sure to register (here) to receive the Zoom links to attend.

Abstract

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. This is one of the most fundamental economic interactions and has been studied intensively, starting from the seminal paper by Myerson and Satterthwaite [1]. While previous works cast this problem in the Bayesian setting, we focus on the recent line of research that studies the natural extension of this model to the online learning framework.

In the online learning model, no information is available at the outset to the intermediary, who has to learn “on the fly” the relevant features of the problem. In this tutorial, we aim to provide a comprehensive overview of the results in this area under different data-generation and feedback models. Specific focus will also be given to the various underlying learning techniques that may be of independent interest. Finally, we will present several open questions and future directions.

Keywords: bilateral trade, pricing, online learning

Target Audience

Students and researchers interested in problems at the intersection of economics and learning. 

Prerequisites

This tutorial is accessible to anyone with a mathematical background (e.g., from economics, computer science, or other technical fields). We assume no prerequisite notions on online learning, although familiarity with some basic notions such as regret, experts, and multi-armed bandits could be useful.

Tutorial Organization

2 hours with two 50-minute sessions with 20 minutes for questions/break.

Outline 

• Introduction to bilateral trade and its repeated version (Federico)

  • Bilateral trade and its online learning model [1,2]

  • Feedback Models and Budget Balance [2]

• Gain From Trade Maximization in Bilateral Trade (Martino)

  • Strong Budget Balance [2]

  • Weak Budget Balance [2,3,4]

  • Global Budget Balance [7,14]

• Related Models (Federico)

  • Contextual Bilateral Trade [10]

  • Brokerage [9,11,12]

  • Two-Sided Markets [5,13]

  • Beyond fixed price mechanisms [6]

Materials

• slides [link]

Some References

[1] R. Myerson, M. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29(2):265–281, 1983

[2] N. Cesa-Bianchi, T. Cesari, R. Colomboni, F. Fusco, S. Leonardi. Bilateral Trade. A Regret Minimization Perspective. MOR, 2023.

[3] Y. Azar, A. Fiat, F. Fusco. An α-regret Analysis of Adversarial Bilateral Trade. Artificial Intelligence, 2024. 

[4] N. Cesa-Bianchi, T. Cesari, R. Colomboni, F. Fusco, S. Leonardi. Regret Analysis of Bilateral Trade with a Smoothed Adversary. JMLR, 2024. 

[5] M. Babaioff, A. Frey, N. Nisan. Learning to Maximize Gains From Trade in Small Markets. EC’24.

[6] G. Aggarwal, A. Badanidiyuru, P. Duetting, F. Fusco. Selling joint ads: A regret minimization perspective. EC’24.

[7] M. Bernasconi, M. Castiglioni, A. Celli, F. Fusco. No-Regret Learning in Bilateral Trade via Global Budget Balance. STOC’24

[8] F. Bachoc, N. Cesa-Bianchi, T. Cesari, R. Colomboni. Fair online bilateral trade. NeurIPS’24.

[9] N. Bolić, T. Cesari, R. Colomboni. An Online Learning Theory of Brokerage. AAMAS’24.

[10] S. Gaucher, M. Bernasconi, M. Castiglioni, A. Celli, V. Perchet. Feature-based online bilateral trade. ICLR’25

[11] T. Cesari, R. Colomboni. An online learning theory of trading-volume maximization. ICLR’25

[12] F. Bachoc, T. Cesari, R. Colomboni. A tight regret analysis of non-parametric repeated contextual brokerage. AISTATS’25.

[13] A. Lunghi, M. Castiglioni, A. Marchesi. Online Two-Sided Markets: Many Buyers Enhance Learning. arXiv’25.

[14] H. Chen, Y. Jin, P. Lu, C. Zhang. Tight Regret Bounds for Fixed-Price Bilateral Trade. arXiv'25

About us

Martino Bernasconi

Martino Bernasconi is a Postdoctoral Researcher at the Computing Sciences Department of Bocconi University. He obtained his PhD from Politecnico di Milano, where he focused on Artificial Intelligence, Algorithmic Game Theory, Multi-Agent Learning, and Online Learning. His research explores optimal strategic behavior in interactions with intelligent agents across various economic models, with an emphasis on computational and learning challenges. Previously, he interned in Quantitative Research at J.P. Morgan in London. 

Federico Fusco 

Federico is an Assistant Professor at the Department of Computer, Control, and Management Engineering at Sapienza University of Rome. Previously, he was a PostDoc and completed his PhD under the supervision of Stefano Leonardi at the same University. During his PhD, he was hosted by Paul Duetting in Google Research Zurich as a Research Intern and then as a Student Researcher. Federico’s research interests span Algorithmic Game Theory, Online Learning, and Submodular Maximization.