Stable matching problem: Difference between revisions

Revision as of 20:50, 19 September 2020

Revision as of 15:20, 27 September 2020

Line 82:

{{main|Gale–Shapley algorithm}}

[[File:Gale-Shapley.gif|thumb|right|Animation showing an example of the Gale–Shapley algorithm]]

In 1962, [[David Gale]] and [[Lloyd Shapley]] proved that, for any equal number of men and women, it is always possible to solve the SMP and make all marriages stable. They presented an [[algorithm]] to do so.<ref name=gs62>{{cite journal |firstfirst1=D. |lastlast1=Gale |first2=L. S. |last2=Shapley |title=College Admissions and the Stability of Marriage |journal=[[American Mathematical Monthly]] |volume=69 |issue= 1|pages=9–14 |year=1962 |jstor=2312726 |doi=10.2307/2312726|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0251958 }}</ref><ref>[[Harry Mairson]]: "The Stable Marriage Problem", ''The Brandeis Review'' 12, 1992 ([http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html online]).</ref>

The [[Gale–Shapley algorithm]] (also known as the deferred acceptance algorithm) involves a number of "rounds" (or "[[iteration]]s"):

Line 137:

The '''[[Hospital resident|hospitals/residents problem]]''' – also known as the '''college admissions problem''' – differs from the stable marriage problem in that a hospital can take multiple residents, or a college can take an incoming class of more than one student. Algorithms to solve the hospitals/residents problem can be ''hospital-oriented'' (as the [[National Resident Matching Program|NRMP]] was before 1995)<ref name="Robinson">{{cite journal|last=Robinson|first=Sara|date=April 2003|title=Are Medical Students Meeting Their (Best Possible) Match?|url=http://www.siam.org/pdf/news/305.pdf|journal=SIAM News|issue=3|page=36|accessdate=2 January 2018}}</ref> or ''resident-oriented''. This problem was solved, with an algorithm, in the same original paper by Gale and Shapley, in which the stable marriage problem was solved.<ref name=gs62/>

The '''[[Hospital resident|hospitals/residents problem with couples]]''' allows the set of residents to include couples who must be assigned together, either to the same hospital or to a specific pair of hospitals chosen by the couple (e.g., a married couple want to ensure that they will stay together and not be stuck in programs that are far away from each other). The addition of couples to the hospitals/residents problem renders the problem [[NP-complete]].<ref>{{cite book|title=The Stable Marriage Problem: Structure and Algorithms|lastlast1=Gusfield|firstfirst1=D.|last2=Irving|first2=R. W.|publisher=MIT Press|year=1989|isbn=0-262-07118-5|___location=|page=54}}</ref>

The '''[[assignment problem]]''' seeks to find a matching in a weighted [[bipartite graph]] that has maximum weight. Maximum weighted matchings do not have to be stable, but in some applications a maximum weighted matching is better than a stable one.

The '''matching with contracts''' problem is a generalization of matching problem, in which participants can be matched with different terms of contracts.<ref>{{cite journal |firstfirst1=John William |lastlast1=Hatfield |first2=Paul |last2=Milgrom |title=Matching with Contracts |journal=[[American Economic Review]] |volume=95 |issue=4 |year=2005 |pages=913–935 |jstor=4132699 |doi=10.1257/0002828054825466}}</ref> An important special case of contracts is matching with flexible wages.<ref>{{cite journal |firstfirst1=Vincent |lastlast1=Crawford |first2=Elsie Marie |last2=Knoer |title=Job Matching with Heterogeneous Firms and Workers |year=1981 |journal=[[Econometrica]] |volume=49 |issue=2 |pages=437–450 |jstor=1913320 |doi=10.2307/1913320}}</ref>

== See also ==

Line 156:

* Kleinberg, J., and Tardos, E. (2005) ''Algorithm Design'', Chapter 1, pp 1–12. See companion website for the Text [http://www.aw-bc.com/info/kleinberg/].

* {{cite book |authorlink=Donald Knuth |last=Knuth |first=D. E. |year=1996 |title=Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms |others=English translation |series=CRM Proceedings and Lecture Notes |publisher=American Mathematical Society }}

* {{cite journal |last=Pittel |first=B. |year=1992 |title=On likely solutions of a stable marriage problem |journal=[[The Annals of Applied Probability]] |volume=2 |issue=2 |pages=358-401358–401 |doi=10.1214/aoap/1177005708 |jstor=2959755 }}

* {{cite journal |last=Roth |first=A. E. |year=1984 |title=The evolution of the labor market for medical interns and residents: A case study in game theory |journal=[[Journal of Political Economy]] |volume=92 |issue=6 |pages=991–1016 |doi=10.1086/261272 |url=http://dash.harvard.edu/bitstream/handle/1/29410143/evolut.pdf }}

* {{cite book | last1=Roth |first1=A. E. |last2=Sotomayor |first2=M. A. O. |year=1990 |title=Two-sided matching: A study in game-theoretic modeling and analysis |publisher=[[Cambridge University Press]] }}

* {{cite book | last1=Shoham | first1=Yoav | last2=Leyton-Brown | first2=Kevin | title=Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations | publisher=[[Cambridge University Press]] | isbn=978-0-521-89943-7 | url=http://www.masfoundations.org | year=2009 | ___location=New York}} See Section 10.6.4; [http://www.masfoundations.org/download.html downloadable free online].