The Problem

The stable marriage problem does not handle divorces. This is because we assume everyone is interested in everyone else of the opposite sex 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. In this problem, assume that men propose to women $($as

done in the book and unlike what we did in the lecture$)$ and consider the following scenario.

Given an instance of the stable marriage problem $($i$.$e$.$ set of women $W$ and the set of men $M$ along with their preference lists: $L_w$ and $L_m$ for every winW and minM

respectively$),$ call a woman winW a reformer if the following property holds. There exists an $L_w^{\text{'}}$ such that if $w$ changes her preference list to $L_w^{\text{'}}($from $L_w)$ then the Gale$-$

Shapley algorithm matches everyone to someone else. In other words, let $S_{\text{o}\text{r}\text{i}\text{g}}$ be the stable marriage output by the Gale$-$Shapley algorithm for the original input and $S_{\text{n}\text{e}\text{w}}$ be

the stable marriage output by the Gale$-$Shapley algorithm for the new instance of the problem where $w^{\text{'}}\text{'}$s preference list is replaced by $L_w^{\text{'}}($but everyone else has the same

preference list as before$).$ Then

$S_{\text{o}\text{r}\text{i}\text{g}}{S}_{\text{n}\text{e}\text{w}}=\frac{O}{.}$

Here are the two parts:

Part $($a$)$: You will first solve a simpler version of the problem. For every integer $n3$ argue the following: There exists an instance of the stable marriage problem with

$n$ men and $n$ women such that there is a woman $w$ such that if she changes her preference list from $L_w$ to $L_w^{\text{'}}$ then we have

$S_{\text{o}\text{r}\text{i}\text{g}}{S}_{\text{n}\text{e}\text{w}}.$

Part $($b$)$: For every integer $n3$ argue the following: There exists an instance of the stable marriage problem with $n$ men and $n$ women such that there is a woman

who is a reformer.

Common Mistake

A common mistake for this problem is to present an instance that solves part $($a$)$ but not part $($b$).$