Skip to content

Stable Marriage Hot Sheet

Use this page when the statement is really about two-sided preferences and the word that matters is stable, not maximum or minimum.

Do Not Use When

  • the objective is maximum number of pairs in a compatibility graph
  • the objective is minimum total cost across a perfect assignment
  • the model has quotas, ties, incomplete lists, or roommate-style one-set matching

Choose By Signal

Core Invariants

  • each proposer only moves forward through the preference list
  • each accepter keeps the best proposer seen so far
  • every rejection is permanent
  • when the queue empties, the result is stable and proposer-optimal for this proposing side

Main Traps

  • mistaking stability for minimum total dissatisfaction
  • forgetting that swapping the proposing side flips which side gets the optimal stable outcome
  • rebuilding accepter preference comparisons on the fly instead of precomputing inverse ranks
  • feeding ties or missing partners to a starter that assumes strict full rankings

Exact Starters In This Repo

Reopen Paths