Content deleted Content added
No edit summary Tags: Reverted Visual edit |
"unmatched" was wrong here |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 1:
{{Short description|Procedure for finding a stable matching}}
{{ {{Use mdy dates|cs1-dates=ly|date=December 2023}}
{{bots|deny=Citation bot}}
In [[mathematics]], [[economics]], and [[computer science]], the '''Gale–Shapley algorithm''' (also known as the '''deferred acceptance algorithm''',{{r|roth}} '''propose-and-reject algorithm''',{{r|carter-price}} or '''Boston Pool algorithm'''{{r|roth}}) is an [[algorithm]] for finding a solution to the [[stable matching problem]]. It is named for [[David Gale]] and [[Lloyd Shapley]], who published it in 1962, although it had been used for the [[National Resident Matching Program]] since the early 1950s. Shapley and [[Alvin E. Roth]] (who pointed out its prior application) won the 2012 [[Nobel Memorial Prize in Economic Sciences|Nobel Prize in Economics]] for work including this algorithm.
The stable matching problem seeks to pair up equal numbers of participants of two types, using preferences from each participant. The pairing must be stable: no pair of matched participants should mutually prefer each other to their assigned match. In each round of the Gale–Shapley algorithm, unmatched participants of one type propose a match to the next participant on their preference list. Each proposal is accepted if its recipient prefers it to their current match. The resulting procedure is a [[truthful mechanism]] from the point of view of the proposing participants, who receive their most-preferred pairing consistent with stability. In contrast, the recipients of proposals receive their least-preferred pairing. The algorithm can be implemented to run in time quadratic in the number of participants, and [[linear time|linear]] in the size of the input to the algorithm.
The stable matching problem, and the Gale–Shapley algorithm solving it, have widespread real-world applications, including matching American medical students to residencies and French university applicants to schools. For more, see {{slink|Stable marriage problem|Applications}}.
Line 24 ⟶ 25:
==Solution==
[[File:Gale-Shapley.gif|thumb|upright=1.35|Animation showing an example of the Gale–Shapley algorithm]]
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}}
Line 71 ⟶ 72:
*[[Deferred-acceptance auction]]
*[[Stable roommates problem]]
*[[Kolkata Paise Restaurant Problem]]
==References==
| |||