Stable Matching Problem

There are $n$ men and $n$ women. Each person has a priority list of $n$ people they’d like to marry. Find a way to marry each man and woman together such that no two non-married man/woman pair prefer each other more than they prefer their current partners

Gale-Shapley Algorithm: $O(n^2)$

• While there are unmarried men $m$ who haven’t exhausted their options
  • Let $m$ choose the highest person on his priority list he hasn’t asked yet
  • If $w$ is free
    • Engage $m$ and $w$
  • If $w$ is already engaged to $m^{\prime }$
    • If $m>m^{\prime }$ on $w$‘s priority list
      • Engage $m$ and $w$
      • Make $m^{\prime }$ free
    • Else
      • $m^{\prime }$ and $w$ remain engaged
• Let all engaged people marry

Claims

• Men will get their best valid match
  • Valid meaning a match that will still enable stable matching
• Women will get their worst valid match