Gale–Shapley algorithm: Difference between revisions

Revision as of 20:09, 15 January 2024

Latest revision as of 04:24, 1 August 2025

(23 intermediate revisions by 14 users not shown)

Line 1:

{{good article}}

{{Short description|Procedure for finding a stable matching}}

{{goodGood article}}

{{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.

The stable matching problem seeks to pair up equal numbers of participants of two types, using preferences from each participant. The pairing must be stable: no pair of matched participants should mutually prefer each other to their assigned match. In each round of the Gale–Shapley algorithm, unmatched participants of one type propose a match to the next participant on their preference list. Each proposal is accepted if its recipient prefers it to their current match. The resulting procedure is a [[truthful mechanism]] from the point of view of the proposing participants, who receive their most-preferred pairing consistent with stability. In contrast, the recipients of proposals receive their least-preferred pairing. The algorithm can be implemented to run in time quadratic in the number of participants, and [[linear time|linear]] in the size of the input to the algorithm.

The stable matching problem, and the Gale–Shapley algorithm solving it, have widespread real-world applications, including matching American medical students to residencies and French university applicants to schools. For more, see {{slink|Stable marriage problem|Applications}}.

Line 20 ⟶ 21:

In other words, a matching is stable when there is no pair (''A'', ''B'') where both participants prefer each other to their matched partners. If such a pair exists, the matching is not stable, in the sense that the members of this pair would prefer to leave the system and be matched to each other, possibly leaving other participants unmatched. A stable matching always exists, and the algorithmic problem solved by the Gale–Shapley algorithm is to find one.{{r|gusfield-irving}}

The stable matching problem has also been called the ''stable marriage problem'', using a metaphor of marriage between men and women, and many sources describe the Gale–Shapley algorithm in terms of [[Marriage proposal|marriage proposals]]. However, this metaphor has been criticized as both sexist and unrealistic: the steps of the algorithm do not accurately reflect typical or even stereotypical human behavior.{{r|wagner|giagkousi}}

==Solution==

Line 35 ⟶ 36:

*A [[Set (abstract data type)|set]] of employers with unfilled positions

*A one-dimensional [[Array (data structure)|array]] indexed by employers, specifying the preference index of the next applicant to whom the employer would send an offer, initially 1 for each employer

*A two-dimensional array indexed by an employer and a number <math>i</math> from 1 to <math>n</math>, naming the applicant who is each employer's {{nowrap|<math>i</math>th}} preference

*A one-dimensional array indexed by applicants, specifying their current employer, initially a [[sentinel value]] such as 0 indicating they are unemployed

*A two-dimensional array indexed by an applicant and an employer, specifying the position of that employer in the applicant's preference list

*A two-dimensional array indexed by an employer and a number <math>i</math> from 1 to <math>n</math>, naming the applicant who is each employer's {{nowrap|<math>i</math>th}} preference

Setting up these data structures takes <math>O(n^2)</math> time. With these structures it is possible to find an employer with an unfilled position, make an offer from that employer to their next applicant, determine whether the offer is accepted, and update all of the data structures to reflect the results of these steps, in constant time per offer. Once the algorithm terminates, the resulting matching can be read off from the array of employers for each applicant. There can be <math>O(n^2)</math> offers before each employer runs out of offers to make, so the total time is <math>O(n^2)</math>.{{r|kt}}

Line 49 ⟶ 50:

==Optimality of the solution==

{{main|Lattice of stable matchings}}

There may be many stable matchings for the same system of preferences. This raises the question: which matching is returned by the Gale–Shapley algorithm? Is it the matching better for applicants, for employers, or thean intermediate one? As it turns out, the Gale–Shapley algorithm in which employers make offers to applicants always yields the same stable matching (regardless of the order in which job offers are made), and its choice is the stable matching that is the ''best for all employers'' and ''worst for all applicants'' among all stable matchings.{{r|jeffe}}

In a reversed form of the algorithm, each round consists of unemployed applicants writing a single job application to their preferred employer, and the employer either accepting the application (possibly firing an existing employee to do so) or rejecting it. This produces a matching that is best for all applicants and worst for all employers among all stable matchings. These two matchings are the top and bottom elements of the [[lattice of stable matchings]].{{r|knuth}}

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 makegive thean agent a worse-off assignment. Moreover, even after thean agent sees the final matching, he/shethey 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 journalweb |last=Fernandez |first=Marcelo Ariel |date=2020-07-July 31, 2020 |title=Deferred acceptance and regret-free truth-telling |url=https://ideas.repec.org//p/jhu/papers/65832.html |journaltype=Economics Working Paper Archive paper|languagepublisher=enJohns Hopkins University Department of Economics}}</ref>

==Generalizations==

Line 66 ⟶ 67:

==Recognition==

Shapley and Roth were awarded the 2012 [[Nobel Memorial Prize in Economic Sciences]] "for the theory of stable allocations and the practice of [[market design]]". Gale had died in 2008, making him ineligible for the prize.{{r|nobel}}

==See also==

*[[Deferred-acceptance auction]]

*[[Stable roommates problem]]

*[[Kolkata Paise Restaurant Problem]]

==References==

Line 98 ⟶ 100:

| publisher = CRC Press

| title = Operations Research: A Practical Introduction

| url = https://books.google.com/books?id=CbFwJLHpX7sC&pg=PA102

| year = 2000}}</ref>

Line 143 ⟶ 145:

| last = Erickson | first = Jeff

| contribution = 4.5 Stable matching

| contribution-url = https://jeffe.cs.illinois.edu/teaching/algorithms/book/04-greedy.pdf

| access-date = 2023-12-19

| date = June 2019

Line 158 ⟶ 160:

| ___location = Montréal, Quebec

| title = Mariages stables et leurs relations avec d'autres problèmes combinatoires

| url = https://www-cs-faculty.stanford.edu/~knuth/mariages-stables.pdf

| year = 1976}} See in particular Problem 6, pp. 87–94.</ref>

Line 174 ⟶ 176:

| journal = The Brandeis Review

| title = The stable marriage problem

| url = https://www1.cs.columbia.edu/~evs/intro/stable/writeup.html

| volume = 12

| year = 1992}}</ref>

Line 184 ⟶ 186:

| date = October 15, 2012

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

| title = Economics Nobel honors perfectmatchmaking matchfinesse | volume = 338

| issue = 6105

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

| page = 314

| doi = 10.1126/science.338.6105.314

| pmid = 23087221}}</ref>

<ref name=roth>{{cite journal