Gale–Shapley Algorithm

In mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm or propose-and-reject algorithm) is an algorithm for finding a solution to the stable matching problem, named for David Gale and Lloyd Shapley. It takes polynomial time, and the time is linear in the size of the input to the algorithm. It is a truthful mechanism from the point of view of the proposing participants, for whom the solution will always be optimal.

Background

The stable matching problem, in its most basic form, takes as input equal numbers of two types of participants ( medical students and internships, for example), and an ordering for each participant giving their preference for whom to be matched to among the participants of the other type. A stable matching always exists, and the algorithmic problem solved by the Gale–Shapley algorithm is to find one. A matching is ''not'' stable if:

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.

Solution

In 1962, David Gale and Lloyd Shapley proved that, for any equal number of participants of each type, it is always possible to find a matching in which all pairs are stable. They presented an algorithm to do so. In 1984, Alvin E. Roth observed that essentially the same algorithm had already been in practical use since the early 1950s, in the National Resident Matching Program.

The Gale–Shapley algorithm involves a number of "rounds" (or " iterations"). In terms of job applicants and employers, it can be expressed as follows:
* In each round, any subset of the employers with open job positions makes a job offer to the applicant they prefer, among the ones they have not yet already made an offer to.
* Each applicant who has received an offer evaluates it against their current position (if they have one). If the applicant is not yet employed, or if they receive an offer from an employer they like better than their current employer, they accept the new offer and become matched to the new employer (possibly leaving a previous employer with an open position). Otherwise, they reject the new offer.
* This process is repeated until everyone is employed.

The runtime complexity of this algorithm is $O(n^2)$ where $n$ is the number of participants of each type. Since the input preference lists also have size proportional to $n^2$, the runtime is linear in the input size.

This algorithm guarantees that:

; Everyone gets matched : At the end, there cannot be an applicant and employer both unmatched. An employer left unmatched at the end of the process must have made an offer to all applicants. But an applicant who receives an offer remains employed for the rest of the process, so there can be no unemployed applicants. Since the numbers of applicants and job openings is equal, there can also be no open positions remaining.
; The matches are stable : If an applicant X and an employer Y could form an unstable pair, Y would have made an offer to X prior to the offer made by Y to their actual match. But X would have accepted this offer and kept it over the offer they ended up with. Therefore, no such pair is possible.

Algorithm

algorithm stable_matching is
Initialize ''m'' ∈ M and ''w'' ∈ W to ''free''
while ∃ ''free'' man ''m'' who has a woman ''w'' to propose to do
w := first woman on m's list to whom m has not yet proposed
if ∃ some pair (m', w) then
if w prefers m to m' then
m' becomes ''free''
(m, w) become ''engaged''
end if
else
(m, w) become ''engaged''
end if
repeat

Optimality of the solution

The existence of different stable matchings raises the question: which matching is returned by the Gale–Shapley algorithm? Is it the matching better for applicants, for employers, or the intermediate one? As it turns out, the Gale–Shapley algorithm in which employers make offers to applicants yields a stable matching that is the ''best for all employers'' and ''worst for all applicants'' among all stable matchings.

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.

In both forms of the algorithm, one group of participants proposes matches, and the other group decides whether to accept or reject each proposal. The matching is always best for the group that makes the propositions, and worst for the group that decides how to handle each proposal.

Strategic considerations

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

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.

Implementation in software packages

* R: The Gale–Shapley algorithm (also referred to as deferred-acceptance algorithm) for the stable marriage and the hospitals/residents problem is available as part of the matchingMarkets and matchingR packages.
* R: Implementation in an R Shiny tool designed for student placement in university programs with limited enrollment (does not use the packages above)
*API: The MatchingTools API provides a free application programming interface for the Gale–Shapley algorithm.
*Python: The Gale–Shapley algorithm is included along with several other well-known matching game algorithms in the matching library, and QuantEcon/MatchingMarkets.py package includes several others for generalized matching games.
*MATLAB: The Gale–Shapley algorithm is implemented in the assign2DStable function that is part of the United States Naval Research Laboratory's free Tracker Component Library.

Recognition

Shapley and Roth were awarded 2012 Nobel Memorial Prize in Economic Sciences "for the theory of stable allocations and the practice of market design"; Gale had died in 2008.

See also

*Deferred-acceptance auction

References

External links

Gale–Shapley JavaScript Demonstration

{{DEFAULTSORT:Gale-Shapley algorithm
Stable matching
Lloyd Shapley
Algorithms