Revision as of 06:26, 19 April 2024 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,587 edits Undid revision 1219675419 by NT1036 (talk) with respect to you and with respect to your contribution here, what meaning do you think that inserting the phrase "with respect to" clarifies or adds, with respect to the existing wording of the article? Tag: Undo ← Previous edit		Revision as of 22:25, 24 May 2024 edit undo 98.15.76.222 (talk) →Optimality of the solution Next edit →
Line 50: ==Optimality of the solution== {{main\|Lattice of stable matchings}} There may be many stable matchings for the same system of preferences. This raises the question: which matching is returned by the Gale–Shapley algorithm? Is it the matching better for applicants, for employers, or ~~the~~an intermediate one? As it turns out, the Gale–Shapley algorithm in which employers make offers to applicants always yields the same stable matching (regardless of the order in which job offers are made), and its choice is the stable matching that is the ''best for all employers'' and ''worst for all applicants'' among all stable matchings.{{r\|jeffe}} In a reversed form of the algorithm, each round consists of unemployed applicants writing a single job application to their preferred employer, and the employer either accepting the application (possibly firing an existing employee to do so) or rejecting it. This produces a matching that is best for all applicants and worst for all employers among all stable matchings. These two matchings are the top and bottom elements of the [[lattice of stable matchings]].{{r\|knuth}}

Gale–Shapley algorithm: Difference between revisions