Gale–Shapley algorithm: Difference between revisions

Revision as of 20:01, 14 January 2024

Revision as of 14:10, 15 January 2024

Line 24:

In 1962, [[David Gale]] and [[Lloyd Shapley]] proved that, for any equal number of participants of each type, it is always possible to find a matching in which all pairs are stable. They presented an algorithm to do so.{{r|gale-shapley|mairson}} In 1984, [[Alvin E. Roth]] observed that essentially the same algorithm had already been in practical use since the early 1950s, as the "Boston Pool algorithm" used by the [[National Resident Matching Program]].{{r|roth|bergstrom}}

The '''Gale–Shapley algorithm''' involves a number of "rounds" (or "[[iteration]]s"). In terms of job applicants and employers, it can be expressed as follows:{{r|jeffe}}

* In each round, one or more employers with open job positions each make a job offer to the applicant they prefer, among the ones they have not yet already made an offer to.

* Each applicant who has received an offer evaluates it against their current position (if they have one). If the applicant is not yet employed, or if they receive an offer from an employer they like better than their current employer, they accept the best new offer and become matched to the new employer (possibly leaving a previous employer with an open position). Otherwise, they reject the new offer.