Stable Matching, in depth: the lattice of all stable matchings, rotations, enumeration, and choosing the egalitarian or minimum-regret answer

Setup and a worked instance

Take n men and n women with complete, strict preference lists. A matching is stable when no man and woman both prefer each other to their assigned partners; such a pair is a blocking pair. The example has four of each, with lists written most preferred first:

Men-proposing Gale-Shapley gives M0 = {m1-w4, m2-w3, m3-w1, m4-w2}. Women-proposing gives M4 = {m1-w1, m2-w4, m3-w2, m4-w3}. The instance has three more stable matchings between them.

The lattice of stable matchings

Say M is above M' when every man likes his partner in M at least as much as his partner in M'. Stability gives the key fact: whenever one man gains, some woman loses, and the opposite. Moving between stable matchings, the two sides' interests are exactly opposed. Take any two stable matchings and give each man the better of his two partners. The result is a matching, and it is stable. The same holds if every man takes the worse partner. These two operations are the lattice's join and meet, and they distribute over each other. The man-optimal matching is the top of the lattice and the woman-optimal matching is the bottom.

Rotations and the rotation poset

How do you step down from a stable matching M without breaking stability? For each man m, let s(m) be the first woman after his current partner on his list who prefers m to her own partner in M. Let next(m) be the man currently matched to s(m). Following next(m) gives a graph where each man has at most one outgoing edge. Every cycle in this graph is a rotation exposed in M. Eliminating it moves each man on the cycle to s(m), the partner of the next man around the cycle. The result is again stable, and it lies just below M in the lattice.

Trace from M0. m1 holds w4; the next woman on his list is w3, who holds m2 and ranks m1 above m2, so next(m1) = m2. m2 holds w3; his next is w4, who prefers m2 to m1, so next(m2) = m1. That gives the cycle rho1 = (m1,w4), (m2,w3), and eliminating it swaps them to m1-w3 and m2-w4. In the same way m3 points to m4 through w2 and m4 points to m3 through w1, which gives rho2 = (m3,w1), (m4,w2). From M3, m1 points to m4 through w1 and m4 to m1 through w3, which gives rho3 = (m1,w3), (m4,w1). m2 and m3 also have edges at M3, but they lead into that cycle and are not on it, so they are not part of any exposed rotation.

The rotation poset. Every rotation is eliminated exactly once on any path from the top to the bottom of the lattice. Some must come before others: rho3 only becomes exposed after rho1 and rho2. A set of rotations closed under predecessors is called a closed set. The central theorem (Irving and Leather, 1986) says that closed sets correspond one to one with stable matchings. Here the closed sets are {}, {rho1}, {rho2}, {rho1, rho2} and all three, which gives exactly five matchings. There are at most n(n-1)/2 rotations, while the number of stable matchings can grow exponentially in n. Counting them is #P-complete.

Enumerating every stable matching

The code enumerates every stable matching by starting at the top and repeatedly eliminating exposed rotations. A seen set removes matchings reached by more than one route. Matchings are tuples where position m holds m's partner.

def gale_shapley(mp, wp):
    n = len(mp)
    rank = [{m: i for i, m in enumerate(wp[w])} for w in range(n)]
    nxt, wife, husband, free = [0] * n, [None] * n, [None] * n, list(range(n))
    while free:
        m = free.pop()
        w = mp[m][nxt[m]]; nxt[m] += 1
        h = husband[w]
        if h is None or rank[w][m] < rank[w][h]:
            husband[w], wife[m] = m, w
            if h is not None:
                wife[h] = None; free.append(h)
        else:
            free.append(m)
    return tuple(wife)

def exposed_rotations(wife, mp, wp):
    n = len(mp)
    rank = [{m: i for i, m in enumerate(wp[w])} for w in range(n)]
    husband = [None] * n
    for m, w in enumerate(wife):
        husband[w] = m
    nxt = {}
    for m in range(n):
        lst = mp[m]
        for w in lst[lst.index(wife[m]) + 1:]:
            if rank[w][m] < rank[w][husband[w]]:
                nxt[m] = husband[w]; break
    rots, seen = [], set()
    for start in nxt:
        path, m = [], start
        while m in nxt and m not in path and m not in seen:
            path.append(m); m = nxt[m]
        if m in path:
            rots.append([(x, wife[x]) for x in path[path.index(m):]])
        seen.update(path)
    return rots

def eliminate(wife, rot):
    new = list(wife)
    for i, (m, _) in enumerate(rot):
        new[m] = rot[(i + 1) % len(rot)][1]
    return tuple(new)

def all_stable(mp, wp):
    top = gale_shapley(mp, wp)
    found, stack = {top}, [top]
    while stack:
        M = stack.pop()
        for r in exposed_rotations(M, mp, wp):
            M2 = eliminate(M, r)
            if M2 not in found:
                found.add(M2); stack.append(M2)
    return found

Test it against brute force: generate every permutation and keep those with no blocking pair. On 3,000 random instances with n from 1 to 6, the two sets agreed every time. This simple version recomputes rotations at every matching. Gusfield's algorithm (1987) finds all rotations once in O(n^2) and then lists the stable matchings in O(n) time each.

Choosing among stable matchings

Score each matching by ranks, where 1 means a first choice. The men's sum and the women's sum measure each side's welfare. Their total measures overall welfare. The regret is the worst rank anyone receives.

Egalitarian (minimum total rank). Here three matchings tie at 18. In general, each rotation changes the total by a fixed amount: rho1 by 0, rho2 by -1 and rho3 by 0. Choosing the best stable matching is therefore choosing a minimum-weight closed set in the rotation poset, which reduces to a minimum cut. Irving, Leather and Gusfield (1987) gave this polynomial algorithm. It is the same max-flow machinery used in bipartite matching.

Minimum regret (best worst-off person). Only M3 achieves regret 3. Gusfield gave an O(n^2) algorithm.

Sex-equal (smallest gap between the sides' sums) and balanced (smallest larger sum). M2 and M3 both have a gap of 2 and a larger sum of 10. In general both are NP-hard (Kato, 1993, for sex-equal), so use heuristics or an integer program, or enumerate when the lattice is small.

A useful fact: if every agent receives their median partner across all stable matchings, the result is itself a stable matching. That gives a principled compromise between the two extremes. If you only want the most efficient assignment and do not need stability, solve a weighted assignment with the Hungarian algorithm. Expect blocking pairs, and so people with a reason to defect.

Engineering a matching system

Turning this into a system involves a few habits.

• Always verify. Ship a checker that scans every man's list down to his partner and reports any blocking pair. Run it on every result, whichever algorithm produced it. It is O(n^2) and catches index bugs that tests on small inputs miss.
• Publish the policy. Moving down the lattice transfers welfare from one side to the other, so choosing a matching other than the proposer-optimal one is a decision someone must own. Record which objective was used and log the chosen matching's position in the lattice.
• Mind incentives. The proposer-optimal mechanism is strategy-proof for the proposing side, and no stable mechanism is strategy-proof for both sides. Choosing an egalitarian matching gives participants on both sides some reason to misreport their preferences. That may be acceptable, but it should be a choice.
• Ties and incomplete lists change everything. With ties, weak stability still exists but stable matchings can differ in size, and finding the largest one is NP-hard. The clean lattice and rotation structure described here applies to strict preferences.
• One-sided markets have no lattice. In stable roommates (one pool, no sides) a stable matching may not exist at all. Irving's algorithm decides in O(n^2) and finds one when it exists.

The smallest roommates failure is worth working through once, because it shows exactly which assumption breaks. Four people, A, B, C and D, must be split into two pairs. A ranks B, C, D. B ranks C, A, D. C ranks A, B, D. Nobody wants D. Only three pairings are possible. If C is with D, then B, who prefers C to A, and C, who prefers B to D, block. If B is with D, then A and B block, since each prefers the other to their current partner. If A is with D, then A and C block. A, B and C form a preference cycle, and whoever ends up with D always has a better option who also wants them. With two sides, a man and a woman can never form this kind of odd cycle, and that is precisely what makes Gale-Shapley and the lattice possible. In production, run Irving's algorithm and, when it reports no solution, fall back to minimizing the number of blocking pairs, which is itself NP-hard and usually approached with heuristics.

Failure modes

• Comparing ranks with list indexing in the inner loop. wp[w].index(m) costs O(n) and turns O(n^2) into O(n^3). Precompute rank tables.
• Mistaking a path for a cycle. In the next() graph, men who only lead into a cycle are not part of the rotation. Eliminating them breaks stability; the verifier will catch it.
• Enumerating without deduplication. Different elimination orders reach the same matching. Without a seen set, the work multiplies with every lattice diamond.
• Assuming the set is small. Adversarial or highly symmetric instances have exponentially many stable matchings. Optimize over the rotation poset instead of listing matchings, and cap enumeration.
• Unequal side sizes left implicit. Pad with dummy agents placed last on everyone's list, or handle incomplete lists explicitly. Then check that the same agents are unmatched in every stable matching, as theory says they must be.

What to do next

1. Run all_stable on the example and confirm the five matchings and three rotations above.
2. Write the brute-force checker and run the random comparison on your own seed.
3. Compute rotation weights for the total-rank objective and pick the egalitarian matching by searching closed sets; then read about min cut for the scalable version.
4. On your real data, measure how far apart the man-optimal and woman-optimal matchings are. If they are identical, the instance has a unique stable matching and the policy question disappears.
5. Compare with an unstable but efficient assignment from maximum matching or the Hungarian algorithm, and count blocking pairs.