Matching with Couples

Couples in the NRMP submit joint rankings of hospital pairs. This seemingly small extension breaks the guaranteed existence of stable matchings, requiring sophisticated heuristics.

Scenario

Algorithm Pseudocode

Couples-Extended DA:
while ∃ free couple (r1, r2) with
  remaining joint preference pairs:
    (h1, h2) ← next pair on couple list
    For each position in the pair:
      if hospital has room: tentatively hold
      else if hospital prefers r_i to worst:
        displace worst, tentatively hold r_i
      else: reject this pair
    if BOTH accepted: keep pair
    else: undo any tentative holds
    Displaced residents re-enter the pool

NOTE: This may cycle! No convergence
guarantee with couples.

Participants

Event Log

Select a scenario and click "Run Algorithm".

~1,100

Couples participate in NRMP annually (2023 data)

The NRMP started handling couples in 1984. A stable matching doesn't always exist with couples, but the NRMP heuristic finds good solutions in practice.

Matching Visualization

Instability Cascade

When couples cause a chain of rejections that cycles back, no stable matching exists.

Key Theorem

Roth (1984): Instability with Couples

The extension of Gale-Shapley to matching with couples does NOT guarantee a stable matching exists. This is a fundamental impossibility result, not a flaw in any specific algorithm.

The NRMP uses a sophisticated heuristic based on Roth-Peranson (1999) that handles couples and typically finds stable or near-stable matchings in practice, even when theoretical guarantees fail.