The Stable Marriage Problem

How to read this

• Each matrix cell “a, b”: a = where the row's man ranks the column's woman, b = where she ranks him (1 = favorite). Levitin's Figure 10.11 uses the same format.
• Yellow arrow = a proposal. Green lines/boxes = current pairs. A red ✕ = rejection; a red dashed line = a partner being dumped for someone better.
• Free proposers are listed under the picture. We always pick the first free one in list order, so a rejected proposer proposes again right away.
• A proposer only moves down the list; a receiver only trades up. That's why it ends in at most n² proposals and why no blocking pair survives.

Try this

1. Levitin §10.4 example: predict each response. Tom's proposal to Lea is the twist — Lea trades Bob (her #2) for Tom (her #1), and Bob falls to Ann.
2. In the checker, pair (Bob, Ann), (Jim, Lea), (Tom, Sue). The checker finds the blocking pair (Bob, Lea): he ranks her 1 > 2, she ranks him 2 > 3.
3. Load Two different stable matchings and run with men proposing, then women proposing. Each man gets his #1 in the first run and his #3 in the second — same instance, both stable.
4. Open "all n! matchings" for the Levitin §10.4 example: exactly one of the 6 is stable, so both proposing orders must find it.
5. Pick n = 5 and Random a few times. Count proposals: never more than n² = 25 (in fact at most n² − n + 1 = 21).