Stable Matching / Gale–Shapley

Blocking pairs, stability, and the deferred-acceptance algorithm.

The idea

A stable matching pairs the two sides of a market — firms and workers, students and schools — so that no pair of participants would abandon the assignment to be with each other.

Take $n$ firms and $n$ workers, where each participant ranks everyone on the other side. A matching pairs them one-to-one. A firm $f$ and a worker $w$ who are not matched to each other form a blocking pair when $f$ prefers $w$ to its assigned worker and $w$ prefers $f$ to her assigned firm: both gain by leaving their partners to pair up. A matching is stable when no blocking pair exists. The deviating unit is a single pair, not one person and not the whole market.

Gale and Shapley proved that a stable matching always exists, by giving an algorithm that produces one: deferred acceptance, in the version where the firms propose.

Algorithm.

Algorithm: Deferred Acceptance Input: n firms and n workers, each ranking everyone on the other side Output: a stable matching 1. every firm unmatched; no worker holds a proposal 2. if no firm is both unmatched and able to propose, return the matching of held proposals 3. each unmatched firm proposes to its highest-ranked worker who has not yet rejected it 4. each worker compares the new proposals with the proposer she holds, if any: she holds the best and rejects the rest // her held proposer only ever improves a displaced firm is unmatched again // a firm only ever moves down its own list 5. go to step 2

A held proposal is tentative until the algorithm stops. No firm proposes twice to the same worker, so the algorithm makes at most $n^{2}$ proposals and terminates, and the matching it ends with has no blocking pair.

Ways to work on it

Not sure where to start? Take the ten-question placement test.