Following example task for my question:
Identify all stable matchings and argue that there are no more.
Following setting:
M:={Alex, Blake, Charlie, Dakota}
W:={Jordan, Kelsey, Leslie, Morgan}
Alex: Jordan > Kelsey > Leslie> Morgan
Blake: Kelsey > Jordan > Leslie > Morgan
Charlie: Jordan > Kelsey > Leslie > Morgan
Dakota: Jordan > Kelsey > Leslie > Morgan
Jordan: Charlie > Alex > Blake > Dakota
Kelsey: Dakota > Blake > Alex > Charlie
Leslie: Blake > Dakota > Charlie > Alex
Morgan: Alex > Charlie > Dakota > Blake
Now to my problem.
The only way I know of to quickly find a stable matching by hand is with the Gale-Shapley algorithm. However, this only provides one solution and that is this one
Alex -> Morgan
Blake -> Leslie
Charlie -> Jordan
Dakota -> Kelsey.
The question would now be how do you get the others out, if there are any, and how do you argue/see that there can no longer be any more stable matchings?
Best Answer
Well, to begin with, there are only $4! = 24$ possible matchings here, stable or otherwise. So even the awful brute force approach is still theoretically possible.
To simplify the casework, it may help you to know the following fact about the Gale-Shapley algorithm: out of all possible stable matchings, the one it finds is best for every man and worst for every woman (assuming men are doing the proposing).
So, for example, the matching you found matches Alex to Morgan, who is last on Alex's preference list. This can only happen if there is no stable matching where Alex does better. So every stable matching matches Alex to Morgan. (Already we've narrowed our options down to only $3! = 6$ candidates for stable matchings.)
Reason further along these lines and you'll be able to prove that in this case, no other stable matching is possible.