Simple trading mechanisms achieve optimal gains in matching markets
The Power of Simple Mechanisms: A Tight $e$-Approximation for Gains from Trade in Matching Markets
Computer Science and Game Theory
Summary
This paper looks at how well simple methods can do when matching buyers and sellers in markets to maximize gains from trade. The authors focus on a mechanism that randomly mixes two ways of offering trades and prove it gets very close to the best possible outcome—specifically, within a factor of e (about 2.718). They improve previous results that had weaker guarantees. Their analysis uses math to carefully compare ideal trade outcomes with what these simple methods can reliably achieve. They also show that their result is the best possible under reasonable conditions.
What this means in practice
- •For market designers: Design simple posted-price mechanisms for two-sided markets that guarantee near-optimal gains from trade.
- •For e-commerce platform teams: Implement efficient trade matching rules that balance buyer values and seller costs with provable performance bounds.
A theory result. No direct application yet.
Authors
Xiaohui Bei, Wenhao Wu, Shengwei Zhou
Abstract
We study how well simple mechanisms approximate gains from trade (GFT) in two-sided matching markets with independent buyer values and seller costs, where feasible outcomes form an arbitrary downward-closed family of matchings. This model includes bilateral trade and double auctions as special cases. We focus on the Generalized Random-Offerer (GRO) mechanism, which is an equal mixture of the Generalized Sellers-Offering Mechanism (GSOM) and the Generalized Buyers-Offering Mechanism (GBOM). We determine GRO's exact worst-case approximation ratio with respect to first-best GFT, showing that it is $e$. This improves the previous $3.15$ approximation guarantee (Babaioff et al. STOC 2026) for the same mechanism. In bilateral trade, the result implies a $1/e$ guarantee for the random-offerer mechanism, improving the previous $1/π$ bound (Jo 2026). Our analysis uses a two-dimensional inequality in quantile space to compare first-best GFT with optimal one-sided auction profits. For each potential trade, we identify the region of buyer values and seller costs for which the first-best allocation selects that trade, and then randomly shrink this region in quantile space, yielding posted-price rules whose expected profits can be evaluated exactly. We establish tightness of the $e$ approximation by constructing markets with regular type distributions, pairwise disjoint trading edges, and a single knapsack constraint. On these instances, GRO's expected GFT approaches a $1/e$ fraction of first-best GFT, therefore ruling out any better guarantee even under these restrictions.