Algo: Stable Matching (Gale-Shapley Algorithm)

How do you fairly match medical graduates to residency programs or students to schools when everyone has different preferences? This is the classic stable matching problem, a cornerstone of algorithmic design with profound real-world impact. The Gale-Shapley algorithm provides an elegant, efficient solution that guarantees a stable outcome, preventing the kind of chaotic re-matching that can occur when two participants would rather be with each other than their assigned partners.

Understanding the Stable Matching Problem

Imagine two equally sized groups: proposers (like job applicants) and receivers (like employers). Each person in both groups has a ranked preference list for all members of the opposite group. A matching is a one-to-one pairing between the groups. A matching is stable if there is no blocking pair. A blocking pair is two individuals (one from each group) who are not matched to each other but who would both prefer to be matched together over their current assignments.

Consider a simple party with two men and two women. If the matching pairs Man A with Woman Y and Man B with Woman X, but Man A prefers Woman X and Woman X prefers Man A, then (Man A, Woman X) is a blocking pair, and the entire matching is unstable. The goal is to find a matching with no such pairs. The Gale-Shapley algorithm, developed by David Gale and Lloyd Shapley in 1962, does exactly this.

The Gale-Shapley Algorithm: Step-by-Step

The algorithm proceeds in rounds until everyone is matched. One group is designated as the proposers (e.g., medical students) and the other as the receivers (e.g., hospitals). This designation is crucial and leads to a powerful property we'll discuss later. Here is the precise procedure:

1. Initialization: All proposers and receivers are initially free (unmatched).
2. Proposal Phase: While there exists a free proposer who has not proposed to every receiver, that proposer $p$ proposes to their highest-ranked receiver $r$ to whom they have not yet proposed.
3. Response Phase: The receiver $r$ considers the proposal.

• If $r$ is free, $r$ tentatively accepts, and $(p,r)$ become matched.
• If $r$ is already matched to some proposer $p^{\prime }$, then $r$ compares $p$ and $p^{\prime }$ based on her preference list.
• If $r$ prefers $p^{\prime }$ (their current partner), the proposal is rejected, and $p$ remains free.
• If $r$ prefers $p$, the proposal is accepted. $r$ breaks the match with $p^{\prime }$ (who becomes free), and forms a new tentative match with $p$.

1. Termination: The algorithm terminates when no free proposer remains who has a receiver left to propose to. All tentative matches become final.

This can be summarized in pseudocode:

Initialize all m ∈ M and w ∈ W to free
while ∃ free man m who still has a woman w to propose to:
    w = first woman on m's list to whom he has not yet proposed
    if w is free:
        (m, w) become engaged
    else:
        let m' be w's current partner
        if w prefers m to m':
            m' becomes free
            (m, w) become engaged
        else:
            m remains free
Output the stable matching of engagements.

Proving Stability and Optimality

A key strength of this algorithm is that its correctness and properties can be rigorously proven.

Proof of Stability: The algorithm always produces a stable matching. Assume, for contradiction, that a blocking pair $(m,w)$ exists in the final matching. This means $m$ prefers $w$ to his final partner, and $w$ prefers $m$ to her final partner. Since $m$ prefers $w$, he must have proposed to $w$ before proposing to his final partner (because he proposes in order of preference). When he proposed, $w$ either rejected him immediately (preferring her partner at that time) or accepted him and later left him for someone she preferred more. In either case, the partner $w$ ended up with is someone she preferred to $m$ at the moment of decision, and because receivers only trade up, her final partner must be someone she prefers at least as much as the partner she had when $m$ proposed. Therefore, she cannot prefer $m$ to her final partner. This contradiction proves no blocking pair can exist.

Proposer-Optimal/Receiver-Pessimal Outcome: The algorithm yields a matching that is optimal for every proposer and pessimal for every receiver, among all possible stable matchings. This means:

• Proposer-Optimal: Every proposer gets the best possible partner they could have in any stable matching. No other stable matching exists where any proposer gets a partner they prefer more.
• Receiver-Pessimal: Every receiver gets the worst possible partner they could have in any stable matching. No other stable matching exists where any receiver gets a partner they prefer less.

This profound asymmetry stems entirely from which group does the proposing. If you swap the roles, you get the receiver-optimal/proposer-pessimal stable matching.

Complexity Analysis: $O(n^2)$

The algorithm is remarkably efficient. Let $n$ be the number of proposers (and also the number of receivers). In the worst case, each proposer will propose to every receiver exactly once before being accepted. A proposal involves looking up preferences and potentially breaking an engagement, which are constant-time $O(1)$ operations. Therefore, with $n$ proposers each making at most $n$ proposals, the total number of operations is on the order of $n^2$. We say the algorithm runs in $O(n^2)$ time. This is considered efficient for a problem where the input itself (the $2n$ preference lists, each of length $n$) is of size $O(n^2)$.

Applications: From Residencies to Admissions

The Gale-Shapley algorithm isn't just theoretical; it orchestrates life-changing systems.

• Medical Residency Assignment (NRMP): The National Resident Matching Program uses a version of this algorithm to match medical school graduates to hospital residency programs. Here, students are the proposers, leading to a student-optimal stable match. The system has successfully eliminated the prior chaotic, unstable "exploding offer" market.
• College Admissions and School Choice: Some public school choice programs and university admission systems in various countries use stable matching algorithms. For example, matching students to high schools in New York City or Boston was reformed using these principles to produce fairer, more efficient outcomes that respect family preferences while ensuring system-wide stability.

In these applications, defining who is the proposer is a critical policy decision, as it determines which side of the market receives the most favorable outcome.

Common Pitfalls

1. Misunderstanding Optimality: A common error is thinking the algorithm finds the "best overall" matching. It finds a stable matching that is optimal for one side. There can be many stable matchings for a given set of preferences. The proposer-optimal and receiver-optimal matchings are often different.
2. Ignoring the Impact of Proposer/Receiver Designation: The roles are not interchangeable. The group chosen as the proposer gets the favorable optimal outcome. Flipping the roles flips the optimality property. This must be carefully considered in real-world implementations based on equity goals.
3. Incorrect Termination Condition: The algorithm terminates not when everyone is matched, but when no free proposer has any receiver left to propose to. In a valid, complete instance, these are equivalent, but it's the correct formal condition.
4. Assuming Preference Lists Must Be Complete: The classic algorithm assumes every proposer ranks every receiver and vice versa. Real-world adaptations must handle incomplete lists (e.g., a student only ranking 5 of 100 schools), which can result in some participants remaining unmatched in the final stable matching.

Summary

• The Gale-Shapley algorithm solves the stable matching problem by iteratively having proposers make offers and receivers accept or reject them based on their preference lists, guaranteeing no blocking pairs exist in the final matching.
• It produces a proposer-optimal (and receiver-pessimal) stable matching, a property determined solely by which group is assigned the active proposing role.
• The algorithm runs efficiently in $O(n^2)$ time, where $n$ is the number of participants in each group.
• Its real-world applications are significant, most famously in the National Resident Matching Program (NRMP) for placing medical graduates, ensuring a fair and orderly process.
• Successfully implementing or analyzing this algorithm requires careful attention to the definition of roles, the proof of stability, and the understanding that it finds one of potentially many stable matchings with specific biased properties.