Sample Complexity of the Second-Best Bilateral Trade

Abstract

We study the sample complexity of learning near-optimal bilateral trade mechanisms. Unlike previous work on learning simple or fixed-price bilateral-trade mechanisms, we focus on mechanisms satisfying Bayesian incentive compatibility (BIC), interim individual rationality (IIR), and ex-ante weak budget balance (WBB). In other words, our target is to design a sample-based mechanism that achieves the second-best gains-from-trade benchmark. We give matching or nearly matching upper and lower bounds in three regimes. For regular product distributions on $[0,h{]}^2$, additive $\epsilon$-approximation has sample complexity $\tilde{\Theta }(h^2/{\epsilon }^2)$. For multiplicative $(1-\alpha )$-approximation under the same assumptions, we find that the sample complexity is $\tilde{\Theta }(h/(\mathrm{SB}(D){\alpha }^2))$, which is benchmark-sensitive with unavoidable dependence on the second-best gains from trade $\mathrm{SB}(D)$. We also investigate unbounded distributions under a monotone hazard rate (MHR) assumption. The sample complexity depends on the ratio ${\chi }_{\mu }(D)=\mu (D)/\mathrm{SB}(D)$, where $\mu (D)$ is the sum of the buyer's expected value and the seller's expected cost.