Content deleted Content added
→Applications: applications are mentioned earlier as part of other sections and I don't think this one is significant compared to the ones that are already mentioned |
Erel Segal (talk | contribs) No edit summary |
||
Line 56:
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 make the agent worse-off. Moreover, even after the agent sees the final matching, he/she cannot deduce a strategy that would guarantee him/her 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 journal |last=Fernandez |first=Marcelo Ariel |date=2020-07-31 |title=Deferred acceptance and regret-free truth-telling |url=https://ideas.repec.org//p/jhu/papers/65832.html |journal=Economics Working Paper Archive |language=en}}</ref> ==Generalizations==
| |||