Gale–Shapley algorithm: Difference between revisions

Revision as of 21:25, 14 December 2024

Revision as of 21:25, 14 December 2024

Line 1:

{{Short description|Procedure for finding a stable matching}}{{MoreGood sourcesarticle}}{{Use mdy dates|cs1-dates=ly|date=December 20242023}}{{Use list-defined references|date=December 2023}}{{bots|deny=Citation bot}}

{{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.