Gale–Shapley algorithm: Difference between revisions

Revision as of 02:09, 30 January 2024

Revision as of 07:28, 30 January 2024

Line 58:

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:

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

| title = Economics Nobel honors perfect match

| doi = 10.1126/science.338.6105.314

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

Line 196 ⟶ 195:

| pages = 909–912

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

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

<ref name=sisterhood>{{cite journal