Top dominance and the possibility of strategy-proof stable solutions to matching problems

Summary This paper explores the possibility of designing strategy-proof mechanisms yielding satisfactory solutions to the marriage and to the college admissions problem. Our first result is negative. We prove that no strategy-proof mechanism can always choose marriages that are individually rational and Pareto efficient. This strengthens a result by Roth (1982) showing that strategy-proof mechanisms cannot always select stable marriages. The result also applies, a fortiori, to college admissions. Since finding difficulties with strategy-proofness is quite an expected result, we then address a second question which is classical within the incentives literature. Are there restrictions on the preferences of agents under which strategy-proof and stable mechanisms do exist? We identify a nontrivial restriction on the domain of preferences, to be called top dominance, under which there exist strategy-proof and stable mechanisms for both types of matching problems. The mechanisms turn out to be exactly those that derive from the most classical algorithms in the literature; namely, the women's optimal, the men's optimal and the student's optimal. Finally, top dominance is shown to be essentially necessary, as well as sufficient, for the existence of strategy-proof stable matching mechanisms.This work is partially supported by grant PB 89-0294, from the Directión General de Investigatión Ciencia y Tecnología of the Spanish Ministerio de Educación y Ciencia. Salvador Barberà is also grateful to the Instituto de Estudios Fiscales. This research was initiated while both authors were visting GREMAQ, Université des Sciencies Sociales, Toulouse, whose hospitality is gratefully acknowledged. The paper extends results that were circulated as GREMAQ W.P. 91.22.232. We are grateful to Matthew Jackson and Marilda Sotomayor for their comments.