Stable Marriage Problem Solver

What Is the Stable Marriage Problem?

The Stable Marriage Problem (SMP) is a classic combinatorial optimization problem introduced by mathematicians David Gale and Lloyd Shapley in their landmark 1962 paper "College Admissions and the Stability of Marriage." The problem asks: given n men and n women, each with a strict ranking of all members of the opposite group, can we always find a stable matching — and if so, how?

A matching is stable if no unmatched pair (m, w) both prefer each other over their current partners. Such a pair is called a blocking pair — they have a rational incentive to defect from their assigned matches. A matching with no blocking pairs is called stable, and Gale and Shapley proved that a stable matching always exists and can be found efficiently.

The Gale-Shapley Algorithm (Deferred Acceptance)

The Gale-Shapley algorithm, also known as the Deferred Acceptance algorithm, finds a stable matching through an iterative proposal process:

• Round 1: Every free proposer proposes to their top-ranked acceptor.
• Each acceptor: If unengaged, tentatively accepts the proposal. If already engaged, compares the new proposer to the current partner — keeps the preferred one and rejects the other.
• Subsequent rounds: Each rejected proposer proposes to their next preferred acceptor (who hasn't yet rejected them).
• Termination: The algorithm ends when no free proposers remain. All tentative engagements become the final stable matching.

The key insight is deferred acceptance — acceptors never commit permanently, only tentatively holding the best offer received. This guarantees that every proposer eventually finds a match and that the result is stable.

Optimality Theorem

The Gale-Shapley algorithm has a remarkable optimality property proven by Gale and Shapley:

• Proposer-optimal: When proposers initiate, every proposer is matched to their best possible partner across all stable matchings. No proposer can do better in any stable matching.
• Acceptor-pessimal: The same matching is simultaneously the worst stable matching for acceptors — each acceptor gets their worst stable partner.
• Acceptor-optimal: Swapping roles (acceptors propose) gives the best stable matching for acceptors and worst for proposers.

This means there is a fundamental tension: whoever proposes gets a strategic advantage. The structure of all stable matchings forms a distributive lattice — one extreme being the proposer-optimal matching and the other the acceptor-optimal matching.

Time Complexity: O(n²)

The Gale-Shapley algorithm runs in O(n²) time. Each of the n proposers makes at most n proposals over the course of the algorithm (once rejected by an acceptor, they never propose to the same acceptor again). With at most n² total proposals and O(1) processing per proposal (using precomputed rank lookup tables for acceptors), the total work is O(n²). This is optimal since reading the input itself requires O(n²) time.

Real-World Applications

• NRMP Medical Residency Match: The National Resident Matching Program has used a variant of Gale-Shapley since 1952 to match ~40,000 medical graduates to hospital residency programs annually in the USA.
• College Admissions: Many university admission systems use stable matching variants. Gale and Shapley's original paper was titled "College Admissions and the Stability of Marriage."
• School Choice Programs: New York City (since 2003) and Boston use deferred acceptance to assign ~80,000 students to high schools each year.
• Kidney Exchange: Matching organ donors to compatible recipients in kidney exchange programs, where compatibility constraints replace preference rankings.
• Job Markets: Matching candidates to firms in markets like law firm clerkships, economics PhD placement, and medical specialty fellowships.

Gale and Shapley's work was recognized with the 2012 Nobel Memorial Prize in Economic Sciences, awarded to Lloyd Shapley and Alvin Roth (who extended the theory to practice).

Algorithm Reference Table