Solution
Five Couples, Five Matchings
Show the problem again
Five men (1 to 5) and five women (A to E) have strict preference lists, most preferred first. - Man 1: C, A, B, E, D - Man 2: E, C, D, A, B - Man 3: D, B, C, E, A - Man 4: A, C, E, B, D - Man 5: A, B, D, C, E - Woman A: 4, 2, 3, 5, 1 - Woman B: 3, 5, 4, 1, 2 - Woman C: 3, 2, 1, 4, 5 - Woman D: 4, 2, 1, 5, 3 - Woman E: 5, 1, 2, 4, 3 A perfect matching of men to women is *stable* if there is no man and woman who are not matched to each other but each prefer the other to their assigned partner (a blocking pair). How many stable matchings exist?
Worked solution
The stable matchings of an instance form a distributive lattice: the man-proposing algorithm produces the man-optimal one, the woman-proposing algorithm the woman-optimal one, and every stable matching lies between them in both preference orders (every man weakly prefers it to the woman-optimal one). The intermediate matchings are found by rotations, which move a group of men down their lists simultaneously. Rather than chase rotations by hand, one can check all 5! = 120 perfect matchings for blocking pairs. Exactly 5 pass the test. Writing each as the partners of men 1 to 5, they are CEDAB (man-optimal), CEBAD, ECDAB, ECBAD and DCBAE (woman-optimal). The structure is visible: from the man-optimal matching, two independent rotations are available (men 1 and 2 swap C and E; men 3 and 5 swap D and B), giving a 2 × 2 square of four matchings, and after both, one more rotation (men 1 and 5 swap E and D) leads to DCBAE. So there are **5** stable matchings. The man-optimal and woman-optimal matchings are two of them, a reminder that Gale-Shapley's output is just one of many stable outcomes and which side proposes matters.
Source: Stable matchings can be numerous (Knuth, Mariages stables, 1976, studies their lattice structure); this instance was found by computer search for AxiomIQ. Statement written for AxiomIQ.