AlgoVerse

Gale–Shapley (stable matching)

Men propose in order of preference and women always keep the best offer so far; the result is a stable matching: no two people both prefer each other to their partners. At most n² proposals.

There are n men and n women, and each ranks everyone on the other side. A matching is unstable if some man m and woman w both prefer each other to their current partners (a "blocking pair"). We want a stable matching. The same problem assigns medical residents to hospitals.

Read the full explanation ↓
Input:
M 3×3 · W 3×3PDF export

Three men and three women. Woman 0 drops man 0 for man 1, and woman 1 drops man 2 for man 0; the result: (0, 1), (1, 0), (2, 2). Each row of M is one man's list of women, best first, and each row of W one woman's list of men.

  1. def gale_shapley(M, W):
  2. # M[m]: man m's list of women, best first; W[w]: woman w's list of men, best first. People are numbered from 0.
  3. n = len(M)
  4. for prefs in M + W:
  5. if sorted(prefs) != list(range(n)):
  6. return None
  7. rank = [[0] * n for _ in range(n)]
  8. for w in range(n):
  9. for i in range(n):
  10. rank[w][W[w][i]] = i
  11. wife = ["·"] * n
  12. husband = ["·"] * n
  13. nxt = [0] * n # the next woman on each man's list
  14. free = list(range(n))
  15. rejections = 0
  16. while free:
  17. m = free[0]
  18. w = M[m][nxt[m]]
  19. nxt[m] = nxt[m] + 1
  20. if husband[w] == "·":
  21. husband[w] = m
  22. wife[m] = w
  23. free.pop(0)
  24. elif rank[w][m] < rank[w][husband[w]]:
  25. old = husband[w]
  26. husband[w] = m
  27. wife[m] = w
  28. wife[old] = "·"
  29. free.pop(0)
  30. free.append(old)
  31. else:
  32. rejections = rejections + 1
  33. return wife

Invariant: Once a woman gets her first proposal she stays engaged, and her fiancé only gets better; each man proposes down his list in order.

Start

free—
wife—
husband—
nxt—

Local variables

Orange = changed in this step

M list

[0, 1, 2][0, 2, 1][1, 0, 2]

W list

[1, 0, 2][0, 1, 2][0, 1, 2]

Call stack

  1. gale_shapley()line 1
Step 1 of 103
Black = propose · Orange = key steppropose: 0/6 · engaged: 0/3 · switch: 0/2 · reject: 0/1
    Explanation

    The problem

    There are n men and n women, and each ranks everyone on the other side. A matching is unstable if some man m and woman w both prefer each other to their current partners (a "blocking pair"). We want a stable matching. The same problem assigns medical residents to hospitals.

    The algorithm (Gale and Shapley, 1962)

    While some man is free, he proposes to the best woman he has not yet proposed to. If she is free she accepts; if she is engaged she keeps the better of the two, and the other becomes free.

    Why it works

    • It ends: each man proposes to each woman at most once: at most n² steps.
    • Everyone is matched: a woman who has had a proposal is never free again; if a man had tried everyone and stayed free, every woman would be engaged, which the equal numbers rule out.
    • Stability: if m prefers w to his wife, he proposed to w earlier, and she turned him down for someone better.

    The result is the best stable matching possible for the proposers.

    The input

    Row m of M is man m's list of women, best first, and row w of W is woman w's list of men; people are numbered from 0.