Two-sided matching, private information, and the impossibility of ex post efficient trade

David Delacretaz | University of Melbourne

Call buyers and sellers in a two-sided allocation problem component complements (CC) if the social surplus generated in each component of the optimal trading network exceeds the sum of the social marginal products of all individuals within the component. Assum- ing that least efficient types never trade, we show that under condition CC no efficient dominant strategy mechanism that respects agents' individual rationality constraints can induce efficient trade and generate a budget surplus. If CC holds with strict inequality, every such mechanism incurs a budget deficit. Using a generalization of Shapley (1962), we show that a sufficient condition for this conditions is that the problem is decomposable into a one-to-one matching problem. We use this result to extend the impossibility theo- rem of Myerson and Satterthwaite (1983a) to (i) all one-to-one assignment problems, (ii) many-to-many exchange environments with homogeneous goods and decreasing marginal valuations, and an additively separable heterogenous commodity model (ASHC) similar to the one developed in Ausubel (2006).