Gale-Shapley Deep Dive, in depth: proposal counts, the tight n(n-1)+1 worst case, parallel rounds and incremental re-matching

A short recap and the code

There are n proposers and n receivers, each with a complete strict preference list. A free proposer proposes to the best receiver they have not yet tried. A receiver holds the best offer it has seen and rejects the rest, dropping its held proposer whenever a better one arrives. The run ends when nobody is free. Here is the implementation measured throughout this page; it returns the matching and the number of proposals:

from collections import deque

def deferred_acceptance(P, R):
    # P[p], R[r]: complete preference lists over 0..n-1, best first
    n = len(P)
    rank = [[0] * n for _ in range(n)]
    for r in range(n):
        for i, p in enumerate(R[r]):
            rank[r][p] = i                 # invert once: O(n^2)
    nxt, held, free, proposals = [0] * n, [-1] * n, deque(range(n)), 0
    while free:
        p = free.popleft()
        r = P[p][nxt[p]]
        nxt[p] += 1
        proposals += 1
        h = held[r]
        if h == -1:
            held[r] = p
        elif rank[r][p] < rank[r][h]:
            held[r] = p
            free.append(h)                 # displaced proposer tries again
        else:
            free.append(p)                 # rejected, tries the next choice
    return held, proposals                 # held[r] is r's proposer

The cost model: count proposals

With the rank table inverted up front, a proposal is a constant number of array reads and writes, so running time is Θ(n²) to build the table plus Θ(number of proposals). The table is the part people forget. Preferences arrive as lists, and comparing two proposers by searching a receiver's list costs O(n) per comparison, which quietly turns the algorithm into O(n³).

The proposal count has a property worth knowing: it does not depend on the order in which free proposers act. Whatever the order, the result is the proposer-optimal stable matching, and a proposer moves down their list only when rejected, so each proposer proposes to exactly the receivers ranked at or above their final partner. The total is the sum over proposers of (position of final partner + 1). On a random instance with n = 300 (seed 5), FIFO order and five random processing orders all made exactly 2,054 proposals and produced the same matching. The count is therefore a property of the instance, and you can compute it from the output alone, which is useful for capacity planning and for checking a run's logs.

The worst case is tight: n(n - 1) + 1

Each proposer proposes at most n times, so n² is a trivial bound. The true bound is a little lower. Receivers never become empty once proposed to, and the run stops the moment every receiver holds someone, so the last receiver to get a proposal gets exactly one. Each of the other n − 1 receivers gets at most n, one from each proposer. Total: at most n(n − 1) + 1.

The bound is reached for every n. This family was found by letting receivers always prefer the newest proposer and reading their lists off the run:

def worst_case(n):
    m = n - 1
    # proposers: cyclic shifts over receivers 0..m-1, then receiver m last
    P = [[(i % m + k) % m for k in range(m)] + [m] for i in range(n)]
    # receiver r prefers proposer r+1, then r+2, ..., wrapping around
    R = [[(r + 1 + k) % n for k in range(n)] for r in range(n)]
    return P, R

for n in (4, 5, 8, 50, 200):
    P, R = worst_case(n)
    assert deferred_acceptance(P, R)[1] == n * (n - 1) + 1

The mechanism: the first n − 1 receivers form a cycle, and each one prefers the proposer arriving next around it, so every proposal displaces the current holder, who moves on and displaces someone else. Only when one proposer has been rejected by the whole cycle does anyone reach the last receiver, which ends the run. Lists that are shifts of one another are the pattern to watch for in real data.

Typical inputs: about n ln n

Random preferences behave far better. With independent uniformly random lists the run resembles coupon collecting: it ends when the last receiver gets its first proposal, and proposers walking random lists hit receivers roughly at random, so about n ln n proposals are expected, a classical analysis associated with Knuth. Measured with seed 1:

The mean sits a little below n·H_n and the spread is wide: one instance in the n = 100 sample needed more than twice the mean. For n = 1,000 the pure-Python code takes about a quarter of a second per instance on a laptop, much of it inverting the rank table. Real preferences are not random. When proposers agree on which receivers are best, the count climbs toward quadratic: if every proposer has the same list, the first receiver is proposed to by all n, the second by n − 1 and so on, n(n + 1)/2 in total, whatever the receivers prefer. Measure the count on production-shaped data instead of assuming n ln n.

Parallel rounds do not fix the worst case

Because order does not matter, all free proposers can propose at once. In each synchronous round every free proposer sends one proposal and each receiver keeps the best of its holder and the new offers. That is the natural shape for a GPU kernel, an MPI job or a MapReduce pipeline, and its cost is the number of rounds.

The measurements show the limit. On random inputs with n = 1,000, about 1,502 rounds carried 7,186 proposals, under five proposals per round on average: after the first few rounds almost everyone is matched and a handful of displaced proposers chase each other. On the worst-case family it is far worse: n = 200 needs 39,602 rounds for 39,801 proposals, which is essentially sequential. Whether stable matching can be solved in polylogarithmic parallel time with polynomially many processors (whether it is in NC) is a long-standing open problem, so no known trick removes this tail.

So a distributed implementation wins only in the first rounds; hand the long tail to a single machine once few proposers remain free.

Data layout for large instances

Dense layout stores P as an n × n array of receiver IDs and rank as an n × n array of positions. With n = 10,000 and 32-bit integers each table is 400 MB; 16-bit integers halve that and suffice up to n = 65,536. Each proposal reads P[p][nxt[p]] sequentially but rank[r][p] at a random location, so for large n the rank lookup is the cache miss that dominates.

Sparse layout fits real clearinghouses, where lists are short. Store each list as an array and each receiver's ranks as a hash map from proposer to position, with absence meaning unacceptable. Work and memory become O(L), the total list length. The loop must skip receivers that do not list the proposer and must stop when a list runs out, leaving that proposer unmatched. For receivers with capacity q, keep the held set in a heap keyed by rank so the worst holder is evicted in O(log q).

Incremental re-matching: when you can resume

Matching systems change: applicants arrive late, programmes withdraw posts. Recomputing costs O(L); resuming the previous run is tempting, and correct in exactly two of the four basic cases.

The safe cases rest on one invariant: every rejection recorded in the state is still justified in the new instance, so the state is one the algorithm could have reached on that instance, and by order-independence the resumed run ends at the new proposer-optimal matching. A randomised test of 2,000 instances with n = 8 (seed 11) agreed with full recomputation every time for the two safe cases, while a naive resume disagreed in 1,400 of 2,000 trials when a proposer left and in 1,772 when a receiver arrived.

from collections import deque

class Matcher:
    # P: proposer -> receivers, R: receiver -> proposers, best first; lists may be partial
    def __init__(self, P, R):
        self.P = {p: list(l) for p, l in P.items()}
        self.R = {r: list(l) for r, l in R.items()}
        self.rank = {r: {p: i for i, p in enumerate(l)} for r, l in self.R.items()}
        self.nxt, self.held, self.free = {p: 0 for p in self.P}, {}, deque(self.P)
        self.run()

    def run(self):
        while self.free:
            p = self.free.popleft()
            prefs = self.P[p]
            while self.nxt[p] < len(prefs):
                r = prefs[self.nxt[p]]
                self.nxt[p] += 1
                if r not in self.R or p not in self.rank[r]:
                    continue                    # receiver gone, or does not accept p
                h = self.held.get(r)
                if h is None or self.rank[r][p] < self.rank[r][h]:
                    self.held[r] = p
                    if h is not None:
                        self.free.append(h)
                    break
        return {p: r for r, p in self.held.items()}

    def add_proposer(self, p, prefs, positions):
        # positions[r]: where r ranks p; r's order of existing proposers is unchanged
        self.P[p], self.nxt[p] = list(prefs), 0
        for r, i in positions.items():
            self.R[r].insert(i, p)
            self.rank[r] = {q: k for k, q in enumerate(self.R[r])}
        self.free.append(p)
        return self.run()

    def remove_receiver(self, r):
        del self.R[r], self.rank[r]
        h = self.held.pop(r, None)
        if h is not None:
            self.free.append(h)
        return self.run()

Persist the state (next indices, held proposers, free queue) with the matching, and recompute for the unsafe cases.

Verifying a production run

Three checks are cheap enough to run on every production matching. Stability: for each proposer, scan the receivers above their partner and confirm none prefers them to its own match, O(L) in total. Optimality for the proposing side: rerun with a different processing order, a reversed queue is enough, and require the identical matching, since order-independence makes any difference a bug. Proposal count: recompute the sum of (partner position + 1) from the output and compare it with the count the run logged; a mismatch means proposals were lost or duplicated, typically because a list named the same receiver twice.

Failure modes

• No rank inversion. Searching lists to compare proposers makes the run cubic. Invert once, before the loop.
• Dense tables at scale. Two n × n tables at n = 10,000 cost 800 MB with 32-bit integers. Switch to sparse lists and hash maps when lists are short.
• Invalid input. Duplicate entries, unknown IDs or a receiver missing a proposer it is asked to rank cause crashes in dense code and silent skips in sparse code. Validate that each list has no duplicates and only known IDs before running.
• Latency budgets from random benchmarks. Random inputs need about n ln n proposals; correlated or cyclic inputs need up to n(n − 1) + 1. Budget for the shape of your data.
• Unsafe resumes. Resuming after a proposer leaves or a receiver arrives returns a wrong matching. Recompute in those cases.
• Non-determinism in inputs. The algorithm is order-independent, but tie-breaking that depends on hash order or unstable sorts is not. Fix seeds and sort keys and store the exact lists you ran.

Trade-offs

For general bipartite assignment without preferences, where you want the largest matching rather than a stable one, stable matching is the wrong tool; Hopcroft-Karp and the broader bipartite matching article cover that problem.

What to do next

1. Instrument your matcher to log the proposal count and the number of rounds, and compare the count with the sum of partner positions after every run.
2. Compute the count on production-shaped inputs and set latency budgets from that, not from random benchmarks.
3. Invert ranks once, and pick dense or sparse storage from n and the average list length.
4. If you distribute the work, measure how many free proposers remain per round and add a sequential finisher for the tail.
5. Adopt incremental resumes only for added proposers and removed receivers, and keep a randomised comparison against full recomputation in CI.
6. Run the stability, reversed-order and proposal-count checks on every production matching.