Five Couples, Five Matchings

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?

• game theory

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.