OpenAlex ·

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

Yang Cai, Vineet Gupta, Yanchen Jiang, Chris Liaw, Aranyak Mehta, Grigoris Velegkas, Di Wang and Mingfei Zhao

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2609.27304
Original
Read it at the publisher
Topics
Computational ComplexityEconometricsGeneral EconomicsOptimization & Control

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; 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 \succeq_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 \succeq_{\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 $Θ(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 = Ω(1/r)$ additional traders per side.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Computational Complexity

Get the few papers worth your time in Computational Complexity every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics