An Example I Heard at DIMACS for Instability in Gale and Shapley’s Roommate Problem
Gale and Shapley (1962). They have the Marriage Problem (match boys and girls so that there is no boy and girl who would like to leave their current pair and form a new pair together) and the Roommate Problem (match boys so that there is no pair of boys who would like to leave their current pair and form a new pair together).
Let there be four boys. Everybody hates Delta. Alpha likes beta best, then gamma. Beta likes gamma best, than alpha. Gamma likes alpha best, then beta.
Then no pairing is stable, in the sense that there are always two boys who would like to split off and start a new room. Start with AB, GD. Then G and B will split off to create A, BG, D. But then both A and G would like to deviate, to give AG, B, D. But then B would deviate, to get AB, G, D, where we started.