Stable Marriage

Problem. $n$ proposers and $n$ acceptors, each with a strict preference ranking of the other side. Find a perfect matching with no blocking pair — no two people who both prefer each other to their assigned partners.

Gale-Shapley — $O(n^2)$

vector<int> stableMatching(int n,
        vector<vector<int>>& pref,      // pref[p] = acceptors in preference order
        vector<vector<int>>& rank) {    // rank[a][p] = a's ranking of p (lower is better)
    vector<int> next(n, 0);             // next acceptor p will propose to
    vector<int> match(n, -1);           // match[a] = current partner of acceptor a
    stack<int> free_;
    for (int p = 0; p < n; p++) free_.push(p);
 
    while (!free_.empty()) {
        int p = free_.top(); free_.pop();
        int a = pref[p][next[p]++];
        if (match[a] == -1) match[a] = p;                    // a is free
        else if (rank[a][p] < rank[a][match[a]]) {           // a prefers p
            free_.push(match[a]);                            // the old partner is dumped
            match[a] = p;
        } else free_.push(p);                                // rejected; try again
    }
    return match;
}

Each proposer proposes to each acceptor at most once, so there are at most $n^2$ proposals.

The guarantees

Property
A stable matching always exists	Gale-Shapley constructs one
The algorithm always terminates	each proposal is unique
The result is proposer-optimal	every proposer gets the best partner they could have in any stable matching
The result is acceptor-pessimist	every acceptor gets their worst possible stable partner
Acceptors’ partners only improve	once matched, an acceptor never trades down
Proposers cannot benefit from lying	proposing truthfully is dominant
Acceptors can benefit from lying	no truthful mechanism exists for both sides

The proposer/acceptor asymmetry is the striking part: which side proposes determines who gets the better outcome, even though the algorithm looks neutral.

Why it is stable

Suppose proposer $p$ and acceptor $a$ form a blocking pair — each prefers the other to their partner. Then $p$ prefers $a$, so $p$ proposed to $a$ at some point (proposers go down their list in order). Acceptor $a$ either rejected $p$ or later dumped $p$, in both cases for someone better. Since acceptors only ever trade up, $a$‘s final partner is at least as good as $p$ — contradicting that $a$ prefers $p$. ∎

The lattice of stable matchings

The set of all stable matchings forms a distributive lattice, with the proposer-optimal matching at one extreme and the acceptor-optimal at the other. Consequences:

• Rural hospitals theorem: the same set of people is unmatched in every stable matching (in the unequal-sizes version).
• The number of stable matchings can be exponential; counting them is p-complete.
• The “median” stable matching is well defined.

Variants

Variant	Note
Hospitals/residents (many-to-one)	the same algorithm with capacities; used by the US NRMP
Unequal numbers	some remain unmatched, but the same set in every stable matching
Incomplete lists	some pairs are unacceptable; matching may be partial
Ties in preferences	weak vs strong stability; finding a maximum stable matching becomes NP-hard
Stable roommates (one-sided, $2n$ people)	a stable matching may not exist; Irving’s $O(n^2)$ algorithm decides
Couples applying together	NP-hard
Egalitarian stable matching (minimise the total rank)	polynomial, via a min-cut on a rotation poset
Minimum-regret stable matching	polynomial

Stable roommates is the important contrast: dropping the two-sided structure destroys the existence guarantee. The three-person “odd cycle” of preferences has no stable pairing.

Where it is used

The algorithm is not a curiosity — it runs real systems:

• US medical residency matching (NRMP), matching ~40 000 graduates to hospitals annually;
• school choice in New York and Boston;
• kidney exchange (a related but distinct matching problem);
• Shapley and Roth received the 2012 Nobel Prize in Economics for this work.

Why it is worth knowing

It is the cleanest example of a mechanism with a proof of both existence and incentive-compatibility — and of how the same algorithm can be fair to one side and not the other. The proof of stability is short enough to reconstruct from scratch, which makes it a good template for “no blocking configuration” arguments generally.

See also: Bipartite Matching · Assignment Problem · Secretary Problem