PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.27304v2cs.GT

TL;DR

Gains-from-trade maximization in two-sided markets must reconcile incentive compatibility, individual rationality, and budget balance, while prior work left open how many sellers on the scarce side suffice. The paper analyzes the surplus difference using rank-by-rank threshold integrals and proves that two additional sellers suffice when m ≥ n and buyers’ distribution first-order stochastically dominates sellers’.

  • Problem

    How many sellers must be recruited on the scarce side to match first-best GFT remained open after prior work required at least 20,000 recruits on both sides.

    Source: §1 · p. 2

  • Method

    The proof decomposes STR(m, n + 2) − OPT(m, n) into rank-by-rank threshold integrals, reducing the result to checking each integral’s non-negativity.

    Source: §3 · p. 8

  • Results

    Two additional sellers let Seller Trade Reduction achieve expected GFT at least the first-best GFT when m ≥ n and buyers’ distribution first-order stochastically dominates sellers’.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    The result resolves the scarce-side recruitment question for markets with m ≥ n under first-order stochastic dominance.

    Source: §1 · p. 2, §1.1 · p. 2

    The model assumes i.i.d. buyer values and seller costs drawn from distributions on R, without continuity or support restrictions.

    Source: §2 · p. 6

Abstract

from arXiv · show

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.

1 Introduction

Two-sided trade seeks first-best gains from trade under incentive, individual-rationality, and budget-balance constraints, yet optimal mechanisms depend on distributions. This section presents an exact scarce-side recruitment guarantee, its proof approach, and the boundary showing that one fewer recruit cannot suffice.

1 Introduction

  • Two-sided markets cannot generally attain full efficiency while satisfying incentive compatibility, individual rationality, and weak budget balance; optimal expected GFT depends on the distributions.Prior work left open how many additional scarce-side traders suffice.Source: §1 · pp. 1–2

1.1 Our Results

  • With m≥n and F_B ⪰FSD F_S, two additional sellers let STR attain at least OPT(m,n); the symmetric smaller-buyer case uses two buyers.The mechanism is prior-independent, and the guarantee matches or exceeds the first-best GFT of the original market.Source: §1.1 · pp. 2–3
  • One additional seller is insufficient already for m=n=1 for any prior-free DSIC, IR, and WBB mechanism, including randomized mechanisms.The impossibility applies beyond anonymous deterministic mechanisms.Source: §1.1 · p. 3

1.2 Proof Overview

  • The proof replaces global trade-size events and quantile buckets with rank-by-rank threshold integrals that separate recruitment gains from trade-reduction losses.The decomposition reduces the comparison to checking a threshold integral for each price threshold.Source: §1.2 · pp. 3–4

1.3 Related Work

  • The guarantee achieves the original market’s first-best GFT with a prior-independent mechanism, unlike multiplicative approximations or methods relying on prior knowledge.STR is defined without reference to the buyer or seller distributions.Source: §1.3 · pp. 5–6

2 Model and Preliminaries

The model pairs i.i.d. buyers and sellers in a two-sided market, where the goal is efficient trade subject to incentive and budget constraints. It defines the first-best GFT benchmark and Seller Trade Reduction (STR), a prior-independent mechanism.

2 Model and Preliminaries

  • Buyers’ values and sellers’ costs are drawn i.i.d. from distributions F_B and F_S, with n denoting the number of sellers in the original market.The model allows arbitrary distributions without continuity or support assumptions.Source: §2 · p. 6

2.1 Mechanisms and Incentives

  • A mechanism specifies allocation and payments, and DSIC, IR, and WBB require truthful reporting, non-negative truthful utility, and no ex-post deficit.Prior independence means the allocation and payment rules do not depend on F_B or F_S.Source: §2.1 · p. 7
  • First-best GFT is the benchmark for the efficient trade size in a market with m buyers and n sellers.The supplied passages denote its expectation by OPT(m, n).Source: §2.1 · p. 7
  • STR computes the efficient trade size and either trades the top-ranked pairs or reduces trade by one pair, and it is DSIC, IR, WBB, and prior-independent.The unreduced case trades when the marginal buyer bid meets the next seller cost; otherwise, the top r′ − 1 pairs trade.Source: §2.1 · p. 7

3 Decomposing Expected Gains From Trade

The section rewrites the expected GFT difference between STR with two recruited sellers and the original market as rank-by-rank threshold integrals. This decomposition separates recruitment gains from trade-reduction losses and reduces the proof to non-negativity at each threshold.

3 Decomposing Expected Gains From Trade

  • The proof reduces STR(m, n + 2) − OPT(m, n) to checking that a threshold integral I_i(x) is non-negative for every rank and threshold.This separates the recruitment gain from the trade-reduction loss.Source: §3 · p. 8
  • STR’s ex-post representation sums non-negative rank-indexed terms when m ≥ n and k ≥ n + 1.The representation lets the expected surplus difference be analyzed term by term.Source: §3 · p. 8
  • At a fixed threshold, the seller-event decomposition expresses the comparison as a gain minus a loss when the buyer’s rank-i value is at least that threshold.The section evaluates the seller-side recruitment gain for k = n + 2 through a binomial event calculation.Source: §3 · p. 9
  • The expected-GFT identity follows by taking expectations of the ex-post representation and integrating the threshold contributions.The proof uses non-negative integrands and finite OPT(m, n) to justify exchanging expectation and integration.Source: §3 · p. 9

4 Warm-Up: Complete Proof for Symmetric Continuous Markets

In the symmetric continuous case, the proof moves to quantile space and establishes non-negativity of each threshold integral. The resulting bound is STR(n, n + 2) ≥ OPT(n, n), and the truncated-integral argument prepares for the general case.

4 Warm-Up: Complete Proof for Symmetric Continuous Markets

  • For continuous F with m = n, buyer order statistics map to uniform quantiles, whose complements follow Beta(i, n − i + 1) distributions.The quantile representation turns the threshold integral into an integral over an order-statistic density.Source: §4 · p. 10

4.1 Proof of Lemma 4.2

  • The proof extends the threshold integrand by truncating w to min(1 − p, w), then proves the truncated integral is non-negative for any upper limit r.This broader inequality is used to establish non-negativity of the threshold integrals in the symmetric case.Source: §4 · pp. 10–11

4 Warm-Up: Complete Proof for Symmetric Continuous Markets

  • STR(n, n + 2) ≥ OPT(n, n) in symmetric continuous markets, establishing the two-additional-seller guarantee in this warm-up setting.The proof establishes non-negativity for every threshold and rank, then integrates and sums those contributions.Source: §4 · p. 11

4.1.1 Proof of Lemma 4.3

  • The proof of the full-interval bound averages two upper bounds on E[min(z, W)^d], using positive weights that sum to one.The bounds are z^d and E[W]z^(d−1), with W distributed as Beta(i, n − i + 1).Source: §4.1.1 · pp. 11–12

5 Generalization to FB ⪰FSD FS and m ≥n

The section extends the threshold-integral argument to arbitrary distributions with F_B first-order stochastically dominating F_S and market sizes m ≥ n. It proves the threshold lower bound and truncated-integral non-negativity needed for the main guarantee.

5.1 Proof of Lemma 5.1

  • Under F_B ⪰FSD F_S, the threshold integral is lower-bounded in terms of a truncated integrand and a Beta(i, m − i + 1) density.The bound applies to every rank i and threshold x when m ≥ n ≥ 1.Source: §5 · p. 12

5 Generalization to F_B ⪰FSD F_S and m ≥ n

  • STR(m, n + 2) ≥ OPT(m, n) for arbitrary distributions with F_B ⪰FSD F_S and m ≥ n.The theorem follows by combining the threshold-integral representation with the two lemmas established in this section.Source: §5 · p. 13

5.1 Proof of Lemma 5.1

  • The buyer quantile coupling handles arbitrary CDFs, including distributions with jumps or flat regions.The proof uses the generalized inverse CDF and uniform order statistics.Source: §5.1 · p. 13

5.2 Proof of Lemma 5.2

  • For m ≥ n, the symmetrized integrand’s two factors have the same sign, establishing non-negativity of the truncated integral.The proof uses monotonicity of the truncated integrand and the density relation between f_i,m and f_i,n.Source: §5.2 · p. 14

6 Tightness: Impossibility of Recruiting One Seller

The section proves that recruiting one additional seller cannot match first-best GFT in bilateral trade for any prior-free DSIC, IR, and WBB mechanism, deterministic or randomized. Its argument extends an earlier lower-bound construction using seller symmetry, a two-point seller distribution, and a continuous component in buyer values.

6 Tightness: Impossibility of Recruiting One Seller

  • Matching first-best GFT throughout the distribution family would force trade probability above 1 on some mixed profiles, a contradiction.For p = 0.8, the derived lower bound is 1.5, although q(c) is a probability in [0, 1].Source: §6 · pp. 15, 18
  • With one buyer and two sellers, every prior-free DSIC, IR, and WBB mechanism fails to match first-best GFT for some F_B ⪰FSD F_S, even if randomized.The distributions can have OPT(1, 1) > 0.Source: §6 · p. 15
  • Symmetrizing over seller identities preserves DSIC, IR, WBB, and expected GFT because sellers are i.i.d.The proof can therefore assume the mechanism treats the two sellers symmetrically.Source: §6 · pp. 15–16
  • Under IR and WBB, the agents’ summed utilities cannot exceed realized GFT, providing an upper bound used in the mechanism analysis.The proof bounds expected surplus using the probability that the low-cost seller trades on a mixed-cost profile.Source: §6 · pp. 16–17
  • The hard-instance family uses seller costs c and 1, while buyer values mix a point mass at 1 with a uniform distribution on [c, 1].This continuous buyer component extends the earlier construction to randomized and potentially non-anonymous mechanisms.Source: §6 · pp. 15–16

7 Conclusion

The conclusion establishes the exact competition complexity of recruiting on the scarce side: two additional traders suffice, and one additional seller does not suffice even in bilateral trade. It also contrasts scarce-side recruitment with the abundant-side lower bound and notes that the paper resolves earlier open questions.

7 Conclusion

  • For m ≥ n and F_B ⪰FSD F_S, two additional sellers suffice uniformly, while one additional seller fails already for m = n = 1.The one-seller impossibility applies to prior-free DSIC, IR, and WBB mechanisms, deterministic or randomized.Source: §7 · p. 19
  • These bounds resolve open questions posed by Babaioff et al. [3, Section 4.3] and Cai et al. [16, Section 5].Source: §7 · p. 19
  • The conclusion contrasts two scarce-side recruits with the Ω(log m) abundant-side lower bound, emphasizing that the recruited side matters more than the number recruited.Source: §7 · p. 19

Related papers

Loading 2609.27304v2…