The Power of Two-Sided Recruitment in Two-Sided Markets

We consider the problem of maximizing the gains from trade (GFT) in two-sided markets. The seminal impossibility result by Myerson and Satterthwaite [MS83] shows that even for bilateral trade, there is no individually rational (IR), Bayesian incentive compatible (BIC) and budget balanced (BB) mechanism that can achieve the full GFT. Moreover, the optimal BIC, IR and BB mechanism that maximizes the GFT is known to be complex and heavily depends on the prior.

In this paper, we pursue a Bulow-Klemperer-style question, i.e., does augmentation allow for priorindependent mechanisms to compete against the optimal mechanism? Our first main result shows that in the double auction setting with m i.i.d. buyers and n i.i.d. sellers, by augmenting O(1) buyers and sellers to the market, the GFT of a simple, dominant strategy incentive compatible (DSIC), and priorindependent mechanism in the augmented market is at least the optimal in the original market, when the buyers' distribution first-order stochastically dominates the sellers' distribution. The mechanism we consider is a slight variant of the standard Trade Reduction mechanism due to McAfee [McA92]. For comparison, Babaioff, Goldner, and Gonczarowski [BGG20] showed that if one is restricted to augmenting only one side of the market, then n(m + 4 √ m) additional agents are sufficient for their mechanism to beat the original optimal and ⌊log 2 m⌋ additional agents are necessary for any priorindependent mechanism.

Next, we go beyond the i.i.d. setting and study the power of two-sided recruitment in more general markets. Our second main result is that for any ε > 0 and any set of O(1/ε) buyers and sellers where the buyers' value exceeds the sellers' value with constant probability, if we add these additional agents into any market with arbitrary correlations, the Trade Reduction mechanism obtains a (1ε)-approximation of the GFT of the augmented market. Importantly, the newly recruited agents are agnostic to the original market.