Learning Second-Best Mechanism in Matching Markets

We study the sample complexity of learning the Bayesian second-best gains from trade in matching markets with unknown value and cost distributions. For independent distributions, we give a sample-based learning algorithm that always outputs a universally dominant-strategy incentive-compatible and ex-post individually rational mechanism and, with high probability, outputs an ex-ante weakly budget-balanced mechanism whose expected gains from trade are within $ϵ$ of the second-best benchmark. For a market with $d$ unknown marginal distributions supported on $[0,h]$ and maximum feasible matching size $r$, we establish a per-marginal sample complexity of $\tilde{\Theta }\left(dr{h}^2/{ϵ}^2\right)$, which is tight up to logarithmic factors. The upper bound uses a critical-contact decomposition to localize the effect of marginal perturbations, with the aggregate exposure controlled by the maximum feasible matching size $r$. For the lower bound, we construct hard instances on star forests and show that the dependence on both $d$ and $r$ is unavoidable.