# Learning to Maximize Gains From Trade in Small Markets

arXiv: https://arxiv.org/abs/2401.11596 · HTML: https://mlsanity.com/paper/2401.11596/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 25 references that are in the map.
- First posted on arXiv 21 Jan 2024.

## Builds on (most cited first, 14 of 14)

- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Sample Complexity of Automated Mechanism Design](https://mlsanity.com/paper/1606.04145/) (2016)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [The Sample Complexity of Auctions with Side Information](https://mlsanity.com/paper/1511.02296/) (2015)
- [The Sample Complexity of Up-to-varepsilon Multi-Dimensional Revenue Maximization](https://mlsanity.com/paper/1808.02458/) (2018)
- [Fixed-Price Approximations in Bilateral Trade](https://mlsanity.com/paper/2107.14327/) (2021)
- [Approximately Efficient Bilateral Trade](https://mlsanity.com/paper/2111.03611/) (2021)
- [(Almost) Efficient Mechanisms for Bilateral Trading](https://mlsanity.com/paper/1604.04876/) (2016)
- [Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets](https://mlsanity.com/paper/1903.06696/) (2019)
- [Approximately Efficient Two-Sided Combinatorial Auctions](https://mlsanity.com/paper/1611.05342/) (2016)
- [The Best of Both Worlds: Asymptotically Efficient Mechanisms with a Guarantee on the Expected Gains-From-Trade](https://mlsanity.com/paper/1802.08023/) (2018)
- [On the Optimal Fixed-Price Mechanism in Bilateral Trade](https://mlsanity.com/paper/2301.05167/) (2023)

## Built on by (most cited first, 5 of 5)

- [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024)
- [Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12903/) (2026)
- [The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms](https://mlsanity.com/paper/2602.10868/) (2026)
- [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026)
- [Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs](https://mlsanity.com/paper/2607.20258/) (2026)

## Abstract (arXiv)

We study the problem of designing a two-sided market (double auction) to maximize the gains from trade (social welfare) under the constraints of (dominant-strategy) incentive compatibility and budget-balance. Our goal is to do so for an unknown distribution from which we are given a polynomial number of samples. Our first result is a general impossibility for the case of correlated distributions of values even between just one seller and two buyers, in contrast to the case of one seller and one buyer (bilateral trade) where this is possible. Our second result is an efficient learning algorithm for one seller and two buyers in the case of independent distributions which is based on a novel algorithm for computing optimal mechanisms for finitely supported and explicitly given independent distributions. Both results rely heavily on characterizations of (dominant-strategy) incentive compatible mechanisms that are strongly budget-balanced.