Revision as of 21:46, 10 November 2020 edit 2a02:a210:2d03:ff80:899c:6810:2fb:68f5 (talk) typo in lede Tag: Reverted ← Previous edit		Revision as of 22:02, 10 November 2020 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,646 edits Undo. The time is quadratic in the number of participants, but so is the input size. So the statement that the time is linear in input size is correct. Tag: Undo 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~~linear time\|~~quadratic~~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==

Gale–Shapley algorithm: Difference between revisions