Revision as of 21:45, 10 November 2020 edit 2a02:a210:2d03:ff80:899c:6810:2fb:68f5 (talk) gale-shapley is quadratic, not linear Tag: Reverted ← Previous edit		Revision as of 21:46, 10 November 2020 edit undo 2a02:a210:2d03:ff80:899c:6810:2fb:68f5 (talk) typo in lede Tag: Reverted Next edit →
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 [[quadratic time\|~~qudratic~~quadratic]] 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==

Gale–Shapley algorithm: Difference between revisions