"Consider boys α, β, γ [...] where α ranks β first, β ranks γ first,
γ ranks α first [...] Then for any way of pairing off the boys, one of these three is
not paired with the person he ranks first, and he and his first choice will prefer each other
to their assigned partners." — Gale & Shapley, 1962, Example 3
Preferences
A: B > C > D
B: C > A > D
C: A > B > D
D: A > B > C
All 3 possible pairings — click to examine:
Why No Stable Matching Exists
A, B, and C form a preference cycle: A prefers B, B prefers C, and C prefers A — each over anyone else. In any pairing, one of these three is not with their top choice, and that person and their top choice form a blocking pair. Person D is always the "odd one out" that triggers instability.Preferences
A: B > C > D
B: A > C > D
C: D > A > B
D: C > A > B
Stable matching found: {A-B, C-D}
Check A-B: A's top choice is B, B's top choice is A. Neither has any incentive to deviate.
Check C-D: C's top choice is D, D's top choice is C. Neither has any incentive to deviate.
No blocking pair exists because every person is with their first choice!
Check A-B: A's top choice is B, B's top choice is A. Neither has any incentive to deviate.
Check C-D: C's top choice is D, D's top choice is C. Neither has any incentive to deviate.
No blocking pair exists because every person is with their first choice!