Gale–Shapley algorithm: Difference between revisions

Revision as of 02:27, 14 January 2024

Revision as of 02:28, 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 ''X'' cannot prefer ''Y'' to their assigned match. And if ''Y'' does not make an offer to ''X'', it can only be because ''Y'' must have stopped making offers after being accepted by a better applicant, so ''Y'' cannot prefer ''X'' to their assigned match. In either case, ''X'' and ''Y'' do not form an unstable pair.{{r|jeffe}}

==Optimality of the solution==