Gale–Shapley algorithm: Difference between revisions

Revision as of 01:56, 14 January 2024

Revision as of 02:02, 14 January 2024

Line 42:

This algorithm guarantees that:

; Everyone gets matched: At the end, there cannot be an applicant and employer both unmatched. An employer left unmatched at the end of the process must have made an offer to all applicants. But an applicant who receives an offer remains employed for the rest of the process, so there can be no unemployed applicants. Since the numbers of applicants and job openings are equal, there can also be no open positions remaining.{{r|jeffe}}

; The matches are stable: IfNo unstable pair of an applicant ''X'' and an employer ''Y'' couldcan formexist. anIf unstablesuch a pair could exist, ''Y'' would have made an offer to their preferred match ''X'', beforebecause making''Y'' anotherwould offerprefer ''X'' to their actualassigned match, and because offers are made in preference order. But if ''X'' wouldreceived havean acceptedoffer thisfrom offer''Y'', and''X'' would have kept it in preference to the offer they ended up with. Therefore, no such pair is possible.{{r|jeffe}}

==Optimality of the solution==