Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Gale–Shapley algorithm
open-in-new
<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, <a href="/facts/Economics/HYctA2Dn">economics</a>, and <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm, propose-and-reject algorithm, or Boston Pool algorithm) is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for finding a solution to the <a href="/facts/Stable_matching_problem/tzNRpF1f">stable matching problem</a>. It is named for <a href="/facts/David_Gale/RQy8c24N">David Gale</a> and <a href="/facts/Lloyd_Shapley/WoY0lyI3">Lloyd Shapley</a>, who published it in 1962, although it had been used for the <a href="/facts/National_Resident_Matching_Program/LlpBtGe1">National Resident Matching Program</a> since the early 1950s. Shapley and <a href="/facts/Alvin_E._Roth/9s8ubcf2">Alvin E. Roth</a> (who pointed out its prior application) won the 2012 <a href="/facts/Nobel_Memorial_Prize_in_Economic_Sciences/8BBwNwre">Nobel Prize in Economics</a> for work including this algorithm. </p><p>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 unmatched 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 <a href="/facts/Truthful_mechanism/mQfERF7h">truthful mechanism</a> 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 <a href="/facts/Linear_time/77T62gmf">linear</a> in the size of the input to the algorithm. </p><p>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 <a href="/facts/Stable_marriage_problem/tzNRpF1f">Stable marriage problem § Applications</a>. </p>