21 Gale-Shapley Algorithm for STABLE MATCHING

Setting:

• Two groups, say hospitals and students, each of size $n$
• Each hospital has a ranking of the $n$ students
• Each student has a ranking of the $n$ hospitals
• Assumption : The list of preferences are strict and complete

THE STABLE MATCHING problem asks to find a stable matching, if one exists. Gale-Shapely algorithm for complete lists:

• There is always a stable matching! (where everyone is allocated)
• $O(n^2)$ time algorithm to find a stable matching
• STABLE MATCHING $\in \mathbf{P}$

1. Initially all hospitals and students are free
2. while there is a hospital which is free and hasn’t made an offer to every student do
3.     Choose such a hospital h
4.     Let s be highest ranked student to which h hasn’t made an offer yet
5.     if s is free then
6.         (s, h) are matched
7.     else
8.         s is currently matched to some hospital h'
9.         if s prefers h' to h then
10.            h remains free
11.        else
12.            s prefers h to their current match h'
13.            (s, h) get matched and h' becomes free
14.        end if
15.    end if
16. end while

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
 
    // hospitalPref[h][i] = i-th preferred student of hospital h
    vector<vector<int>> hospitalPref(n, vector<int>(n));
 
    // studentPref[s][i] = i-th preferred hospital of student s
    vector<vector<int>> studentPref(n, vector<int>(n));
 
    for (int h = 0; h < n; ++h)
        for (int i = 0; i < n; ++i)
            cin >> hospitalPref[h][i];
 
    for (int s = 0; s < n; ++s)
        for (int i = 0; i < n; ++i)
            cin >> studentPref[s][i];
 
    // rank[s][h] = how much student s likes hospital h (lower = better)
    vector<vector<int>> rank(n, vector<int>(n));
    for (int s = 0; s < n; ++s)
        for (int i = 0; i < n; ++i)
            rank[s][studentPref[s][i]] = i;
 
    vector<int> studentMatch(n, -1);   // which hospital student s is matched to
    vector<int> hospitalMatch(n, -1);  // which student hospital h is matched to
    vector<int> nextOffer(n, 0);       // next student index to propose to
 
    queue<int> freeHospitals;
    for (int h = 0; h < n; ++h)
        freeHospitals.push(h);
 
    // ---- Gale-Shapley ----
    while (!freeHospitals.empty()) {
        int h = freeHospitals.front();
        freeHospitals.pop();
 
        int s = hospitalPref[h][nextOffer[h]++];
        
        if (studentMatch[s] == -1) {
            // s is free
            studentMatch[s] = h;
            hospitalMatch[h] = s;
        } else {
            int h2 = studentMatch[s];
            // check preference
            if (rank[s][h] < rank[s][h2]) {
                // s prefers h
                studentMatch[s] = h;
                hospitalMatch[h] = s;
 
                hospitalMatch[h2] = -1;
                freeHospitals.push(h2);
            } else {
                // s rejects h
                freeHospitals.push(h);
            }
        }
    }
 
    // Output result
    cout << "Matches (hospital -> student):\n";
    for (int h = 0; h < n; ++h)
        cout << h << " -> " << hospitalMatch[h] << "\n";
}
 

Running time is clearly $O(n^2)$, but correctness is not obvious at all!

Correctness of Gale-Shapley Algorithm

• Students keep getting better offers as the algorithm progresses
• The sequence of offers made by Hospitals keep getting worse for them

If a hospital is free, then there is a student to whom they have not yet made an offer.
So all hospitals and students are matched!

Theorem

Gale-Shapley returns a stable matching

• Suppose not, and there is an unstable pair $h$ and $s^{\prime }$
• Let $(h,s)$ and $(h^{\prime },s^{\prime })$ be allocation done by Gale-Shapley
  • There $h$ prefers $s^{\prime }$ over $s$, and $s^{\prime }$ prefers $h$ over $h^{\prime }$
• Last offer made by hospital $h$ was to student $s$
• Question : Did $h$ make an offer to student $s^{\prime }$ before making to $s$ ?
• If NO, then $h$ prefers $s$ to $s^{\prime }$. Contradiction
• If YES, then $h$ was rejected by $s^{\prime }$ in favour of some other hospital. As the student offers keep getting better and since $h^{\prime }\ne h$ it follows that $s^{\prime }$ prefers its final offer $h^{\prime }$ to $h$.

Surprising Property of Gale-Shapley algorithm

Gale Shapley always returns the SAME stable matching

For each hospital $h$, let

1. Let $\text{VALID}(h)=\{s:\text{There is a stable matching which matches h to s}\}$
2. $\text{WORST}(S)$ is the lowest ranked (in preference list of $s$) hospital from $\text{VALID}(s)$

Theorem

Gale-Shapley always returns the matching which matches s to $\text{WORST}(s)$ for each student $s$

• Again : Not clear why this is even a matching, forget being stable!