Content deleted Content added
Added corollary of sex-specific optimality; optimality for one sex implies worst possible outcome for the other |
Adding short description: "Algorithm for solving the stable matching problem" (Shortdesc helper) |
||
Line 1:
{{Short description|Algorithm for solving the 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.
| |||