Gains-from-Trade in Bilateral Trade with a Broker

We study bilateral trade with a broker, where a buyer and seller interact exclusively through the broker. The broker strategically maximizes her payoff through arbitrage by trading with the buyer and seller at different prices. We study whether the presence of the broker interferes with the mechanism's gains-from-trade (GFT) achieving a constant-factor approximation to the first-best gains-from-trade (FB), in a similar vein to the constant-factor approximability without a broker by Deng, Mao, Sivan and Wang (STOC'21).

We first identify a structural connection between GFT, FB, and the broker's expected profit when the broker uses a posted-pricing mechanism, which implies the 1/2-approximation via median-based pricing by McAfee (AERB'08) as a special case. More importantly, inspired by this, we show that the GFT achieves a 1/36-approximation to the FB even if the broker runs an optimal posted-pricing mechanism under symmetric agents with monotone-hazard-rate distributions, which are central to mechanism design due to Myerson (MOR'81). We cement this result by proving that the approximation factor can also be lower bounded by 2/M 2 if the hazard rates are bounded above by M . Furthermore, if the broker uses a quantile-based postedpricing mechanism of offering the α-quantile (of the buyer's distribution) to the buyer and the β-quantile (of the seller's distribution) to the seller, e.g., due to a lack of a precise estimation of the distributions, the mechanism achieves a β(1 -α)-approximation to the first-best GFT. As a corollary, we prove that there exists a simple single-sample mechanism of the broker that achieves a 1/12-approximation to the first-best GFT.

Beyond posted-pricing mechanisms, even if the broker uses an arbitrary incentive-compatible (IC) and individually-rational (IR) mechanism that maximizes her expected profit, we prove that it induces a 1/2-approximation to the first-best GFT when the buyer's and seller's distributions are uniform distributions with arbitrary supports. This bound is shown to be tight.

We complement such results by proving that if the broker uses an arbitrary profit-maximizing IC and IR mechanism, there exists a family of problem instances under which the approximation factor to the first-best GFT becomes arbitrarily close to zero. We show that this phenomenon persists even if we restrict one of the buyer's or seller's distributions to have a singleton support, or even in the symmetric setting where the buyer and seller have identical distributions. Finally, we show that in the general-distribution and public-seller settings, the inapproximability of the first-best gains-from-trade carries over to first-best social welfare as well.