Gale–Shapley algorithm: Difference between revisions

Revision as of 08:38, 9 November 2020

Revision as of 21:45, 10 November 2020

Line 1:

In [[mathematics]], [[economics]], and [[computer science]], the '''Gale–Shapley algorithm''' (also known as the '''deferred acceptance algorithm''') is an [[algorithm]] for finding a solution to the [[stable matching problem]], named for [[David Gale]] and [[Lloyd Shapley]].

It takes [[polynomial time]], and the time is [[linearquadratic time|linearqudratic]] 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==