Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 37 ยท Applications

Stable Matching and the Gale-Shapley Algorithm

Match two sides with preferences using the Gale-Shapley deferred acceptance algorithm. Learn stability, proposer-optimality, and real markets such as residency matching.

Some markets cannot use prices to decide who gets what. Medical graduates are assigned to hospitals, students to schools, kidney donors to patients. Each side has preferences over the other, and the question is how to pair them up so that nobody has a reason to break the arrangement. Matching theory, part of market design, answers this. Its central tool, the Gale-Shapley deferred acceptance algorithm, earned Alvin Roth and Lloyd Shapley the 2012 Nobel Prize in economics.

The marriage problem

There are n men and n women (the classical story; any two sides work). Each person ranks everyone on the other side. A matching pairs each man with exactly one woman. A blocking pair is a man and a woman who are not matched together, but each prefers the other to their current partner. A matching is stable if it has no blocking pair: nobody can profitably elope.

Stability is the matching counterpart of Nash equilibrium: no pair has an incentive to deviate.

The deferred acceptance algorithm

  1. Every unmatched man proposes to the highest-ranked woman on his list to whom he has not yet proposed.
  2. Each woman tentatively keeps the best proposal received so far (including her current partner) and rejects the others.
  3. Rejected men go on to their next choice. Repeat until nobody is rejected.

"Deferred" means that a woman never accepts permanently until the process ends: she can trade up.

Deferred acceptance

Propose Each free man asks his top remaining choice
Hold Each woman keeps her best offer
Reject Others move to their next choice
Stop When no one is rejected

It always ends after at most n squared proposals.

1 / 2
Python Gale-Shapley in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Checking stability

A good habit: verify that the output has no blocking pairs. The function below checks every man-woman pair.

Python Finding blocking pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The arbitrary matching has a blocking pair: Adam and Zoe prefer each other to their partners. The output of the algorithm has none.

Properties

  • Always terminates with a stable matching; at most n squared proposals.
  • Proposer-optimal: among all stable matchings, each proposing man gets the best partner he can have in any stable matching. Simultaneously, each woman gets her worst stable partner. Who proposes matters a lot.
  • Strategy-proof for the proposing side: men cannot gain by lying about their preferences. The receiving side (women) can sometimes benefit by misreporting.
  • Many stable matchings can exist, forming a lattice; the proposer-optimal and receiver-optimal ones are the two extremes.
Python Proposer-optimal versus receiver-optimal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When men propose, each gets his first choice (m1-w1, m2-w2). When women propose, each woman gets hers (w1-m2, w2-m1). Both are stable, and each side prefers the version in which it proposes.

Real markets

  • Residency matching: the US National Resident Matching Program (NRMP) uses a hospital-proposing or applicant-proposing variant of deferred acceptance. The version with applicants proposing is strategy-proof for applicants.
  • School choice: New York City and Boston moved from "immediate acceptance" (where gaming was rewarded) to deferred acceptance so that families can safely list true preferences.
  • Many-to-one matching: a hospital can take several residents. Its preferences over sets of applicants must be "substitutable", and capacities are handled by letting a hospital hold its best quota of applicants.
  • Kidney exchange: patients with willing but incompatible donors swap donors in cycles. Here nobody has a "side"; the top trading cycles algorithm finds efficient, strategy-proof swaps.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a blocking pair?

    Such a pair would break away, so a stable matching has none.
  2. 2. Which side gets its best possible stable partner in the deferred acceptance algorithm?

    The algorithm is proposer-optimal: each proposer gets the best partner available in any stable matching.
  3. 3. How many proposals can the algorithm make at most with n men and n women?

    Each man proposes to each woman at most once, so at most n * n proposals.
  4. 4. Why did cities such as Boston and New York adopt deferred acceptance for school choice?

    Strategy-proofness for the proposing side removes the incentive to game the system.

Summary

  • Stable matching: no blocking pair, so no two agents prefer each other to their current partners.
  • Gale-Shapley deferred acceptance always finds a stable matching in at most n squared proposals.
  • It is optimal for the proposing side and worst for the receiving side among stable matchings.
  • Truthful reporting is dominant for the proposers.
  • Variants run residency, school-choice and kidney-exchange markets.

Next: Nash Bargaining