Gale–Shapley algorithm: Difference between revisions

Revision as of 10:16, 11 November 2021

Revision as of 07:12, 15 November 2021

Line 16:

==Solution==

[[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>{{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> In 1984, [[Alvin E. Roth]] observed that essentially the same algorithm had already been in practical use since the early 1950s, in the [[National Resident Matching Program]].<ref>{{cite journal|last=Bergstrom|first=Theodore C.|date=June 1992|issue=2|journal=[[Journal of Economic Literature]]|jstor=2727713|pages=896–898|title=Review of ''Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis'' by A. E. Roth and M. A. O. Sotomayor|volume=30}}</ref>

The '''Gale–Shapley algorithm''' involves a number of "rounds" (or "[[iteration]]s"):

Line 23:

* This process is repeated until everyone is engaged.

The runtime complexity of this algorithm is <math>O(n^2)</math> where <math>n</math> is the number of men or women.<ref name="IwamaMiyazaki2008">{{cite journal|last1=Iwama|first1=Kazuo|author1-link=Kazuo Iwama (computer scientist)|last2=Miyazaki|first2=Shuichi|title=A Survey of the Stable Marriage Problem and Its Variants|year=2008|pages=131–136|doi=10.1109/ICKS.2008.7|journal=International Conference on Informatics Education and Research for Knowledge-Circulating Society (icksIcks 2008)|isbn=978-0-7695-3128-1|hdl=2433/226940|s2cid=10642344|url=https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/226940/1/ICKS.2008.7.pdf|hdl-access=free}}</ref> Since the input preference lists also have size proportional to <math>n^2</math>, the runtime is linear in the input size.

This algorithm guarantees that:

Line 67:

| title = Machiavelli and the Gale–Shapley algorithm

| volume = 88

| year = 1981| jstor = 2321753 }}</ref> However, it is possible for some coalition to misrepresent their preferences such that some men are better-off and the other men retain the same partner.<ref>{{cite conference

| last = Huang | first = Chien-Chung

| editor1-last = Azar | editor1-first = Yossi

Line 84:

==Implementation in software packages==

*[[R (programming language)|R]]: The Gale–Shapley algorithm (also referred to as deferred-acceptance algorithm) for the stable marriage and the [[Hospital resident|hospitals/residents problem]] is available as part of the <code>matchingMarkets</code><ref>{{cite journal|last=Klein|first=T.|year=2015|title=Analysis of Stable Matchings in R: Package matchingMarkets|url=http://cran.at.r-project.org/web/packages/matchingMarkets/vignettes/matching.pdf|journal=Vignette to R Package MatchingMarkets}}</ref><ref>{{cite web|url=http://cran.at.r-project.org/web/packages/matchingMarkets/|title=matchingMarkets: Analysis of Stable Matchings|date=12 January 2020|work=R Project}}</ref> and <code>matchingR</code><ref>{{cite web|url=https://cran.r-project.org/web/packages/matchingR/|title=matchingR: Matching Algorithms in R and C++|date=25 May 2021|work=R Project}}</ref> packages.

*[[Application programming interface|API]]: The MatchingTools API provides a free application programming interface for the Gale–Shapley algorithm.<ref>{{cite web|url=https://matchingtools.com|title=MatchingTools API}}</ref>

*[[Python (programming language)|Python]]: The Gale–Shapley algorithm is included along with several other well-known matching game algorithms in the <code>matching</code> library,<ref>{{cite journal | firstfirst1=H. | lastlast1=Wilde | first2=V. | last2=Knight | first3=J. | last3=Gillard | title=Matching: A Python library for solving matching games | journal=Journal of Open Source Software | year=2020 | volume=5 | issue=48 | page=2169 | doi=10.21105/joss.02169| bibcode=2020JOSS....5.2169W | doi-access=free }}</ref> and <code>QuantEcon/MatchingMarkets.py</code> package<ref>{{cite web|url=https://github.com/QuantEcon/MatchingMarkets.py|title=matchingMarkets.py|date=27 September 2021|work=Python package}}</ref> includes several others for generalized matching games.

*[[MATLAB]]: The Gale–Shapley algorithm is implemented in the <code>assign2DStable</code> function that is part of the [[United States Naval Research Laboratory |United States Naval Research Laboratory's]] free Tracker Component Library.<ref>{{cite web|url=https://github.com/USNavalResearchLaboratory/TrackerComponentLibrary|title=Tracker Component Library|work=Matlab Repository|access-date=January 5, 2019}}</ref>