The Lattice of Stable Matchings

For the 3-person symmetric example, there are exactly 3 stable matchings. They form a distributive lattice under the dominance ordering: men-optimal at the top, women-optimal at the bottom, connected by rotations.

Preference Lists

Men	Preferences
α	A > B > C
β	B > C > A
γ	C > A > B

Women	Preferences
A	β > γ > α
B	γ > α > β
C	α > β > γ

Lattice Diagram

Click a matching node to see its bipartite graph below.

Men-optimal

Middle

Women-optimal

Selected Matching

M_men (Men-Optimal)

Bipartite Graph

Rotations Between Matchings

A rotation is a cyclic permutation where each man trades his current partner for the next man's partner (in the cycle), moving from one stable matching to another.

Rotation σ1: M_men → M_mid

α: A → B

β: B → C

γ: C → A

Rotation σ2: M_mid → M_women

α: B → C

β: C → A

γ: A → B

Each step down the lattice applies a rotation: men get worse off, women get better off.

Conway's Lattice Theorem

The set of all stable matchings for a given instance, ordered by male preference (where M ≥ M' if every man weakly prefers his partner in M to his partner in M'), forms a distributive lattice. The unique supremum is the men-optimal matching (produced by male-proposing DA), and the unique infimum is the women-optimal matching (produced by female-proposing DA).

The lattice structure reveals a deep duality: what is best for one side is worst for the other. Rotations are the atomic operations that traverse the lattice.

Conway, J.H. (unpublished, circa 1976); Knuth, D.E. (1976). "Mariages stables et leurs relations avec d'autres problemes combinatoires."