Content deleted Content added
see also Deferred-acceptance auction |
→top: namesakes |
||
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 [[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.
| |||