Gale–Shapley algorithm: Difference between revisions

Content deleted Content added
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 unstableunmatched pair of an applicant ''X'' and an employer ''Y'' can existbe unstable. If such a pair could exist, ''Y'' would have mademakes an offer to ''X'', becausethen ''YX'' would preferonly reject ''XY'' toafter theirreceiving assignedan even matchbetter offer, andso becauseit offerswould arebe madeimpossible infor preference''X'' orderto prefer ''Y'' over their assigned match. ButAnd if ''XY'' receiveddoes not make an offer fromto ''YX'', it can only be because ''XY'' wouldstopped havemaking keptoffers after being accepted by a better applicant, so it inwould preferencebe impossible for ''Y'' to theprefer offer''X'' theyto endedtheir upassigned withmatch. Therefore, no such pair is possible.{{r|jeffe}}
 
==Optimality of the solution==