xiii. Stable Matching

Agents rank partners on the other side; a matching is stable if no pair $(p,a)$ prefer each other to their assigned partners (a blocking pair). Gale–Shapley always finds one in $O(\sum |\text{lists}|)$, and the side that proposes gets its best possible outcome. One-sided “roommates” instances may have no stable matching; Irving’s algorithm decides.

Gale–Shapley (with incomplete lists and capacities)

vector<int> galeShapley(int m, const vector<vector<int>>& pref, const vector<vector<int>>& rnk, vector<int> cap = {}) {
    // pref[p]: acceptors in p's order (incomplete allowed); rnk[a][p]: a's rank of p, INT_MAX = unacceptable
    int n = sz(pref); if (cap.empty()) cap.assign(m, 1);
    vector<int> nxt(n), res(n, -1), fr(n); iota(all(fr), 0);
    vector<set<pair<int, int>>> held(m);                       // {rank, proposer}
    while (sz(fr)) {
        int p = fr.back(); fr.pop_back();
        if (nxt[p] == sz(pref[p])) continue;                   // list exhausted: p stays single
        int a = pref[p][nxt[p]++];
        if (rnk[a][p] == INT_MAX || !cap[a]) { fr.push_back(p); continue; }
        held[a].insert({rnk[a][p], p});
        if (sz(held[a]) > cap[a]) { auto w = prev(held[a].end()); fr.push_back(w->second); held[a].erase(w); }
    }
    for (int a = 0; a < m; a++) for (auto [r, p] : held[a]) res[p] = a;
    return res;                                                // partner of each proposer, -1 if none
}

Property (proposers $P$ propose to acceptors $A$)
terminates after at most $\sum_p	\text{pref}_p
the result is stable	always exists in the two-sided case
proposer-optimal: every proposer gets their best partner over all stable matchings	the proposing side wins
acceptor-pessimal: every acceptor gets their worst stable partner
rural hospitals: the same agents are matched in every stable matching (and a hospital that is not full gets the same residents)
stable matchings form a distributive lattice (proposer-wise max / min of two stable matchings is stable)
truth-telling is optimal for proposers (no proposer gains by lying); acceptors can gain
many-to-one (hospitals–residents): residents propose, hospitals keep their best $c_h$	the same theorems via cloning

Proof: termination, stability, optimality, rural hospitals

Termination: a proposer never proposes twice to the same acceptor. Stability: let $p$ prefer $a$ to $p$‘s final partner (or $p$ is single but finds $a$ acceptable). Then $p$ proposed to $a$ and was rejected, then or later, in favour of agents $a$ ranks higher; an acceptor’s held set only improves, so at the end $a$ holds ${\text{cap}}_a$ agents (one, in the one-to-one case) all better than $p$. So $(p,a)$ does not block.

Proposer-optimal. Call $a$ achievable for $p$ if some stable matching pairs them. Suppose the run ever rejects $p$ by an achievable $a$, and look at the first such rejection, in favour of $p^{\prime }$ whom $a$ prefers. Let $M$ be stable with $M(p)=a$; then $M(p^{\prime })=a^{\prime }\ne a$ is achievable for $p^{\prime }$. Up to now no proposer was rejected by an achievable partner, so $p^{\prime }$ has not been rejected by $a^{\prime }$, and since proposers go down their lists, $p^{\prime }$ prefers $a$ to $a^{\prime }$. Then $(p^{\prime },a)$ blocks $M$. Contradiction: no proposer is ever rejected by an achievable partner, so each ends with the best achievable one (the result is itself stable, so its partner is achievable).

Acceptor-pessimal. Let $M_0$ be the result and $M$ stable with $a$ preferring $M_0(a)=p$ to $M(a)$. Then $p$ prefers $a$ (its best achievable partner) to $M(p)\ne a$, so $(p,a)$ blocks $M$.

Rural hospitals (one-to-one). Every proposer matched in some stable $M$ is matched in $M_0$ (its partner there is at least as good as in $M$), so $M_0$ matches at least as many proposers; every acceptor matched in $M_0$ is matched in $M$ (its $M_0$ partner is its worst stable one), so $M$ matches at least as many acceptors. Both matchings have equal sizes on both sides, so the matched sets coincide. Many-to-one: clone hospital $h$ into $c_h$ copies with $h$‘s preferences, which residents rank consecutively in place of $h$; stable matchings correspond, and the algorithm above simulates proposals to the clones.

Lattice (complete lists). Let $M,M^{\prime }$ be stable and give each proposer the better of its two partners. Two proposers cannot get the same $a$: if $a=M(p)=M^{\prime }(q)$ with $p$ preferring $M(p)$ to $M^{\prime }(p)$ and $q$ preferring $M^{\prime }(q)$ to $M(q)$, stability of $M^{\prime }$ makes $a$ prefer $q$ to $p$, and stability of $M$ makes $a$ prefer $p$ to $q$. Each acceptor then gets the worse of its two partners (if $a=M(p_0)$ is $p_0$‘s choice, $p_0$ prefers $a$ to $M^{\prime }(p_0)$, so $a$ prefers $M^{\prime }(a)$ to $p_0$). A blocking pair $(p,a)$ of the result: $p$ prefers $a$ to both of its partners, $a$ prefers $p$ to its partner in the matching ($M$ or $M^{\prime }$) that gave it, so $(p,a)$ blocks that matching. Contradiction.

Proof: proposers cannot gain by lying (Dubins–Freedman)

Blocking lemma. Let $M_0$ be the proposer-optimal stable matching for the true preferences, $M$ any matching in which everyone is matched acceptably, and $P^{\prime }$ the nonempty set of proposers who strictly prefer $M$ to $M_0$. Then some $(p,a)$ with $p\notin P^{\prime }$ blocks $M$. Case $M(P^{\prime })\ne M_0(P^{\prime })$: take $a=M(p^{\prime })\notin M_0(P^{\prime })$ with $p^{\prime }\in P^{\prime }$. Since $p^{\prime }$ prefers $a$ to $M_0(p^{\prime })$ and $M_0$ is stable, $a$ prefers $p=M_0(a)$ to $p^{\prime }$, and $p\notin P^{\prime }$ (as $a\notin M_0(P^{\prime })$); $p$ weakly prefers $M_0(p)=a$ to $M(p)\ne a$, so $(p,a)$ blocks $M$. Case $M(P^{\prime })=M_0(P^{\prime })=A^{\prime }$: each $a\in A^{\prime }$ rejected $M(a)\in P^{\prime }$ during the run (that proposer reached its $M_0$ partner later). Let $a\in A^{\prime }$ be the acceptor receiving its final proposal (from $M_0(a)$) last; at that moment it already held someone, $p$, who is rejected now. If $p\in P^{\prime }$, $p$ would later propose to $M_0(p)\in A^{\prime }$, contradicting the choice of $a$; so $p\notin P^{\prime }$. $p$ proposed to $a$ before $M_0(p)$, so $p$ prefers $a$ to $M_0(p)⪰M(p)$; and $a$ held $p$ after having rejected $M(a)$, so $a$ prefers $p$ to $M(a)$. So $(p,a)$ blocks $M$.

Strategy-proofness. Suppose proposer $q$ misreports and the algorithm returns $M$, which $q$ truly prefers to $M_0(q)$. $M$ is stable for the reported profile, so no pair without $q$ blocks it under true preferences (those agents reported truthfully). Applying the lemma with true preferences, a blocking pair $(p,a)$ with $p\notin P^{\prime }$ exists; since $q\in P^{\prime }$, $p\ne q$, contradicting stability under the reports.

Stable roommates (Irving)

One set of $n$ agents (even), complete strict lists. Phase 1 runs proposals and deletes from each receiver’s list everyone worse than the proposer it holds; phase 2 repeatedly finds a rotation (follow “second choice’s current holder” until a cycle) and eliminates it. An empty list means no stable matching. $O(n^2)$ entries, $O(n^3)$ worst case in this simple form.

vector<int> stableRoommates(const vector<vector<int>>& rnk) {   // rnk[i][j]: position of j in i's list; {} if none
    int n = sz(rnk); if (n % 2) return {};
    vector<vector<char>> act(n, vector<char>(n)); vector<deque<int>> pref(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) if (i != j) pref[i].push_back(j), act[i][j] = 1;
        sort(all(pref[i]), [&](int x, int y) { return rnk[i][x] < rnk[i][y]; });
    }
    vector<int> propose(n, -1), proposed(n, -1); bool ok = true;
    auto rem = [&](int x, int y) { act[x][y] = act[y][x] = 0; };
    auto clip = [&](int x) {                                    // drop deleted entries at both ends
        while (sz(pref[x]) && !act[x][pref[x].front()]) pref[x].pop_front();
        while (sz(pref[x]) && !act[x][pref[x].back()]) pref[x].pop_back();
        if (pref[x].empty()) ok = false;
    };
    auto add = [&](int x, int y) {                              // y holds x: delete everyone y likes less
        propose[x] = y, proposed[y] = x;
        while (ok) { clip(y); if (!ok) return; if (pref[y].back() != x) rem(y, pref[y].back()); else break; }
    };
    auto nextOf = [&](int x) {                                  // holder of x's second choice
        clip(x); int y = pref[x].front(); pref[x].pop_front(); clip(x);
        int sec = pref[x].front(); pref[x].push_front(y);
        return proposed[sec];
    };
    queue<int> q; for (int i = 0; i < n; i++) q.push(i);
    while (sz(q) && ok) {                                       // phase 1: proposals
        int x = q.front(); q.pop();
        while (ok) {
            clip(x); if (!ok) break;
            int y = pref[x].front(), X = proposed[y];
            if (X != -1 && rnk[y][X] < rnk[y][x]) { rem(x, y); continue; }
            if (X != -1) propose[X] = -1, proposed[y] = -1, q.push(X);
            add(x, y); break;
        }
    }
    if (!ok) return {};
    for (int cur = 0; ok;) {                                    // phase 2: eliminate rotations
        for (; cur < n; cur++) { clip(cur); if (!ok) return {}; if (sz(pref[cur]) > 1) break; }
        if (cur == n) break;
        vector<int> cyc, CYC; int x = cur, y = cur;
        do { x = nextOf(x); y = nextOf(nextOf(y)); } while (x != y && ok);
        if (!ok) return {};
        do { cyc.push_back(y); y = nextOf(y); } while (x != y);
        for (int a : cyc) { int b = propose[a]; CYC.push_back(b); propose[a] = -1, proposed[b] = -1; rem(a, b); }
        for (int i = 0; i < sz(cyc) && ok; i++) add(cyc[i], CYC[(i + 1) % sz(cyc)]);
    }
    if (!ok) return {};
    return propose;
}

Proof sketch: Irving's algorithm

Phase 1 is safe: when $y$ holds $x$‘s proposal, any agent $z$ that $y$ ranks below $x$ cannot be $y$‘s partner in a stable matching: by induction no stable matching pairs $x$ with someone $x$ ranks above $y$ (those rejected or deleted $x$ safely), so in a stable matching with $\{y,z\}$, $x$ would prefer $y$ to its partner while $y$ prefers $x$ to $z$, a blocking pair. Phase 2 is safe: a rotation $(x_0,y_0),\dots ,(x_{r-1},y_{r-1})$ (with $y_i$ first on $x_i$‘s list and $y_{i+1}$ second) can be eliminated (each $x_i$ moves to $y_{i+1}$, deleting worse entries) without destroying all stable matchings: if a stable matching exists in the table, one exists after elimination (Irving’s lemma, by an exchange argument showing that a stable matching using some pair $\{x_i,y_i\}$ can be transformed). End: when every list has length one, the table pairs everyone and the pairing is stable (all potential blocking pairs were deleted with a justification). An emptied list certifies non-existence.

Notes and variants

• With ties, weak stability always exists (break ties arbitrarily) but maximising its size is NP-hard; with couples, existence is NP-hard.
• Egalitarian (minimise total rank) and minimum-regret stable marriages are polynomial: stable matchings correspond to closed subsets of the rotation poset (Irving–Leather), with weights adding over rotations, so the egalitarian one is a maximum weight closure (Flow Modeling).
• The number of stable matchings can be exponential; counting is p-complete.
• A popular special case: when one side’s preferences are derived from a common score (e.g. all hospitals rank by exam score), the stable matching is the serial dictatorship: process residents by score, each takes their best hospital with space.
• The lattice of stable matchings has a well-defined median (coordinate-wise median of any odd number of stable matchings is itself stable), a middle ground between the proposer-optimal and acceptor-optimal extremes.
• This is not just a curiosity: the many-to-one version runs the US medical residency match (NRMP, ~40,000 applicants/year), New York and Boston school choice, and is the starting point for kidney-exchange matching; Shapley and Roth shared the 2012 Nobel Prize in Economics for this line of work.