Matching markets keep half their best gains despite constraints
Second-Best Gains from Trade in Matching Markets
Computer Science and Game Theory
Summary
In markets where buyers and sellers are matched based on their preferences and limitations, it’s often impossible to achieve the absolute best trade efficiency due to practical rules. The authors show that even under these tough conditions, you can still capture at least half of the best possible gains from trade. This finding applies not just to simple one-to-one trades but also to more complex markets with many participants and restrictions. They use mathematical tools to prove this important efficiency guarantee.
What this means in practice
- •For market designers: Design trade mechanisms that guarantee at least half of optimal efficiency under practical constraints in complex matching markets.
- •For online trading platforms: Ensure platform matching algorithms maintain strong budget balance while capturing significant trade gains across multiple buyers and sellers.
A theory result. No direct application yet.
Authors
Xiaohui Bei, Bo Li, Wenhao Wu, Shengwei Zhou
Abstract
We study gains from trade (GFT) in two-sided matching markets with independent private types and arbitrary downward-closed feasibility constraints. The second-best benchmark is the maximum expected GFT achievable by a Bayesian incentive compatible, interim individually rational mechanism that is strongly budget balanced at every report profile. These constraints generally preclude attaining the first-best GFT and raise the question of how much efficiency must be lost. We prove that the second-best GFT is at least one half of the first-best GFT in every such matching market. This recovers and generalizes the recent $1/2$ guarantee for bilateral trade by Liu et al. (2026) to markets with multiple buyers and sellers and arbitrary downward-closed feasibility constraints. Together with their matching lower bound for bilateral trade, our result establishes a tight worst-case ratio of $1/2$ for this general class of matching markets. Our proof builds on the virtual-GFT framework of Brüstle et al. (EC 2017) to reduce the problem to a one-parameter Lagrangian. The main step is a geometric, edge-by-edge analysis based on first-best edge-selection regions, combined with a randomized contraction in rank space.