Stable matching problem: Difference between revisions

Revision as of 07:28, 23 October 2020

Revision as of 23:25, 13 December 2020

Line 13:

==Applications==

Algorithms for finding solutions to the stable marriage problem have applications in a variety of real-world situations, perhaps the best known of these being in the assignment of graduating medical students to their first hospital appointments.<ref>[http://www.dcs.gla.ac.uk/research/algorithms/stable/ Stable Matching Algorithms]</ref> In 2012, [[Nobel Memorial Prize in Economic Sciences]] was awarded to [[Lloyd S. Shapley]] and [[Alvin E. Roth]] "for the theory of stable allocations and the practice of market design."<ref>{{cite web|url=https://www.nobelprize.org/nobel_prizes/economics/laureates/2012/ |title=The Prize in Economic Sciences 2012 |publisher=Nobelprize.org |access-date= |accessdate=2013-09-09}}</ref>

An important and large-scale application of stable marriage is in assigning users to servers in a large distributed Internet service.<ref name=nuggets>{{cite journal | author= Bruce Maggs and [[Ramesh Sitaraman]] | title = Algorithmic nuggets in content delivery | journal= ACM SIGCOMM Computer Communication Review |year=2015|volume=45|issue=3|url = http://www.sigcomm.org/sites/default/files/ccr/papers/2015/July/0000000-0000009.pdf}}</ref> Billions of users access web pages, videos, and other services on the Internet, requiring each user to be matched to one of (potentially) hundreds of thousands of servers around the world that offer that service. A user prefers servers that are proximal enough to provide a faster response time for the requested service, resulting in a (partial) preferential ordering of the servers for each user. Each server prefers to serve users that it can with a lower cost, resulting in a (partial) preferential ordering of users for each server. [[Content delivery network]]s that distribute much of the world's content and services solve this large and complex stable marriage problem between users and servers every tens of seconds to enable billions of users to be matched up with their respective servers that can provide the requested web pages, videos, or other services.<ref name=nuggets />

Line 32:

All three are stable, because instability requires both of the participants to be happier with an alternative match. Giving one group their first choices ensures that the matches are stable because they would be unhappy with any other proposed match. Giving everyone their second choice ensures that any other match would be disliked by one of the parties. In general, the family of solutions to any instance of the stable marriage problem can be given the structure of a finite [[distributive lattice]],

and this structure leads to efficient algorithms for several problems on stable marriages.<ref>{{cite journal

| last = Gusfield | first = Dan | authorlinkauthor-link = Dan Gusfield

| doi = 10.1137/0216010

| issue = 1

Line 135:

The '''[[stable roommates problem]]''' is similar to the stable marriage problem, but differs in that all participants belong to a single pool (instead of being divided into equal numbers of "men" and "women").

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|accessdateaccess-date=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|last1=Gusfield|first1=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.

Line 155:

==Further reading==

* 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 |authorlinkauthor-link=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–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 }}