Modified Exercise $1\mathrm{.}5($pg$.24-25)$

The Stable Matching Problem, as discussed in the lecture, assumes that all Ph$.$D$.$ advisors

and graduate students have a fully ordered list of preferences. In this problem we will consider

a version of the problem in which Ph$.$D$.$ advisors and graduate students can be indifferent

between certain options. As before we have a set $P$ of $n$ Ph$.$D$.$ advisors and a set $G$ of $n$

graduate students. Assume each Ph$.$D$.$ advisor and each graduate student ranks the members

of the opposite set, but now we allow ties in the ranking. For example $($with $n=4),$ a student

could say that $p_1$ is ranked in first place; second place is a tie between $p_2$ and $p_3($they have

no preference between them$)$; and $p_4$ is in last place. We will say that $s$ prefers $p$ to $p^{\text{'}}$ if $p$ is

ranked higher than $p^{\text{'}}$ on their preference list $($they are not tied$).$

With indifferences in the rankings, there could be two natural notions for stability. And for

each, we can ask about the existence of stable matchings, as follows.

$($a$)$ A strong instability in a perfect matching S consists of a Ph$.$D$.$ advisor $p$ and a student

$s,$ such that each of $p$ and $s$ prefers the other to their partners in S $.$ Does there always

exist a perfect matching with no strong instability? Either give an example of a set of

Ph$.$D$.$ advisors and students with preference lists for which every perfect matching has

a strong instability; or give an algorithm that is guaranteed to find a perfect matching

with no strong instability.

$($b$)$ A weak instability in a perfect matching S consists of a Ph$.$D$.$ advisor $p$ and a student $s,$

such that their partners in S are $s^{\text{'}}$ and $p^{\text{'}},$ respectively, and one of the following holds:

$p$ prefers $s$ to $s^{\text{'}},$ and $s$ either prefers $p$ to $p^{\text{'}}$ or is indifferent between these two

choices; or

$s$ prefers $p$ to $p^{\text{'}},$ and $p$ either prefers $s$ to $s^{\text{'}}$ or is indifferent between these two

choices.

In other words, the pairing between $p$ and $s$ is either preferred by both, or preferred by

one while the other is indifferent. Does there always exist a perfect matching with no weak

instability? Either give an example of a set of Ph$.$D$.$ advisors and students with preference

lists for which every perfect matching has a weak instability; or give an algorithm that is

guaranteed to find a perfect matching with no weak instability.