Stable Marriage, in depth: Gale-Shapley deferred acceptance, proposer optimality, incentives, variants and implementation at scale

Definitions: matchings and blocking pairs

Take n proposers and n receivers. Each proposer ranks all receivers strictly, and each receiver ranks all proposers strictly. A matching pairs each proposer with exactly one receiver. A pair (p, r) that is not matched together is a blocking pair if p prefers r to p's current partner and r prefers p to r's current partner. A matching with no blocking pair is stable.

Stability is a weaker goal than it first appears, and a stronger one. Weaker, because it does not maximise anyone's happiness: some people may get their last choice. Stronger, because it is a property of the whole assignment that can be checked in O(n²) time by looking at every pair, and because a stable matching resists unravelling. Historically, markets without stable assignment procedures saw offers made earlier and earlier and side deals made outside the system; Alvin Roth's studies of medical residency markets documented this, and that line of work was recognised in the 2012 economics Nobel prize shared by Roth and Shapley.

Note what stability is not. It is not the same as maximising the number of matched pairs, which augmenting-path algorithms such as Kuhn's algorithm solve, and it is not minimum total cost, which the Hungarian algorithm solves. A minimum-cost assignment can contain blocking pairs, and a stable matching can have a poor total score.

Deferred acceptance and why it works

Deferred acceptance runs in rounds. Every free proposer proposes to the best receiver they have not yet proposed to. Each receiver looks at everyone currently proposing to them plus the proposer they are holding, keeps the one they like best, and rejects the rest. Holding is tentative, which is where the name comes from: a receiver never commits until the end, and drops a held proposer whenever a better one arrives. The process stops when no proposer is free.

The order in which free proposers act does not change the result, so a queue works as well as synchronous rounds. Here is a complete implementation with an O(1) rank lookup:

from collections import deque

def deferred_acceptance(prop_prefs, recv_prefs):
    """prop_prefs[p] and recv_prefs[r] are lists, best first. Returns {proposer: receiver}."""
    rank = {r: {p: i for i, p in enumerate(lst)} for r, lst in recv_prefs.items()}
    next_choice = {p: 0 for p in prop_prefs}   # index into p's list
    held = {}                                  # receiver -> proposer
    free = deque(prop_prefs)
    while free:
        p = free.popleft()
        r = prop_prefs[p][next_choice[p]]
        next_choice[p] += 1
        current = held.get(r)
        if current is None:
            held[r] = p
        elif rank[r][p] < rank[r][current]:
            held[r] = p
            free.append(current)               # displaced proposer tries again
        else:
            free.append(p)                     # rejected, tries next choice
    return {p: r for r, p in held.items()}

def blocking_pairs(prop_prefs, recv_prefs, match):
    partner = {r: p for p, r in match.items()}
    rank = {r: {p: i for i, p in enumerate(lst)} for r, lst in recv_prefs.items()}
    out = []
    for p, prefs in prop_prefs.items():
        for r in prefs:
            if r == match[p]:
                break                          # everything after is worse for p
            if rank[r][p] < rank[r][partner[r]]:
                out.append((p, r))
    return out

Why it terminates: each proposal goes down a proposer's list and never repeats, so there are at most n² proposals. Why everyone ends matched: a receiver who has been proposed to stays held forever, so if some proposer were rejected by all n receivers, all n receivers would be holding someone, which needs n other proposers, but there are only n - 1 others. Why the result is stable: suppose p prefers r to p's final partner. Then p proposed to r earlier and was rejected or later displaced, which only happens in favour of someone r likes more, and a receiver's held partner only improves over time. So r ends with someone r prefers to p, and (p, r) cannot block. The total work is O(n²), which is linear in the input size, since the input is two n by n preference tables. Ship the blocking_pairs checker alongside the solver and run it in tests; it is the cheapest correctness oracle you will ever get.

Worked example with three stable answers

Four proposers, Ana, Ben, Cy and Dee, and four receivers, W, X, Y and Z, with the preferences in the diagram. Running the code above with a FIFO queue gives this trace:

The result is Ana with Z, Ben with W, Cy with Y and Dee with X, and the blocking-pair checker returns an empty list. Eight proposals for four people is typical; the worst case is n(n - 1) + 1 proposals for adversarial inputs, and random preferences need about n ln n on average.

This instance has three stable matchings. Listing all 24 permutations and filtering with the checker finds them: the one above; Ana-Y, Ben-W, Cy-Z, Dee-X; and Ana-Y, Ben-Z, Cy-W, Dee-X. Running the same algorithm with the receivers proposing produces the last of these, in which every receiver gets their first choice and Ben ends with Z, last on Ben's list. Dee and X are paired in all three, because each is the other's first choice.

Who the algorithm favours

The three stable answers are not equally good for everyone, and the algorithm picks a specific one. Gale and Shapley proved that proposer-proposing deferred acceptance gives every proposer the best partner they can have in any stable matching, simultaneously. It is proposer-optimal. The same matching gives every receiver the worst partner they have in any stable matching: it is receiver-pessimal. In the example, Ana gets Z (second on Ana's list) instead of Y (third), while Z gets Ana (third choice) instead of Ben (first).

More generally, the stable matchings of an instance form a distributive lattice, ordered by proposer preference, with the proposer-optimal matching at one end and the receiver-optimal at the other. The number of stable matchings can grow exponentially in n, so do not enumerate them for real instances. If you want a compromise, such as minimising the worst rank anyone receives or the sum of ranks, there are polynomial algorithms based on the lattice structure (the egalitarian stable matching, for example), but some fairness objectives, such as minimising the difference between the two sides, are NP-hard.

Incentives follow the same split. Under proposer-proposing deferred acceptance, no proposer can get a better partner by lying about their preferences: the mechanism is strategy-proof for the proposing side, a result due to Roth and to Dubins and Freedman. Receivers, however, can sometimes do better by misreporting, for example by rejecting an offer they would accept. No stable mechanism is strategy-proof for both sides. This is why the choice of who proposes is a policy decision. The US National Resident Matching Program moved to an applicant-proposing design in the late 1990s, based on work by Roth and Peranson, partly so that applicants could rank programs honestly.

Variants used in practice

Real problems rarely have equal sides and complete, strict lists. Here is what survives each relaxation.

The capacities variant is the one most systems need. Each receiver keeps a bounded heap of held proposers ordered by its ranking; when the heap is full and a better proposer arrives, the worst held one is evicted and becomes free. A binary heap makes each step O(log q). The rural hospitals theorem matters operationally: if a program is under-filled in one stable matching, it is under-filled by the same number in all of them, so changing the tie-breaking or who proposes will not fix it; only changing preferences or capacities will.

Ties deserve care. If a school ranks students in coarse priority groups, you must break ties to run the algorithm, and the tie-breaking rule changes who gets what. Single tie-breaking, one random order for all schools, and multiple tie-breaking, a separate order per school, behave differently, and published studies of school choice have compared them. Whatever you choose, record the random seed so the outcome can be reproduced and audited.

Engineering at scale

For n in the thousands the rank table dominates memory: n² integers. Ten thousand by ten thousand entries as 32-bit integers is 400 MB; with 16-bit ranks it is 200 MB. Real lists are usually short, since applicants rank perhaps ten to twenty programs, so store ranks sparsely as a hash map or as a sorted array per receiver, and treat absence as unacceptable. With incomplete lists, a proposer whose list runs out stays unmatched; the loop must check next_choice[p] < len(prefs[p]) before proposing.

Determinism matters for audits. The result does not depend on processing order, but floating-point scores, unstable sorts and hash ordering in the tie-breaking step can make two runs disagree. Generate preference lists with a stable sort and an explicit tie-break key, then store the inputs, the seed and the output together.

Testing is easy to get right. For small n, enumerate all n! matchings and check that the algorithm's answer is stable and that every proposer weakly prefers it to every other stable matching. For large n, generate random instances, run the checker, and run both orientations to confirm that every proposer weakly prefers the proposer-optimal result. A property-based test with a library such as Hypothesis will find the off-by-one in list exhaustion faster than any hand-written case.

Failure modes

• Treating stability as fairness. A stable matching can give a whole group their last choices. Report the rank distribution on each side, not just the fact that it is stable.
• Unexamined proposer choice. Swapping who proposes changes outcomes for many people. Decide it deliberately and document it.
• Rank inversion bugs. Mixing up rank 0 as best with a score where larger is better silently produces the receiver-pessimal answer for the wrong side. The blocking-pair checker catches this.
• Strategic receivers. If receivers can see interim results or negotiate outside the system, the guarantees weaken. Collect all preferences before running, and run once.
• Couples and side constraints bolted on. Adding must-pair constraints can make a stable matching impossible. If you add them, add detection for instability in the output and a fallback.

What to do next

1. Implement deferred acceptance and the blocking-pair checker, and reproduce the eight-step trace above.
2. Enumerate all stable matchings of the example by brute force and confirm there are three.
3. Run the receiver-proposing version and compare each person's rank in both results.
4. Extend the code to capacities with a heap per receiver and test it against a brute-force checker.
5. Add incomplete lists and confirm the rural hospitals theorem on random instances.
6. For a real assignment problem, write down which side proposes and why, how ties are broken, and how the seed is stored.
7. Read about greedy algorithms and compare how their exchange-argument proofs differ from the stability proof here.