← 研踪 PaperTrailarXiv:2609.27304 · v3
The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
首次提交 2026-09-23 11:37
版本更新 2026-11-03 15:13
雷达观测 2026-11-04 23:40
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-03 15:13 · 最新观测版本
The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
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.
查看此版本解读 →查看此版本原文 ↗