Gale–Shapley algorithm: Difference between revisions

Revision as of 02:22, 14 January 2024

Revision as of 02:23, 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: No unmatched pair of an applicant ''X'' and an employer ''Y'' can be unstable. If ''Y'' makes an offer to ''X'', then ''X'' would only reject ''Y'' after receiving an even better offer, so it would be impossible for ''X'' to prefer ''Y'' over their assigned match. And if ''Y'' does not make an offer to ''X'', it can only be because ''Y'' stopped making offers after being accepted by a better applicant, so it would be impossible for ''Y'' to prefer ''X'' to their assigned match. ThereforeIn either case, no''X'' suchand pair''Y'' isdo possiblenot form an unstable pair.{{r|jeffe}}

==Optimality of the solution==