The Problem

This problem is inspired by a question raised by Devashish in class. As Devashish's question pointed out, the stable marriage problem does not handles "divorces." This is because we assume everyone is interested in everyone else of the opposite gender and we assume that the preferences do not change.

In this problem, we will see the effect of changes in preferences in the outcome of the Gale-Shapley algorithm (for this problem you can assume the version of the Gale-Shapley algorithm that we did in class where the women do all the proposing).

Given an instance of the stable marriage problem (i.e. set of men MM and the set of women WW along with their preference lists: LmLm and LwLw for every m∈Mm∈M and w∈Ww∈Wrespectively), call a man m∈Mm∈M a home-wrecker if the following property holds. There exists an L′mLm′ such that if mm changes his preference list to L′mLm′ (from LmLm) then the Gale-Shapley algorithm matches everyone to someone else. In other words, let SorigSorig be the stable marriage output by the Gale-Shapley algorithm for the original input and SnewSnew be the stable marriage output by the Gale-Shapley algorithm for the new instance of the problem where mm's preference list is replaced by L′mLm′ (but everyone else has the same preference list as before). Then Sorig∩Snew=∅Sorig∩Snew=∅.

For every integer n≥2n≥2 prove the following: There exists an instance of the stable marriage problem with nn men and nn women such that there is a man who is a home-wrecker.