Why do stable clearinghouses work so well? - Small sets of stable matchings in typical environments, and the limits-on-manipulation theorem of Demange, Gale and Sotomayor

Alvin E.  Roth

doi:10.3934/jdg.2015009

Article Contents

2015, Volume 2, Issue 3&4: 331-340. Doi: 10.3934/jdg.2015009

This issue Previous Article Finding all stable matchings with couples Next Article Dynamic club formation with coordination

Why do stable clearinghouses work so well? - Small sets of stable matchings in typical environments, and the limits-on-manipulation theorem of Demange, Gale and Sotomayor

Alvin E. Roth^1,

1.
Department of Economics, Stanford University, Landau Economics Building, 579 Serra Mall, Room 344, Stanford University, Stanford, CA 94305-6072

Received: March 31, 2015

Revised: July 31, 2015

Published: June 2015

Abstract Related Papers Cited by

Abstract

Marilda Sotomayor is one of the pioneers of the theory of stable matching. She has published many important results, including some which are fundamental to subsequent developments. I will concentrate on one fundamental theorem, which today allows us to understand better why stable clearinghouses work so well. Demange, Gale and Sotomayor (1987)[16] proved a theorem which implies that when the set of stable matchings is small, participants in a stable clearinghouse will seldom be able to profit from strategically manipulating their preferences. More recent results show (empirically and theoretically) that the set of stable matchings can be expected to be small in typical applications. Therefore, reporting true preferences will be rewarded in clearinghouses that produce stable matchings in terms of stated preferences, and so there is a reason that such clearinghouses elicit sufficiently good preference data to produce matchings that are stable with respect to true preferences.

Keywords:

Stable matching,
market design.

Mathematics Subject Classification: 91A, 91B, 91C.

Citation:

Related Papers

Cited by

References

[1]	A. Abdulkadiroglu, P. A. Pathak and A. E. Roth, The New York City high school match, American Economic Review, Papers and Proceedings, 95 (2005), 364-367.
[2]	A. Abdulkadiroglu, P. A. Pathak and A. E. Roth, Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match, American Economic Review, 99 (2009), 1954-1978.
[3]	A. Abdulkadiroglu, P. A. Pathak, A. E. Roth and T. Sönmez, The Boston public school match, American Economic Review, Papers and Proceedings, 95 (2005), 368-371.
[4]	H. Adachi, On a characterization of stable matchings, Economics Letters, 68 (2000), 43-49.doi: 10.1016/S0165-1765(99)00241-4.
[5]	I. Ashlagi, M. Braverman and A. Hassidim, Stability in large matching markets with complementarities, Operations Research, 62 (2014), 713-732.doi: 10.1287/opre.2014.1276.
[6]	I. Ashlagi, Y. Kanoria and J. D. Leshno, Unbalanced random matching markets: The stark effect of competition, Journal of Political Economy, forthcoming. Available from: http://web.mit.edu/iashlagi/www/papers/UnbalancedMatchingAKL.pdf.
[7]	A. Banerjee, E. Duflo, M. Ghatak and J. Lafortune, Marry for what: Caste and mate selection in modern India, American Economic Journal: Microeconomics, 5 (2013), 33-72.
[8]	G. S. Becker, A theory of marriage: Part I, Journal of Political Economy, 81 (1973), 813-846.
[9]	G. S. Becker, A theory of marriage: Part II, Journal of Political Economy, 82 (1974), S11-S26.
[10]	G. S. Becker, A Treatise on the Family, Harvard University Press, Cambridge MA, 1981.
[11]	P. A. Coles and R. I. Shorrer, Optimal truncation in matching markets, Games and Economic Behavior, 87 (2014), 591-615.doi: 10.1016/j.geb.2014.01.005.
[12]	P. Coles, Y. Gonczarowski and R. I. Shorrer, Strategic behavior in unbalanced matching markets, Working Paper, 2014. Available from: http://scholar.harvard.edu/files/ran/files/cgs_0.pdf.
[13]	V. P. Crawford and E. M. Knoer, Job matching with heterogeneous firms and workers, Econometrica, 49 (1981), 437-450.
[14]	G. Demange and D. Gale, The strategy structure of 2-sided matching markets, Econometrica, 53 (1985), 873-888.doi: 10.2307/1912658.
[15]	G. Demange, D. Gale and M. Sotomayor, Multi-item auctions, Journal of Political Economy, 94 (1986), 863-872.
[16]	G. Demange, D. Gale and M. Sotomayor, A further note on the stable matching problem, Discrete Applied Mathematics, 16 (1987), 217-222.doi: 10.1016/0166-218X(87)90059-X.
[17]	L. E. Dubins and D. A. Freedman, Machiavelli and the gale-shapley algorithm, American Mathematical Monthly, 88 (1981), 485-494.doi: 10.2307/2321753.
[18]	F. Echenique and J. Oviedo, Core many-to-one matchings by fixed-point methods, Journal of Economic Theory, 115 (2004), 358-376.doi: 10.1016/S0022-0531(04)00042-1.
[19]	T. Fleiner, A fixed-point approach to stable matchings and some applications, Mathematics of Operations Research, 28 (2003), 103-126.doi: 10.1287/moor.28.1.103.14256.
[20]	D. Gale and L. Shapley, College admissions and the stability of marriage, American Mathematical Monthly, 69 (1962), 9-15.doi: 10.2307/2312726.
[21]	D. Gale and M. Sotomayor, Some remarks on the stable matching problem, Discrete Applied Mathematics, 11 (1985), 223-232.doi: 10.1016/0166-218X(85)90074-5.
[22]	D. Gale and M. Sotomayor, Ms. machiavelli and the stable matching problem, American Mathematical Monthly, 92 (1985), 261-268.doi: 10.2307/2323645.
[23]	J. Hatfield and P. Milgrom, Matching with contracts, American Economic Review 95 (2005), 913-935.
[24]	H. Günter, A. Hortaçsu and D. Ariely, Matching and sorting in online dating, American Economic Review, 100 (2010), 130-163.
[25]	R. Holzman and D. Samet, Matching of like rank and the size of the core in the marriage problem, Games and Economic Behavior 88 (2014), 277-285.doi: 10.1016/j.geb.2014.10.003.
[26]	A. Hylland and R. Zeckhauser, The efficient allocation of individuals to positions, Journal of Political Economy, 87 (1979), 293-314.
[27]	N. Immorlica and M. Mahdian, Marriage, honesty, and stability, SODA 2005 Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, 2005, 53-62.
[28]	J. H. Kagel and A. E. Roth, The dynamics of reorganization in matching markets: A laboratory experiment motivated by a natural experiment, Quarterly Journal of Economics, 115 (2000), 201-235.
[29]	M. Kaneko and M. H. Wooders, Cores of partitioning games, Mathematical Social Sciences, 3 (1982), 313-327.doi: 10.1016/0165-4896(82)90015-4.
[30]	A. S. Kelso, Jr. and V. P. Crawford, Job matching, coalition formation, and gross substitutes, Econometrica, 50 (1982), 1483-1504.
[31]	D. E. Knuth, Mariages Stables (French), Stable Mariages, Les Presses de l'Université de Montreal, Montreal, 1976.
[32]	D. E. Knuth, R. Motwani and B. Pittel, Stable husbands, Proceedings of the first annual ACM-SIAM Symposium on Discrete Algorithms, 1 (1990), 1-14.doi: 10.1002/rsa.3240010102.
[33]	F. Kojima and P. A. Pathak, Incentives and stability in large two-sided matching markets, American Economic Review, 99 (2009), 608-627.
[34]	F. Kojima, P. A. Pathak and A. E. Roth, Matching with couples: Stability and incentives in large markets, Quarterly Journal of Economics, 128 (2013), 1585-1632.
[35]	T. C. Koopmans and M. Beckmann, Assignment problems and the location of economic activities, Econometrica, 25 (1957), 53-76.doi: 10.2307/1907742.
[36]	D. G. McVitie, The stable marriage problem and the selection of students for university admission, M.Sc. Thesis, University of Newcastle upon Tyne, 1967.
[37]	D. G. McVitie and L. B. Wilson, Stable marriage assignments for unequal sets, BIT Numerical Mathematics, 10 (1970), 295-309.
[38]	D. G. McVitie and L. B. Wilson, The application of the stable marriage assignment to university admissions, Operational Research Quarterly, 21 (1970), 425-433.
[39]	D. G. McVitie and L. B. Wilson, The stable marriage problem, Communications of the ACM, 14 (1971), 486-490.doi: 10.1145/362619.362631.
[40]	A. E. Roth, The economics of matching: Stability and incentives, Mathematics of Operations Research, 7 (1982), 617-628.doi: 10.1287/moor.7.4.617.
[41]	A. E. Roth, Incentive compatibility in a market with indivisible goods, Economics Letters, 9 (1982), 127-132.doi: 10.1016/0165-1765(82)90003-9.
[42]	A. E. Roth, The evolution of the labor market for medical interns and residents: A case study in game theory, Journal of Political Economy, 92 (1984), 991-1016.
[43]	A. E. Roth, Misrepresentation and stability in the marriage problem, Journal of Economic Theory, 34 (1984), 383-387.doi: 10.1016/0022-0531(84)90152-2.
[44]	A. E. Roth, The college admissions problem is not equivalent to the marriage problem, Journal of Economic Theory, 36 (1985), 277-288.doi: 10.1016/0022-0531(85)90106-1.
[45]	A. E. Roth, New physicians: A natural experiment in market organization, Science, 250 (1990), 1524-1528.
[46]	A. E. Roth, A natural experiment in the organization of entry level labor markets: Regional markets for new physicians and surgeons in the U.K., American Economic Review, 81 (1991), 415-440.
[47]	A. E. Roth and E. Peranson, The redesign of the matching market for american physicians: Some engineering aspects of economic design, American Economic Review, 89 (1999), 748-780.
[48]	A. E. Roth and M. Sotomayor, Interior points in the core of two-sided matching markets, Journal of Economic Theory, 45 (1988), 85-101.doi: 10.1016/0022-0531(88)90255-4.
[49]	A. E. Roth and M.a Sotomayor, The college admissions problem revisited, Econometrica, 57 (1989), 559-570.doi: 10.2307/1911052.
[50]	A. E. Roth and M. Sotomayor, Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge University Press, 1990.doi: 10.1017/CCOL052139015X.
[51]	L. S. Shapley and M. Shubik, The assignment game I: The core, International Journal of Game Theory, 1 (1972), 111-130.
[52]	M. Sotomayor, A non-constructive elementary proof of the existence of stable marriages, Games and Economic Behavior, 13 (1996), 135-137.doi: 10.1006/game.1996.0029.
[53]	M. Sotomayor, The lattice structure of the set of stable outcomes of the multiple partners assignment game, International Journal of Game Theory, 28 (1999), 567-583.doi: 10.1007/s001820050126.
[54]	M. Sotomayor, Existence of stable outcomes and the lattice property for a unified matching market, Mathematical Social Sciences, 39 (2000), 119-132.doi: 10.1016/S0165-4896(99)00028-1.
[55]	M. Sotomayor, An elementary non-constructive proof of the non-emptiness of the core of the housing market of Shapley and Scarf, Mathematical Social Sciences, 50 (2005), 298-303.doi: 10.1016/j.mathsocsci.2005.04.004.