Stable Marriage Problem

The Stable Marriage Problem is the historical name for a matching problem between two groups with ranked preferences. Today, it is often explained more neutrally as a stable matching problem between applicants and programs, students and schools, or any two-sided market.

The classic solution is the Gale-Shapley deferred acceptance algorithm, which always produces a stable matching.

A Simple Goal

We want a matching with no blocking pair: no applicant and program that would both prefer each other over their assigned match.

If such a pair exists, the matching is unstable because those two sides would rather deviate.

Interactive Demo

Algorithm Explanation

At a high level, the Gale-Shapley algorithm works like this:

1. Everyone starts unmatched.
2. Each unmatched applicant proposes to the highest-ranked program they have not yet tried.
3. Each program tentatively keeps its favorite proposal so far and rejects the rest.
4. Rejected applicants move to their next choice.
5. The process repeats until no more proposals are needed.

The word tentatively matters. Programs may replace an earlier tentative match if a better proposal arrives later.

Why the Result Is Stable

Gale-Shapley prevents blocking pairs because:

• applicants propose in order of preference
• programs only trade up, never down
• once a program rejects an applicant, it will never want that applicant later

So when the algorithm ends, there is no unmatched pair that would rather be together.

Time Complexity

For $n$ participants on each side:

• each applicant proposes to each program at most once
• there are at most $n^2$ proposals

Time complexity: O(n^2)
Space complexity: O(n^2) to store preferences

Applications

• Medical residency matching
• College admissions and school choice
• Job matching platforms
• Organ exchange systems

Historical Note

The historical title comes from the original 1962 paper, but the algorithm is now used far beyond marriage-style examples.

Key Papers

• Gale, D., & Shapley, L. S. (1962). College Admissions and the Stability of Marriage.
  https://www.jstor.org/stable/2312726
• Roth, A. E. (1984). The Evolution of the Labor Market for Medical Interns and Residents.
  https://www.jstor.org/stable/1837229