Men's Preferences

α: A > B > C
β: B > C > A
γ: C > A > B

Women's Preferences

A: β > γ > α
B: γ > α > β
C: α > β > γ

Lattice of Stable Matchings

Men-Optimal (top)
Middle matching
Women-Optimal (bottom)

Click a lattice node to view matching

Conway's Lattice Theorem (1976)

The set of all stable matchings, ordered by men's preferences, forms a finite distributive lattice. The men-optimal matching (produced by men-proposing GS) is the unique supremum (top), and the women-optimal matching (produced by women-proposing GS) is the unique infimum (bottom).

For every pair of stable matchings M and M', the "join" (where each man gets his preferred partner from M or M') and the "meet" (where each man gets his less-preferred partner) are both also stable matchings.
Verification: Why these are the only 3 stable matchings

For 3 men and 3 women with these cyclic preferences, we can verify all 6 possible perfect matchings (3! = 6) and check each for blocking pairs:

  • M1: {αA, βB, γC} — Stable (men-optimal: each man gets 1st choice)
  • M2: {αB, βC, γA} — Stable (middle: each man gets 2nd choice)
  • M3: {αC, βA, γB} — Stable (women-optimal: each woman gets 1st choice)
  • {αA, βC, γB} — Unstable: (β,B) is a blocking pair
  • {αB, βA, γC} — Unstable: (γ,A) is a blocking pair
  • {αC, βB, γA} — Unstable: (α,A) is a blocking pair