Hospital-Resident Problem

The National Resident Matching Program (NRMP) has matched medical graduates to residency programs since 1952. Alvin Roth discovered in 1984 it used a variant of Gale-Shapley, earning him the 2012 Nobel Prize.

Algorithm Mode

Current NRMP algorithm (since 1998). Residents propose — better for residents.

Resident-Proposing DA:
while ∃ free resident r who
  hasn't proposed to all hospitals:
    h ← r's top unproposed hospital
    if h has vacant slot:
      tentatively match (r, h)
    else if h prefers r to its
      worst current match r':
      unmatch r', tentatively match (r, h)
      r' becomes free
    else:
      h rejects r

Preferences

Residents (blue)

Hospitals (green, quota in brackets)

Event Log

The switch to resident-optimal in 1998 improved outcomes for residents across the board.