ON A CONJECTURE BY GALE ABOUT ONE-SIDED MATCHING PROBLEMS

This paper proves the following result on one-sided matching problems: when there are n objects to be assigned to n agents, for n ≥3, there exits no mechanism that satisfies symmetry, Pareto optimality, and strategy-proofness. Examples of mechanisms are presented to show the independence of the conditions, which also illustrate the well-known tradeoff between equity and efficiency in the framework of matching problems. Finally, some extensions of the result to more general matching problems are considered. © 1990.