# Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2017.

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

- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [An Online Learning Theory of Brokerage](https://mlsanity.com/paper/2310.12107/) (2023)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)
- [A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage](https://mlsanity.com/paper/2503.02646/) (2025)
- [Nonparametric Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12904/) (2026)
- [A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search](https://mlsanity.com/paper/2603.08679/) (2026)
- [Trading Volume Maximization with Online Learning](https://mlsanity.com/paper/2405.13102/) (2024)
- [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026)

## Abstract (arXiv)

We design simple mechanisms to approximate the Gains from Trade (GFT) in two-sided markets with multiple unit-supply sellers and multiple unit-demand buyers. A classical impossibility result by Myerson and Satterthwaite showed that even with only one seller and one buyer, no Individually Rational (IR), Bayesian Incentive Compatible (BIC) and Budget-Balanced (BB) mechanism can achieve full GFT (trade whenever buyer's value is higher than the seller's cost). On the other hand, they proposed the "second-best" mechanism that maximizes the GFT subject to IR, BIC and BB constraints, which is unfortunately rather complex for even the single-seller single-buyer case. Our mechanism is simple, IR, BIC and BB, and achieves frac12 of the optimal GFT among all IR, BIC and BB mechanisms. Our result holds for arbitrary distributions of the buyers' and sellers' values and can accommodate any downward-closed feasibility constraints over the allocations. The analysis of our mechanism is facilitated by extending the Cai-Weinberg-Devanur duality framework to two-sided markets.