Content deleted Content added
No edit summary Tags: Reverted Visual edit |
Undo runningheadertemplatestogetheronasingleline and unexplained removal of relevant wikilinks |
||
Line 1:
{{Short description|Procedure for finding a stable matching}}
{{Good article}} {{Use mdy dates|cs1-dates=ly|date=December 2023}} {{Use list-defined references|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.
Line 22 ⟶ 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}}
| |||