Given $n>1$ women and men. Let $M$ be the stable matching given by the Gale Shapley algo with men proposing. Is there a stable matching instance such that:
changing one man’s preference list results in matching $M’$ – a stable matching given by the Gale Shapley algo with men proposing under this slightly altered preference list – where every man strictly prefers his partner in $M$ over his partner in $M’$ (according to their original preference list used to get matching $M$).
The answer should be yes but I’m not sure how or why. The first thing that came to mind is to try to use induction. I came up with a scenario for $n=2$ but I don’t know how to extend it to greater $n$.