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

arXiv:2609.27304 · cs.GT · Submitted 2026-09-23 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "The Power of Recruiting the Smaller Side".

Jane: Here's the gist of the paper. We study Bulow-Klemperer-style competition complexity in two-sided double auctions with m unit-demand buyers drawn i.i.d.

Tom: from FB and n unit-supply sellers drawn i.i.d.

Jane: from FS, and prove that recruiting just two additional sellers enables Seller Trade Reduction (STR), a priorindependent mechanism, to achieve expected Gains From Trade (GFT) at least the first-best GFT of the original market.

Tom: This result resolves open questions regarding the optimal number of recruits needed for achieving first-best gains in two-sided markets.

Title and authors: Tom: So we're looking at this paper titled "The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets". It's about how many extra sellers you need to get a fair deal in these kinds of double auctions.

Jane: Exactly. It tackles the Bulow-Klemperer style complexity, which is basically figuring out how hard it is to set up an auction when you have buyers and sellers on both sides, and this paper suggests we don't need a huge number of recruits to get close to the best possible outcome.

Lu: The authors are Cai, Gupta, Jiang, Liaw, Mehta, Velegkas, Wang and Zhao. They are digging into prior-independent mechanisms like Seller Trade Reduction or Buyer Trade Reduction which try to find optimal trade sizes without knowing the buyers' or sellers' preferences beforehand.

Meng: So what’s the core idea here? Because in these markets, if one side is much smaller than the other, they might need a lot of partners to make things work fairly. This paper claims you only need two extra participants on the smaller side to match the best possible gains from trade.

Tom: That sounds like a big deal because it’s about making mechanisms that work well without knowing all those preferences upfront. They say when the buyer side is smaller, meaning there are more sellers, if you add just two more sellers, you can get expected gains from trade that are at least as good as the first-best possible gains from trade in the original market.

Jane: That’s a really concrete result because it directly addresses a question about how many people you need to recruit to achieve optimality in these setups. It resolves some of those open questions about what's optimal for two-sided markets.

Lu: The paper goes into the technical details by showing that this bound is uniform, meaning it works no matter how large m or n are, as long as the buyer valuations first-order stochastically dominate the seller costs.

Meng: Wait, so if the buyer side is smaller—meaning you have more sellers—and those buyers' valuations are stochastically better than what sellers actually charge, adding just two sellers helps achieve that optimal gain from trade level. That sounds like a practical finding for designing systems.

Tom: It does. And it’s not just theoretical; they show this bound of two is actually the best possible one you can get in this setting. They prove that adding only one more seller isn't enough, even when the number of buyers and sellers are equal, m equals n equals one.

Jane: That part is crucial because it means we don't need to recruit a large constant number of traders on both sides anymore to get close to first-best performance in bilateral trade.

Title and authors: Lu: The proof uses a decomposition into threshold integrals, which basically breaks the problem down into checking if some integral is positive for every possible price threshold. They show this integral is always non-negative by proving a lemma about the truncated integrand being non-negative over a certain range of integration.

Meng: It sounds like they are using this integral check to prove that adding two sellers definitely helps achieve the first-best gains from trade, even when we generalize to different distributions for the buyers and sellers.

Tom: Right, and they extend this beyond just symmetric cases where the buyer distribution is identical—they show it works even if the buyers' distribution is only first-order stochastically dominant over the sellers' costs. That’s a nice generalization for real-world data where things aren't perfectly symmetric.

Jane: And they also establish a lower bound in the case where there are only one buyer and two sellers, showing that Gains From Trade for that specific setup is actually less than the first-best Gains From Trade if the distributions are set up a certain way.

Lu: That lower bound helps prove the tightness of this result by showing that even with just two traders, you can’t always guarantee matching the first-best gains under all possible distribution scenarios.

Meng: So, if I’m building a system and I know my buyer distribution will be better than the seller costs, adding just two sellers gives me a solid guarantee on performance relative to what I could get without them. That makes sense for deployment constraints where recruitment is limited.

Tom: It does make sense for deploying mechanisms that are prior-independent because you can control that small number of recruits and still hit a strong performance target based on the market imbalance.

Jane: So to wrap up this paper "The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets", it boils down to this: if one side is smaller, adding just two traders is enough for Seller Trade Reduction or Buyer Trade Reduction to hit expected gains from trade that are at least the first-best level.

Lu: And they’ve shown this bound of two is tight, meaning you can't get away with just one more trader in the bilateral case. This shows that which side you recruit on is actually more important than just the quantity of traders added.

Meng: From my standpoint on deployment, this means we can simplify our recruitment strategy for achieving strong outcomes in these markets; focusing on adding two sellers when there are more sellers seems like a solid rule of thumb for meeting performance targets.

Tom: It’s a solid finding because it moves us away from needing massive numbers of recruits to get near optimal results, which simplifies the design process significantly. We'll see what this means for other complex matching problems next.

The paper's summary: Tom: So, to wrap up this section, we’re talking about how adding just two extra sellers—or buyers, depending on who is smaller—can get a mechanism running at first-best performance in these double auctions.

Jane: Right. It means that if you’re designing a system for a two-sided market and one side is smaller than the other, you don't need to recruit a huge number of partners to get close to the best possible expected gain from trade.

Lu: The core idea is that recruiting just two additional traders enables Seller Trade Reduction or Buyer Trade Reduction to hit those first-best gains, which is what the original market would achieve on its own.

Meng: So, for someone who’s actually building a system, it simplifies things because you don't have to worry about recruiting hundreds of people just to get decent results in a constrained environment.

Tom: Exactly. And they didn't just say two is enough; they proved that one extra trader isn't enough when the market is perfectly balanced, like when there are equal buyers and sellers, one trader doesn't work for any mechanism tested there.

Jane: That’s a strong point because it shows that which side you choose to recruit on matters more than just how many traders you add in total.

Lu: The proof itself uses a clever trick, breaking the difference between the actual outcome and the optimal outcome into something called threshold integrals. They show that for every possible price level, these integrals are non-negative, which proves that adding those two traders always pushes you toward better results.

Tom: It’s not just about a nice theoretical bound; they extend this to situations where the buyer preferences aren't perfectly matched to the seller costs, as long as they follow a certain order called first-order stochastic dominance.

Jane: That generalization is important because it shows this isn't just for perfectly symmetrical cases; it’s robust enough for real-world data where things are usually messy.

Lu: And they even show a lower bound in the case of one buyer and two sellers, proving that even there, if you have certain distribution patterns, you still can't beat first-best gains with just those two traders.

Meng: So, it’s a very specific result about sufficiency—two is the magic number—but they also give us limits on how good that performance can actually get under different conditions.

Tom: It’s a lot of numbers and analysis, but the main point for us here is that we can significantly simplify our recruitment strategy when we know which side has fewer participants.

Jane: And it opens up a new direction for designing these trade mechanisms because we now have a concrete, small number to test against.

Lu: But there’s still room to explore what happens if you try to recruit more than two traders on the smaller side, or if you want to understand exactly how much better the performance gets when you go beyond that limit.

The paper's improvements: Tom: So, we’re looking at how this paper suggests improving the original idea—the one that says two extra traders are enough—and what else they found by pushing things a bit further.

Jane: The main improvement is showing that this small number of recruits actually works even when the buyer preferences aren't perfectly matched to the seller costs, as long as those preferences follow a specific order we call first-order stochastic dominance.

Lu: They also made sure to prove that this result holds across different types of mechanisms—deterministic ones, randomized ones, whatever—when there’s a perfect balance between buyers and sellers, when the number of participants is one on each side.

Meng: That means if you’re building something that relies on a specific mechanism, like Seller Trade Reduction or Buyer Trade Reduction, you don't have to worry about the underlying mathematical structure being too complex for this two-trader bound to apply.

Tom: And they did address the tightness of the bound by proving that one additional trader simply isn't enough in that perfectly balanced one-on-one market case, which is a pretty important clarification for how we think about these designs.

Jane: It’s a refinement of the original finding because it sets a clear limit on what you can expect to achieve with just one extra person, even in the simplest setup.

Lu: The analysis also establishes that this two-trader bound is uniform across all market sizes m and n, as long as that buyer distribution condition holds, which means the result isn't just a fluke for small markets.

Tom: That uniformity is what makes it useful for real-world scenarios because we don't have to re-calculate everything every time the market size changes; the bound stays consistent.

Jane: What this changes for us is that we can now confidently design systems knowing that if one side is smaller, two recruits give us a guaranteed performance boost compared to what we’d get without them.

Lu: And they also gave a lower bound in the case of one buyer and two sellers, which adds another layer of caution when applying this to specific market sizes.

Meng: So, it’s not just one number; it’s a set of constraints—the two-trader limit for small sides and the failure point for one trader in balanced markets—that helps us deploy these ideas safely.

Tom: Exactly. It moves the conversation from just "what's enough" to "what's necessary and what's impossible," which is how you build reliable production models.

Jane: And this whole set of findings points toward a clearer picture of optimal recruitment strategies for achieving fair trade in these kinds of complex systems, so next time we look at the implications for designing AI agents that interact with markets...

Conclusion: Tom: So, to wrap up this whole discussion on "The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets", the main takeaway is that you don't need a huge number of recruits to get close to optimal performance if you know which side is smaller.

Jane: Right. It boils down to this paper showing that recruiting just two additional sellers or buyers is enough for Seller Trade Reduction or Buyer Trade Reduction mechanisms to hit expected gains from trade at least as good as the first-best level, provided the buyer side is smaller and valuations follow a specific dominance order.

Lu: That’s the main theorem—that uniform bound of two traders is sufficient under those conditions.

Meng: From my deployment view, it means we can significantly simplify our recruitment strategy when we know one side has fewer participants; focusing on adding two sellers seems like a solid rule of thumb for meeting performance targets without needing massive scale.

Tom: It's not just about the quantity; they proved that one extra trader isn't enough even in the simplest, perfectly balanced case where there are equal buyers and sellers, which is a pretty tight result.

Jane: That tightness is important because it shows that which side you recruit on matters more than just how many traders you add in total for those mechanisms.

Lalam: I’m confident this result holds strongly because the proof uses a decomposition into threshold integrals and shows they are always non-negative under the specified conditions.

Lu: The analysis also extends this to arbitrary distributions, so it works even when things aren't perfectly symmetrical, as long as that buyer distribution condition is met.

Meng: That generalization is what makes it useful for real-world data where things are usually messy; you don't need perfect symmetry to get a strong performance guarantee.

Tom: It’s a very clean result in terms of the mechanics—we’re talking about two units adding enough value to bridge the gap between what we can achieve and what's optimal.

Jane: And it opens up a new direction for designing these trade mechanisms because we now have a concrete, small number to test against when planning for market recruitment.

Lalam: I’m sure this finding will be cited often because it resolves that open question about how many recruits are truly needed for first-best gains in two-sided markets.

Tom: Exactly. So, that's the wrap on "The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets".

Jane: Next up, we’re looking at how this kind of recruitment logic might apply to designing AI agents that interact with complex markets...

Google Research

cs.GT

Submitted: 2026-09-23

Updated: 2026-11-03

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

Importance score: 100/100

The gist: We study Bulow-Klemperer-style competition complexity in two-sided double auctions with m unit-demand buyers drawn i.i.d.

Key concepts

Seller Trade Reduction (STR)
STR is a priorindependent mechanism used in trade settings. The paper analyzes how this specific mechanism performs when the number of sellers changes. It aims to show that adding a small, fixed number of sellers can improve the expected gains from trade compared to the original market setup.
Gains From Trade (GFT)
GFT measures the economic benefit or surplus generated by a trade or mechanism compared to an optimal scenario. The goal of the research is to prove that recruiting two extra sellers allows STR to achieve GFT values that are at least as good as what is possible in the original market.
First-Best GFT
This represents the highest possible expected gains from trade achievable in a market with no constraints or prior knowledge about the participants. The paper demonstrates that recruiting two additional sellers enables STR to reach at least this ideal, first-best level of efficiency.

Terminology

Summary

We study Bulow-Klemperer-style competition complexity in two-sided double auctions with m unit-demand buyers drawn i. p. 0

Where the paper says it

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 Google Research {caiy, vineet, yanchenjiang, cvliaw, aranyak, gvelegkas, wadi, mingfei}@google. com Abstract We study Bulow-Klemperer-style competition complexity in two-sided double auctions with m unit-demand buyers drawn i.

i.d. from FB and n unit-supply sellers drawn i. p. 0
Where the paper says it

com Abstract We study Bulow-Klemperer-style competition complexity in two-sided double auctions with m unit-demand buyers drawn i. from FB and n unit-supply sellers drawn i.

i.d. from FS, and prove that recruiting just two additional sellers enables Seller Trade Reduction (STR), a priorindependent mechanism, to achieve expected Gains From Trade (GFT) at least the first-best GFT of the original market. p. 0
Where the paper says it

from FB and n unit-supply sellers drawn i. When m ≥ n and buyer valuations first-order stochastically dominate seller costs (FB ⪰FSD FS), we prove that recruiting just two additional sellers enables Seller Trade Reduction (STR), a priorindependent mechanism, to achieve expected Gains From Trade (GFT) at least the first-best GFT of the original market.

This result resolves open questions regarding the optimal number of recruits needed for achieving first-best gains in two-sided markets. p. 4
Where the paper says it

3] about the optimal number of recruits one needs for m = n = 1 (they showed the answer is in {2, 3, 4}) and the question in [16, Section 5] of what is achievable by augmenting only the scarce side. Approximating Gains From Trade and Welfare in Two-Sided Markets.

Key Findings on Recruitment Sufficiency

The main theorem establishes that when the buyer side is the smaller side of the market (m ≥ n), recruiting just two additional sellers enables Seller Trade Reduction to achieve expected Gains From Trade at least the first-best optimal GFT of the original (m, n) market. This finding is symmetric for the buyer side when n ≥ m, proving that recruiting two additional buyers enables Buyer Trade Reduction to match or exceed the first-best GFT. p. 2

Where the paper says it

1]), Theorem 1. 1 symmetrically implies that when n ≥ m and FB ⪰FSD FS, recruiting two additional buyers enables Buyer Trade Reduction to match the first-best GFT.

Furthermore, this result significantly strengthens previous findings by showing that recruiting only two additional sellers is sufficient to match or exceed the first-best GFT in bilateral trade (m = n = 1). p. 2
Where the paper says it

In particular, Theorem 1. 1 significantly strengthens the two-sided recruitment guarantee of [16], which recruits a large constant number of traders on both sides, to recruiting only two additional sellers and no additional buyers, and resolves the bilateral trade (m = n = 1) open problem of [3, Section 4.

Establishing Optimality and Bounds

The paper complements the main result by demonstrating that this uniform bound of two additional traders cannot be improved, showing that one additional seller does not suffice even in bilateral trade. This impossibility result is extended to hold for every prior-free DSIC, IR, and WBB mechanism—deterministic or randomized—when m = n = 1. p. 2

Where the paper says it

3] had already proved that recruiting 1 additional trader fails for anonymous, deterministic prior-independent mechanisms when m = n = 1. Building on the structure of their hard instance, we extend this impossibility result to hold for every prior-free DSIC, IR, and WBB mechanism—deterministic or randomized.

The analysis contrasts the new result with previous bounds that required recruiting a large constant number of traders on both sides of the market. p. 1
Where the paper says it

They proved that under FB ⪰FSD FS and m ≥ n, recruiting a constant number of traders c = O(1) on both sides of the market enables the GFT from STR to achieve expected GFT at least the first-best GFT. However, the constant appearing in their analysis is at least 20,000.

Decomposition into Threshold Integrals

The proof relies on decomposing the expected surplus difference STR(m, n + 2) − OPT(m, n) into a sum of rank-by-rank threshold integrals. This decomposition reduces the problem to checking the non-negativity of a single threshold integral Ii(x) for each price threshold x. p. 7

Where the paper says it

The following lemma is the main takeaway of this section: it shows that proving Theorem 1. 1 reduces to checking the non-negativity of a single threshold integral Ii(x) for each price threshold x ∈ R, which cleanly separates the recruitment gain from the trade-reduction loss.

The analysis then proceeds by showing that this integral is non-negative by proving Lemma 4. p. 7
Where the paper says it

The following lemma is the main takeaway of this section: it shows that proving Theorem 1. 1 reduces to checking the non-negativity of a single threshold integral Ii(x) for each price threshold x ∈ R, which cleanly separates the recruitment gain from the trade-reduction loss.

2, which involves showing the truncated integrand is non-negative over a range of integration. p. 9
Where the paper says it

1) with min(1 − p, w) and allowing the upper limit of integration to be any r ∈ [0, 1]—both because this truncated integrand enables a direct reduction to an integral over the full interval [0, 1], and because this exact generality will be reused in Section 5 when we treat general distributions FB ⪰FSD FS. 2 (Non-Negativity of the Truncated Integral).

Generalization to Arbitrary Distributions

The final step in proving Theorem 1.1 involves extending the analysis from the symmetric continuous case (FB = FS) to arbitrary distributions satisfying first-order stochastic dominance (FB ⪰FSD FS) and arbitrary market sizes m ≥ n. p. 9

Where the paper says it

4 Warm-Up: Complete Proof for Symmetric Continuous Markets (FB = FS, m = n) Before treating general distributions under first-order stochastic dominance, we present the proof of Theorem 1. 1 in the symmetric continuous setting where FB = FS = F is continuous and m = n.

This extension shows that the threshold integral Ii(x) remains non-negative when the buyer distribution is generalized, leading to the final conclusion that STR(m, n + 2) ≥ OPT(m, n). p. 7
Where the paper says it

The following lemma is the main takeaway of this section: it shows that proving Theorem 1. 1 reduces to checking the non-negativity of a single threshold integral Ii(x) for each price threshold x ∈ R, which cleanly separates the recruitment gain from the trade-reduction loss.

The proof also establishes a lower bound for any prior-free mechanism M in the bilateral case (m = 1, k = 2), showing that GFTM(1, 2) < OPT(1, 1) under certain distributions. p. 2
Where the paper says it

Let M be any prior-free mechanism (deterministic or randomized) for m = 1 buyer and k = 2 sellers that is dominant-strategy incentive-compatible (DSIC), individually rational (IR), and weakly budget-balanced (WBB). Then there exist distributions FB ⪰FSD FS on [0, 1] with OPT(1, 1) > 0 such that GFTM(1, 2) < OPT(1, 1).

Tightness of the Bound

The paper concludes by showing that the uniform bound of two additional sellers is optimal by demonstrating that one additional seller does not suffice for any prior-free DSIC, IR, and WBB mechanism when m = n = 1. This tight bound implies that which side a market designer recruits on matters far more than how many traders are recruited. p. 3

Where the paper says it

Since Theorem 1. 1 places both additional traders on the scarce side, it also implies the corresponding two-sided bound.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Seller Trade Reduction for Scarce Sides: The AI system can achieve expected Gains From Trade at least OPT(m, n) by recruiting just two additional sellers when m >= n and buyer valuations first-order stochastically dominate seller costs (FB >= FSD FS).

  2. Optimal Recruitment Strategy: The system can determine that recruiting only two additional sellers is sufficient to match or exceed the first-best Gains From Trade of the original market, resolving a key open question for mechanisms like Seller Trade Reduction (STR).

  3. Robustness Against Mechanism Complexity: The system's analysis proves that recruiting only one additional seller is insufficient for any prior-free Dominant Strategy Incentive Compatible, Individually Rational, and Weakly Budget Balanced mechanism when m = n = 1.

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 at least n and buyer valuations first-order stochastically dominate seller costs (F B 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 at most 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) at least r(1 - F S(x)) for all x in R (recovering F B FSD F S at r = 1). When m at least n at least 1, c = 1/r + 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 (2, 1/r - 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 = 2/(5r), every prior-independent DSIC, IR, and WBB mechanism requires c at least 1/(64r) = Ω(1/r) additional traders per side.

Sources

Related papers