Skip to main content
SpringerLink
Log in

Bipartite choices

  • Published:
Decisions in Economics and Finance Aims and scope Submit manuscript

Abstract

This piece in the Milestones series is dedicated to the paper coauthored by David Gale and Lloyd Shapley and published in 1962 under the title “College admissions and the stability of marriage” on the American Mathematical Monthly.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. A few years later, his cowinner Roth mused: “I’m hardly alone among economists of my generation who don’t have degrees in economics. A bunch of us rode in on the wave that brought game theory into economics” (Roth 2018, p. 1609).

  2. Notwithstanding his many other achievements, Shapley was awarded the Nobel prize in Economics for CASM. An afternoon’s work from a mathematician may go a long way.

  3. We surmise that this is a common starting point for drama: a (unique) stable matching where everybody feels unfulfilled.

  4. From Shapley’s letter: “Let each boy propose to his best girl. Let each girl with several proposals reject all but her favorite, but defer acceptance until she is sure no one better will come her way. The rejected boys then propose to their next-best choices, and so on, until there are no girls with more than one suitor. Marry” (Levine 2018, p. 8).

  5. The KDF9 was built for mathematical and scientific processing. Its logic circuits were entirely solid-state. It weighed 4.7 tonnes. Between 1964 and 1980 only 29 machines were produced.

  6. The online introduction to Bergstrom and Manning (1983) incorrectly refers to Roth (1984a) instead of Roth (1982).

  7. Our paper conflates assignments and matchings, as in the old literature. Nowadays, it is customary to speak of matchings when both sides of the market have preferences, and of assignments otherwise.

  8. Roth (2002) acknowledges Wilson as the Dean of Design. Their thoughts about game theory and market design are lively juxtaposed in Roth and Wilson (2019).

  9. There are exceptions: f.i., schools in New York City are active players, whose preferences affect the final allocation.

  10. There is no space to go over the many medical and ethical details; see f.i. Chapter 4 in Vulkan et al. (2013).

References

  • Abeledo, H.G., Isaak, G.: A characterization of graphs which assure the existence of stable matchings. Math. Soc. Sci. 22, 93–96 (1991)

    Article  Google Scholar 

  • Abdulkadiroğlu, A., Sönmez, T.: School choice: a mechanism design approach. Am. Econ. Rev. 93, 729–747 (2003)

    Article  Google Scholar 

  • Abdulkadiroğlu, A., Sönmez, T.: Matching markets: theory and practice. In: Acemoglu, D., Arellano, M., Dekel, E. (eds.) Advances in Economics and Econometrics: Tenth World Congress, pp. 3–47. Cambridge University Press, Cambridge (2013)

    Chapter  Google Scholar 

  • Alkan, A.: Nonexistence of stable threesome matchings. Math. Soc. Sci. 16, 207–209 (1988)

    Article  Google Scholar 

  • Baccara, M., Lee, S., Yariv, L.: Optimal dynamic matching. Theor. Econ. 15, 1221–1278 (2020)

    Article  Google Scholar 

  • Balinski, M., Raitier, G.: Of stable marriages and graphs, and strategy and polytopes. SIAM Rev. 39, 575–604 (1997)

    Article  Google Scholar 

  • Balinski, M., Raitier, G.: Graphs and marriages. Am. Math. Mon. 105, 430–445 (1998)

    Article  Google Scholar 

  • Balinski, M., Sönmez, T.: A tale of two mechanisms: student placement. J. Econ. Theory 84, 73–94 (1999)

    Article  Google Scholar 

  • Bergstrom, T., Manning, R.: Can courtship be cheatproof? Working paper (1983). https://escholarship.org/uc/item/5dg0f759

  • Blair, C.: Every finite distributive lattice is a set of stable matching. J. Comb. Theory Ser. A. 37, 353–356 (1984)

    Article  Google Scholar 

  • Crawford, V.P., Knoer, E.M.: Job matching with heterogeneous firms and workers. Econometrica 49, 437–450 (1981)

    Article  Google Scholar 

  • Chiappori, P.-A.: Matching with Transfers: The Economics of Love and Marriage. Princeton University Press, Princeton (2017)

    Book  Google Scholar 

  • Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)

  • Deijfen, M., Holroyd, A.E., Martin, J.B.: Friendly frogs, stable marriage, and the magic of invariance. Am. Math. Mon. 124, 387–402 (2017)

    Article  Google Scholar 

  • Demange, G., Gale, D.: The strategy structure of two-sided matching markets. Econometrica 53, 873–888 (1985)

    Article  Google Scholar 

  • Doval, L.: Dynamically stable matching. Theor. Econ. 17, 687–724 (2022)

    Article  Google Scholar 

  • Dubins, L.E., Freedman, D.A.: Machiavelli and the Gale–Shapley algorithm. Am. Math. Mon. 88, 485–494 (1981)

    Article  Google Scholar 

  • Eisenberg, E., Gale, D.: Consensus of subjective probabilities: the pari-mutuel method. Ann. Math. Stat. 30, 165–168 (1959)

    Article  Google Scholar 

  • Fleiner, T.: A fixed-point approach to stable matchings and some applications. Math. Oper. Res. 28, 103–126 (2003)

    Article  Google Scholar 

  • Fenoaltea, E.M., Baybusinov, I.B., Zhao, J., Zhou, L., Zhang, Y.-C.: The stable marriage problem: an interdisciplinary review from the physicist’s perspective. Phys. Rep. 917, 1–79 (2021)

    Article  Google Scholar 

  • Gale, D.: A theory of n-person games with perfect information. Proc. Natl. Acad. Sci. 39, 496–501 (1953)

    Article  Google Scholar 

  • Gale, D.: The two-sided matching problem. Origin, development and current issues. Int. Game Theory Rev. 3, 237–252 (2001)

    Article  Google Scholar 

  • Gale, D.: Topological games at Princeton: a mathematical memoir. Games Econ. Behav. 66, 647–656 (2009)

    Article  Google Scholar 

  • Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9–15 (1962). (Reprinted in: Am. Math. Mon. 120, 386–391 (2013))

  • Gale, D., Sotomayor, M.: Ms. Machiavelli and the stable matching problem. Am. Math. Mon. 92, 261–268 (1985)

    Article  Google Scholar 

  • Gans, J.S., Shepherd, G.B.: How are the mighty fallen: rejected classic articles by leading economists. J. Econ. Perspect. 8, 165–179 (1994)

    Article  Google Scholar 

  • Gardner, M.: Mathematical games. Sci. Am. Jan. 110–111 (1973)

  • Gibbard, A.: Manipulation of voting schemes: a general result. Econometrica 41, 587–601 (1973)

    Article  Google Scholar 

  • Greinecker, M., Kah, C.: Pairwise stable matching in large economics. Econometrica 89, 2929–2974 (2021)

    Article  Google Scholar 

  • Grimm, W., Grimm, J.: Das lied von Hildebrand und Hadubrand und das Wei\(\beta \)enbrunner Gebet. Thurneisen, Kassel (1812)

    Google Scholar 

  • Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. The MIT Press, Cambridge (1989)

    Google Scholar 

  • Halmos, P.R.: Statement of policy. Am. Math. Mon. 89, 3–4 (1982)

    Article  Google Scholar 

  • Hatfield, G.W., Milgrom, P.R.: Matching with contracts. Am. Econ. Rev. 95, 913–935 (2005)

    Article  Google Scholar 

  • Jain, K., Vaziarni, V.V.: Eisenberg–Gale markets: algorithms and game-theoretic properties. Games Econ. Behav. 70, 84–106 (2010)

    Article  Google Scholar 

  • Kelso, A.S., Jr., Crawford, V.P.: Job matching, coalition formation, and gross substitutes. Econometrica 50, 1483–1504 (1982)

    Article  Google Scholar 

  • Knuth, D.E.: Mariages Stables et Leurs Relations avec d’Autres Problèmes Combinatoires. Les Presses de l’Université de Montréal, Montréal (1981). Translated in English as: Stable Marriage and its Relation to Other Combinatorial Problems. American Mathematical Society, Providence (1997)

  • Knuth, D.E., Motwani, R., Pittel, B.: Stable husbands. Random Struct. Algorithms 1, 1–14 (1990)

    Article  Google Scholar 

  • Kojima, F.: Recent developments in matching theory and their practical applications. In: Honoré, B., Pakes, A., Piazzesi, M., Samuelson, L. (eds.) Advances in Economics and Econometrics: Eleventh World Congress, pp. 138–175. Cambridge University Press, Cambridge (2017)

    Chapter  Google Scholar 

  • Kominers, S.D., Teytelboym, A., Crawford, V.P.: An invitation to market design. Oxford Rev. Econ. Policy 33, 541–571 (2017)

    Article  Google Scholar 

  • Koopmans, T.C., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica 25, 53–76 (1957)

    Article  Google Scholar 

  • Levine, D.K.: Introduction to the special issue in honor of Lloyd Shapley: eight topics in game theory. Games Econ. Behav. 108, 1–12 (2018)

    Article  Google Scholar 

  • Maffray, F.: Kernels in perfect line-graphs. J. Combin. Theory Ser. B 55, 1–8 (1992)

    Article  Google Scholar 

  • McVitie, D.G., Wilson, L.V.: Stable marriage assignment for unequal sets. BIT Numer. Math. 10, 295–309 (1970a)

  • McVitie, D.G., Wilson, L.V.: The application of the stable marriage assignment to university admissions. Oper. Res. Quart. 21, 425–433 (1970b)

  • McVitie, D.G., Wilson, L.V.: The stable marriage problem. Commun. ACM 14, 486–490 (1971)

    Article  Google Scholar 

  • Ostrovsky, M.: Stability in supply chain networks. Am. Econ. Rev. 98, 897–923 (2008)

    Article  Google Scholar 

  • Persson, T.: Award ceremony speech, 10 December 2012, NobelPrize.org (2012). www.nobelprize.org/prizes/economic-sciences/2012/ceremony-speech/

  • Popper, K.R.: The Poverty of Historicism. Basic Books, New York (1957)

    Google Scholar 

  • Rostek, M., Yoder, N.: Matching with complementary contracts. Econometrica 88, 1793–1827 (2020)

    Article  Google Scholar 

  • Roth, A.: The economics of matching: stability and incentives. Math. Oper. Res. 7, 617–628 (1982)

    Article  Google Scholar 

  • Roth, A.E.: Misrepresentation and stability in the marriage problem. J. Econ. Theory 34, 383–387 (1984a)

  • Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Pol. Econ. 92, 991–1016 (1984b)

  • Roth, A.E.: The college admissions problem is not equivalent to the marriage problem. J. Econ. Theory 36, 277–288 (1985)

    Article  Google Scholar 

  • Roth, A.: Conflict and coincidence of interest in job matching: some new results and open questions. Math. Oper. Res. 10, 379–389 (1985)

    Article  Google Scholar 

  • Roth, A.E.: The economist as engineer: game theory, experimentation, and computation as tools for design economics. Econometrica 70, 1341–1378 (2002)

    Article  Google Scholar 

  • Roth, A.E.: The origins, history, and design of the resident match. JAMA 289, 909–912 (2003)

    Article  Google Scholar 

  • Roth, A.E.: Deferred acceptance algorithms: history, theory, practice, and open questions. Int. J. Game Theory 36, 537–569 (2008)

    Article  Google Scholar 

  • Roth, A.E.: Marketplaces, markets, and market design. Am. Econ. Rev. 108, 1609–1658 (2018)

    Article  Google Scholar 

  • Roth, A.E., Peranson, E.: The redesign of the matching market for American physicians: some engineering aspects of economic design. Am. Econ. Rev. 89, 748–780 (1999)

    Article  Google Scholar 

  • Roth, A.E., Sönmez, T., Ünver, M.T.: Kidney exchange. Quant. J. Econ. J. 119, 457–488 (2004)

    Google Scholar 

  • Roth, A.E., Wilson, R.B.: How market design emerged from game theory: a mutual interview. J. Econ. Perspect. 33, 118–143 (2019)

    Article  Google Scholar 

  • Roth, A.E., Sotomayor, M.: Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge Univ. Press, Cambridge (1990)

    Book  Google Scholar 

  • Satterthwaite, M.: Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. J. Econ. Theory 10, 187–217 (1975)

    Article  Google Scholar 

  • Schuh, F.: Spel van delers. Nieuw Tijdschrift voor Wiskunde 39, 299–304 (1952)

    Google Scholar 

  • Shapley, L.S.: A value for \(n\)-person games. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games, vol. II, pp. 307–317. Princeton University Press, Princeton (1953)

    Google Scholar 

  • Shapley, L.S., Shubik, M.: The assignment game I: the core. Int. J. Game Theory 1, 111–130 (1971)

    Article  Google Scholar 

  • Shapley, L.S., Scarf, H.: On cores and indivisibility. J. Math. Econ. 1, 23–37 (1974)

    Article  Google Scholar 

  • Sobel, J.: ReGale: some memorable results. Games Econ. Behav. 66, 632–642 (2009)

    Article  Google Scholar 

  • Sönmez, T., Ünver, M.T.: Matching, allocation, and exchange of discrete resources. In: Benhabib, J., Bisin, A., Jackson, M.O. (eds.) Handbook of Social Economics, vol. 1A, pp. 781–852. Elsevier, Amsterdam (2011)

    Google Scholar 

  • Sotomayor, M.: Letter on David Gale’s work to Bernhard von Stengel, 12 March (2008). https://gametheorysociety.org/david-gale-december-13-1921-march-7-2008/

  • The Economist: Priceless. 18th October (2012)

  • The Royal Swedish Academy of Sciences.: The Prize in Economic Sciences, Information to the Public (2012). https://www.nobelprize.org/uploads/2018/06/popular-economicsciences2012.pdf

  • van Basshuysen, P.: Markets, market algorithms, and algorithmic bias. J. Econ. Methodol. (forthcoming) (2022)

  • Vande Vate, J.H.: Linear programming brings marital bliss. Oper. Res. Lett. 8, 147–153 (1989)

    Article  Google Scholar 

  • Von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton (1944)

    Google Scholar 

  • Vulkan, N., Roth, A.E., Neeman, Z.: The Handbook of Market Design. Oxford University Press, Oxford (2013)

    Book  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Management, Università Ca’ Foscari Venezia, Cannaregio 873, 30121, Venezia, Italy

    Marco LiCalzi

Authors
  1. Marco LiCalzi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marco LiCalzi.

Ethics declarations

Conflict of interest

The author is a member of the Editorial Board of Decisions in Economics and Finance. The author did not receive support from any organization for the submitted work. He has no financial or proprietary interest to disclose.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

I wish to thank Francesca Beccacece, Cristina Molinari, Niccolò Urbinati, Gino Favero, Achille Basile, and three referees for their comments.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

LiCalzi, M. Bipartite choices. Decisions Econ Finan 45, 551–568 (2022). https://doi.org/10.1007/s10203-022-00380-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10203-022-00380-z

Keywords

Mathematics Subject Classification

JEL Classification

Search

Navigation