Gale–Shapley algorithm: Difference between revisions

Revision as of 02:25, 6 May 2021

Revision as of 17:26, 16 May 2021

Line 1:

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. Depending on how it is used, it can find either the solution that is optimal for the participants on one side of the matching, or for the participants on the other side. It is a [[truthful mechanism]] from the point of view of the participants for whom it provides the optimal solution.

==Background==