TY - JOUR
T1 - Top dominance and the possibility of strategy-proof stable solutions to matching problems
AU - Alcalde, José
AU - Barberà, Salvador
PY - 1994/5/1
Y1 - 1994/5/1
N2 - 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. © 1994 Springer-Verlag.
AB - 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. © 1994 Springer-Verlag.
U2 - https://doi.org/10.1007/BF01215380
DO - https://doi.org/10.1007/BF01215380
M3 - Article
VL - 4
SP - 417
EP - 435
JO - Economic Theory
JF - Economic Theory
SN - 0938-2259
ER -