Gale–Shapley algorithm: Difference between revisions

Revision as of 08:10, 25 November 2019

Revision as of 10:38, 25 November 2019

Line 32:

==Algorithm==

'''function''' stableMatchingstable_matching {

Initialize all ''m'' ∈ M and ''w'' ∈ W to ''free''

'''while''' ∃ ''free'' man ''m'' who still has a woman w to propose to {

w = first woman on m's list to whom m has not yet proposed

'''if''' w is ''free''

(m, w) become ''engaged''

'''else''' some pair (m', w) already exists

'''if''' w prefers m to m'

m' becomes ''free''

(m, w) become ''engaged''

'''else'''

(m', w) remain ''engaged''

}

}

Line 90:

*[[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 others for generalized matching problems in the <code>QuantEcon/MatchingMarkets.py</code> package<ref>{{cite web|url=https://github.com/QuantEcon/MatchingMarkets.py|title=matchingMarkets.py|date=|work=Python package}}</ref>

*[[Matlab (programming language)|MatlabMATLAB]]: 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>

==References==