Gale–Shapley algorithm: Difference between revisions

Revision as of 19:24, 25 January 2022

Revision as of 19:24, 25 January 2022

Line 1:

{{Short description|Algorithm for solvingfinding thea stable matching problem}}

In [[mathematics]], [[economics]], and [[computer science]], the '''Gale–Shapley algorithm''' (also known as the '''deferred acceptance algorithm''' or '''propose-and-reject algorithm''') is an [[algorithm]] for finding a solution to the [[stable matching problem]], named for [[David Gale]] and [[Lloyd Shapley]] who had described it as solving both the ''college admission problem'' and the ''stable marriage problem''.

It takes [[polynomial time]], and the time is [[linear time|linear]] in the size of the input to the algorithm. It is a [[truthful mechanism]] from the point of view of the proposing participants, for whom the solution will always be optimal.