Content deleted Content added
"unmatched" was wrong here |
|||
| (7 intermediate revisions by 5 users not shown) | |||
Line 6:
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 72:
*[[Deferred-acceptance auction]]
*[[Stable roommates problem]]
*[[Kolkata Paise Restaurant Problem]]
==References==
Line 99 ⟶ 100:
| publisher = CRC Press
| title = Operations Research: A Practical Introduction
|
| year = 2000}}</ref>
Line 144 ⟶ 145:
| last = Erickson | first = Jeff
| contribution = 4.5 Stable matching
| contribution-url
| access-date = 2023-12-19
| date = June 2019
Line 159 ⟶ 160:
| ___location = Montréal, Quebec
| title = Mariages stables et leurs relations avec d'autres problèmes combinatoires
|
| year = 1976}} See in particular Problem 6, pp. 87–94.</ref>
Line 175 ⟶ 176:
| journal = The Brandeis Review
| title = The stable marriage problem
|
| volume = 12
| year = 1992}}</ref>
| |||