Gale–Shapley algorithm: Difference between revisions

Revision as of 08:21, 4 July 2022

Revision as of 03:01, 27 July 2022

Line 48:

{{main|Lattice of stable matchings}}

[[File:DA-men-optimality.png|thumb|Proof that deferred acceptance is optimal for men]]

The existence of different stable matchings raises the question: which matching is returned by the Gale-ShapleyGale–Shapley algorithm? Is it the matching better for men, for women, or the intermediate one? In the above example, the algorithm converges in a single round on the men-optimal solution because each woman receives exactly one proposal, and therefore chooses that proposal, ensuring that each man has an accepted offer, ending the match.

This is a general fact: the Gale-ShapleyGale–Shapley algorithm in which men propose to women ''always'' yields a stable matching that is the ''best for all men'' and ''worst for all women'' among all stable matchings. Similarly, if the women propose then the resulting matching is the ''best for all women'' and ''worst for all men'' among all stable matchings. These two matchings are the top and bottom elements of the [[lattice of stable matchings]].

To see this, consider the illustration at the right. Let A be the matching generated by the men-proposing algorithm, and B an alternative stable matching that is better for at least one man, say ''m''₀. Suppose ''m''₀ is matched in B to a woman ''w''₁, which he prefers to his match in A. This means that in A, ''m''₀ has visited ''w''₁, but she rejected him (this is denoted by the green arrow from ''m''₀ to ''w''₁). ''w''₁ rejected him in favor of some man that she prefers, say ''m''₂. So in B, ''w''₁ is matched to ''m''₀ but "yearns" (wants but unmatched) for ''m''₂ (this is denoted by the red arrow from ''w''₁ to ''m''₂).

Line 85:

==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.

* [[R (programming language)|R]]: Implementation in an [[RStudio|R Shiny tool]] <ref>{{cite web|url=https://rgrasman.shinyapps.io/MasterTrackAdmission/|title=Optimal Master Track Allocation|date=30 Dec 2017}}</ref> designed for student placement in university programs with limited enrollment (does not use the packages above)

*[[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 | first1=H. | last1=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.

Line 91:

==Recognition==

Shapley and Roth were awarded 2012 [[Nobel Memorial Prize in Economic Sciences]] "for the theory of stable allocations and the practice of [[market design]]"; Gale had died in 2008.<ref>{{cite web|url=https://www.science.org/content/article/economics-nobel-honors-perfect-match|title=Economics Nobel Honors Perfect Match|work=Science Mag|access-date=December 5, 2020}} </ref>

==See also==