xxvi. Stable Marriage

Problem. $n$ men and $n$ women each rank the other side. Find a matching with no blocking pair (a man and a woman who both prefer each other to their partners).

Gale–Shapley: free men propose in order of preference; a woman keeps the best proposal so far. Always terminates in $O(n^2)$ with a stable matching that is the best possible for every man (and the worst for every woman) among all stable matchings.

vector<int> galeShapley(const vector<vector<int>>& pm, const vector<vector<int>>& pw) {   // men propose; returns wife of each man
    int n = sz(pm); vector<vector<int>> rank(n, vector<int>(n));
    for (int w = 0; w < n; w++) for (int i = 0; i < n; i++) rank[w][pw[w][i]] = i;
    vector<int> next(n, 0), husband(n, -1), wife(n, -1); queue<int> freeMen;
    for (int m = 0; m < n; m++) freeMen.push(m);
    while (sz(freeMen)) {
        int m = freeMen.front(); freeMen.pop(); int w = pm[m][next[m]++];
        if (husband[w] < 0) husband[w] = m, wife[m] = w;
        else if (rank[w][m] < rank[w][husband[w]]) { wife[husband[w]] = -1; freeMen.push(husband[w]); husband[w] = m; wife[m] = w; }
        else freeMen.push(m);
    }
    return wife;
}

Proof: termination, stability, proposer-optimality

Termination. Each man proposes to each woman at most once: at most $n^2$ proposals. A woman, once proposed to, stays engaged, so if a man were rejected by everyone, all $n$ women would be engaged to the other $n-1$ men, impossible. Stability. If $m$ prefers $w$ to his wife, he proposed to $w$ earlier and was rejected or later dropped, each time for someone $w$ prefers; her partner only improves, so she prefers her husband to $m$. Man-optimality. Suppose some man is rejected by a woman who is his partner in some stable matching; take the first such rejection in the run: $w$ rejects $m$ for $m^{\prime }$. In the stable matching $M$ where $m$ is with $w$, $m^{\prime }$ is with some $w^{\prime }$; $m^{\prime }$ had not yet been rejected by any stable partner, so he prefers $w$ to $w^{\prime }$, and $w$ prefers $m^{\prime }$ to $m$: $(m^{\prime },w)$ blocks $M$, a contradiction. Tested against all stable matchings for $n\le 5$. More: Stable Matching.