Matching markets achieve most trade gains with simple rules
From Bilateral Trade to Matching Markets: Sharp Gains from Trade
Computer Science and Game Theory
Summary
This paper explores how much benefit can be gained from trading things when many buyers and sellers match up, each with their own private values. The authors find exact limits on how efficient trade can be under certain fairness and incentive constraints, even when there are many types of buyers and sellers. Their results expand known insights from simple one-on-one trades to complex markets where multiple matches happen. They measure precisely how close practical trade outcomes come to the best possible trade outcomes.
What this means in practice
- •For market designers: Design incentive-compatible matching mechanisms that guarantee at least about 72% of the best possible trade gains under realistic constraints.
- •For online platform engineers: Build matching algorithms for marketplaces that ensure fair trade without expected budget loss, informed by precise efficiency bounds from this theory.
A theory result. No direct application yet.
Authors
Zhengyang Liu, Ying Qin, Zihe Wang
Abstract
We study gains from trade in matching markets with independent private values and costs, Bayesian incentive compatibility, interim individual rationality, and no expected budget deficit. A second-best guarantee for finite bilateral trade extends without loss to matching markets with independent Borel priors, arbitrary downward-closed feasibility, and finite expected first-best gains. For bounded buyers with monotone hazard rates and arbitrary bounded sellers, we determine the exact worst-case ratio of second-best to first-best gains, approximately $0.72490721$. For binary buyers and sellers with at most $m$ types, we determine the exact ratio for every $m$, including $8/9$ when $m=2$ and a limit of $4/5$ as $m$ grows. Both families of bounds are tight already in bilateral trade.