# American Institute of Mathematical Sciences

April  2015, 2(3&4): 331-340. doi: 10.3934/jdg.2015009

## 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

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

Received  April 2015 Revised  August 2015 Published  November 2015

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.
Citation: Alvin E. Roth. 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. Journal of Dynamics and Games, 2015, 2 (3&4) : 331-340. doi: 10.3934/jdg.2015009
##### 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, (). [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.

show all references

##### 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, (). [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.
 [1] E. Camouzis, H. Kollias, I. Leventides. Stable manifold market sequences. Journal of Dynamics and Games, 2018, 5 (2) : 165-185. doi: 10.3934/jdg.2018010 [2] V. Carmona, E. Freire, E. Ponce, F. Torres. The continuous matching of two stable linear systems can be unstable. Discrete and Continuous Dynamical Systems, 2006, 16 (3) : 689-703. doi: 10.3934/dcds.2006.16.689 [3] Jie Wei, Meijing Chang. Online channel design in the presence of price self-matching: Self-operating or e-marketplace?. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022043 [4] Didier Vila, Alain Martel, Robert Beauregard. Taking market forces into account in the design of production-distribution networks: A positioning by anticipation approach. Journal of Industrial and Management Optimization, 2007, 3 (1) : 29-50. doi: 10.3934/jimo.2007.3.29 [5] Carlos Hervés-Beloso, Emma Moreno-García. Market games and walrasian equilibria. Journal of Dynamics and Games, 2020, 7 (1) : 65-77. doi: 10.3934/jdg.2020004 [6] Jose S. Cánovas, María Muñoz-Guillermo. On the dynamics of a durable commodity market. Discrete and Continuous Dynamical Systems - B, 2019, 24 (12) : 6621-6631. doi: 10.3934/dcdsb.2019159 [7] Simone Farinelli. Geometric arbitrage theory and market dynamics. Journal of Geometric Mechanics, 2015, 7 (4) : 431-471. doi: 10.3934/jgm.2015.7.431 [8] Alberto A. Pinto, João P. Almeida, Telmo Parreira. Local market structure in a Hotelling town. Journal of Dynamics and Games, 2016, 3 (1) : 75-100. doi: 10.3934/jdg.2016004 [9] Lixin Wu, Fan Zhang. LIBOR market model with stochastic volatility. Journal of Industrial and Management Optimization, 2006, 2 (2) : 199-227. doi: 10.3934/jimo.2006.2.199 [10] Didier Aussel, Rafael Correa, Matthieu Marechal. Electricity spot market with transmission losses. Journal of Industrial and Management Optimization, 2013, 9 (2) : 275-290. doi: 10.3934/jimo.2013.9.275 [11] Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete and Continuous Dynamical Systems, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281 [12] Luigi Ambrosio, Federico Glaudo, Dario Trevisan. On the optimal map in the $2$-dimensional random matching problem. Discrete and Continuous Dynamical Systems, 2019, 39 (12) : 7291-7308. doi: 10.3934/dcds.2019304 [13] Danilo Coelho, David Pérez-Castrillo. On Marilda Sotomayor's extraordinary contribution to matching theory. Journal of Dynamics and Games, 2015, 2 (3&4) : 201-206. doi: 10.3934/jdg.2015001 [14] Shichu Chen, Zhiqiang Wang, Yan Ren. A fast matching algorithm for the images with large scale disparity. Mathematical Foundations of Computing, 2020, 3 (3) : 141-155. doi: 10.3934/mfc.2020021 [15] J. M. Mazón, Julio D. Rossi, J. Toledo. Optimal matching problems with costs given by Finsler distances. Communications on Pure and Applied Analysis, 2015, 14 (1) : 229-244. doi: 10.3934/cpaa.2015.14.229 [16] Paola B. Manasero. Equivalences between two matching models: Stability. Journal of Dynamics and Games, 2018, 5 (3) : 203-221. doi: 10.3934/jdg.2018013 [17] F. M. Bass, A. Krishnamoorthy, A. Prasad, Suresh P. Sethi. Advertising competition with market expansion for finite horizon firms. Journal of Industrial and Management Optimization, 2005, 1 (1) : 1-19. doi: 10.3934/jimo.2005.1.1 [18] Michael Grinfeld, Harbir Lamba, Rod Cross. A mesoscopic stock market model with hysteretic agents. Discrete and Continuous Dynamical Systems - B, 2013, 18 (2) : 403-415. doi: 10.3934/dcdsb.2013.18.403 [19] Dieter Armbruster, Christian Ringhofer, Andrea Thatcher. A kinetic model for an agent based market simulation. Networks and Heterogeneous Media, 2015, 10 (3) : 527-542. doi: 10.3934/nhm.2015.10.527 [20] Duy Nguyen, Jingzhi Tie, Qing Zhang. Stock trading rules under a switchable market. Mathematical Control and Related Fields, 2013, 3 (2) : 209-231. doi: 10.3934/mcrf.2013.3.209

Impact Factor: