Gale–Shapley algorithm: Difference between revisions

Revision as of 19:10, 30 January 2024

Revision as of 20:38, 30 January 2024

Line 3:

{{Use mdy dates|cs1-dates=ly|date=December 2023}}

{{Use list-defined references|date=December 2023}}

{{bots|deny=Citation bot}}

In [[mathematics]], [[economics]], and [[computer science]], the '''Gale–Shapley algorithm''' (also known as the '''deferred acceptance algorithm''',{{r|roth}} '''propose-and-reject algorithm''',{{r|carter-price}} or '''Boston Pool algorithm'''{{r|roth}}) is an [[algorithm]] for finding a solution to the [[stable matching problem]]. It is named for [[David Gale]] and [[Lloyd Shapley]], who published it in 1962, although it had been used for the [[National Resident Matching Program]] since the early 1950s. Shapley and [[Alvin E. Roth]] (who pointed out its prior application) won the 2012 [[Nobel Memorial Prize in Economic Sciences|Nobel Prize in Economics]] for work including this algorithm.

Line 58 ⟶ 59:

The Gale–Shapley algorithm is a [[truthful mechanism]] from the point of view of the proposing side. This means that no proposer can get a better matching by misrepresenting their preferences. Moreover, the Gale–Shapley algorithm is even ''group-strategy proof'' for proposers, i.e., no coalition of proposers can coordinate a misrepresentation of their preferences such that all proposers in the coalition are strictly better-off.{{r|dubins-freedman}} However, it is possible for some coalition to misrepresent their preferences such that some proposers are better-off, and the others retain the same partner.{{r|huang}}

The Gale–Shapley algorithm is non-truthful for the non-proposing participants. Each may be able to misrepresent their preferences and get a better match.{{r|sisterhood}} A particular form of manipulation is ''truncation'': presenting only the topmost alternatives, implying that the bottom alternatives are not acceptable at all. Under complete information, it is sufficient to consider misrepresentations of the form of truncation strategies. However, successful misrepresentation requires knowledge of the other agents' preferences; without such knowledge, misrepresentation can give an agent a worse assignment. Moreover, even after an agent sees the final matching, they cannot deduce a strategy that would guarantee a better outcome in hindsight. This makes the Gale–Shapley algorithm a [[Regret-free mechanism|''regret-free truth-telling mechanism'']]. Moreover, in the Gale–Shapley algorithm, truth-telling is the only strategy that guarantees no regret. The Gale–Shapley algorithm is the only regret-free mechanism in the class of quantile-stable matching mechanisms.<ref>{{Cite journalweb |last=Fernandez |first=Marcelo Ariel |date=July 31, 2020 |title=Deferred acceptance and regret-free truth-telling |journal=Economics Working Paper Archive |url=https://ideas.repec.org//p/jhu/papers/65832.html |type=Working paper|publisher=Johns Hopkins University Department of Economics}}</ref>

==Generalizations==

Line 185 ⟶ 186:

| journal = [[Science (journal)|Science]]

| title = Economics Nobel honors perfect match

| volume = 338

| issue = 6105

| page = 314

| doi = 10.1126/science.338.6105.314

| pmid = 23087221

| url = https://www.science.org/content/article/economics-nobel-honors-perfect-match}}</ref>

Line 200 ⟶ 196:

| pages = 909–912

| title = The origins, history, and design of the resident match

| volume = 289| pmid = 12588278 }}</ref>

<ref name=sisterhood>{{cite journal