Gale–Shapley algorithm: Difference between revisions

Revision as of 08:35, 26 November 2019

Revision as of 22:05, 2 December 2019

Line 32:

==Algorithm==

'''functionalgorithm''' stable_matching {'''is'''

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

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

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

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

(m, w) become ''engaged''

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

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

m' becomes ''free''

(m, w) become ''engaged''

'''else'''

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

'''end if'''

}

'''end if'''

}

'''repeat'''

==Optimality of the solution==