The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets

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{⪰}_{\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; symmetrically, when $m\le n$, Buyer Trade Reduction suffices with two additional buyers. This resolves open questions of Babaioff, Goldner, and Gonczarowski (SODA 2020) and Cai, Liaw, Mehta, and Zhao (STOC 2024). Moreover, this uniform bound is optimal: already for $m=n=1$, no prior-independent mechanism (deterministic or randomized) that is dominant-strategy incentive-compatible (DSIC), individually rational (IR), and weakly budget-balanced (WBB) matches the first-best GFT with one additional seller. We further extend our characterization to $r$-dominance ($F_B{⪰}_r{F}_S$), where $r\in (0,1]$ and $1-F_B(x)\ge r(1-F_S(x))$ for all $x\in \mathbb{R}$ (recovering $F_B{⪰}_{\mathrm{FSD}}{F}_S$ at $r=1$). When $m\ge n\ge 1$, $c=\lceil 1/r\rceil +1$ additional sellers suffice for STR to match or exceed the first-best GFT, while every prior-independent DSIC, IR, and WBB mechanism requires at least $\max (2,\lceil 1/r\rceil -1)$ additional sellers even for $m=n=1$, pinning down the optimal bound to within two traders. Finally, this $\Theta (1/r)$ bound cannot be asymptotically improved even by recruiting on both sides: for $r<1/64$ and $m=n=\lceil 2/(5r)\rceil$, every prior-independent DSIC, IR, and WBB mechanism requires $c\ge \lceil 1/(64r)\rceil =\Omega (1/r)$ additional traders per side.