Two more sellers or buyers enable optimal trade in two-sided markets
The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
Computer Science and Game Theory
Summary
This paper studies trading between buyers and sellers, where each side has many participants with different values for goods. The researchers show that by adding just two extra participants on the smaller side, simple trading methods can achieve the best possible total gains from trade without knowing exact details about buyers or sellers. They also prove that adding only one extra participant is not enough to reach this optimal outcome. This answers previously open questions about how many extra participants are needed for effective trading mechanisms.
What this means in practice
- •For market designers: Improve mechanisms for marketplaces by adding precisely two extra participants on the smaller side to achieve optimal trading efficiency without detailed distribution knowledge.
- •For online auction platforms: Design double auction systems that guarantee optimal trade outcomes by recruiting two additional sellers or buyers when one side is smaller, ensuring robust performance.
A theory result. No direct application yet.
Authors
Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Di Wang, Mingfei Zhao
Abstract
We study Bulow-Klemperer-style competition complexity in two-sided double auctions with $m$ unit-demand buyers drawn i.i.d. from $F_B$ and $n$ unit-supply sellers drawn i.i.d. from $F_S$. When $m \ge n$ and buyer valuations first-order stochastically dominate seller costs ($F_B \succeq_{\mathrm{FSD}} F_S$), we prove that recruiting just two additional sellers enables Seller Trade Reduction (STR), a prior-independent mechanism, to achieve expected Gains From Trade (GFT) at least the first-best GFT of the original market. When the buyer side is the smaller side of the market ($m \le n$), an analogous result holds for Buyer Trade Reduction with 2 additional buyers. This resolves open questions of Babaioff, Goldner, and Gonczarowski (SODA 2020) and Cai, Liaw, Mehta, and Zhao (STOC 2024). We complement our upper bound by showing that this uniform bound is optimal: already for $m = n = 1$, no prior-free mechanism (deterministic or randomized) that is dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced can match the first-best GFT by recruiting only one additional seller.