20 How fast can we solve the Stable Matching Problem ?

The Stable Matching Problem asks to find a stable matching, if one exists.

• STABLE MATCHING $\in \mathbf{NP}$
  • Given a matching, check the $n^2$ pairs one-by-one if they are unstable or not
  • If no unstable pair, then matching is stable
• Brute-force algorithm for STABLE MATCHING ?
  • Tries all the matchings. How many are there ?
  • This is too slow
  • Brute force takes $n!$

Gale-Shapley algorithm (1962) 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}$