4. (page 24, Exercise 5, Chapter 1, 25 points) The Stable Matching Problem, as discussed in the text, assumes that all men and women have a fully ordered list of preferences. In this proble, we will consider a version of the problem in which men and women can be indifferent between certain options. As before we have a set of M of n men and a set W of n women Assume each man and each woman ranks the members of the opposite gender, but now we allow ties in the ranking. For example (with n = 4) a woman would say that m is ranked in the first place; second place is a tie between m2 and m (she has no preference between them); and m4 is in last place. We will say that w prefers m to m if m is ranked higher m' on her preference list (they are not tied) With indifferences in the rankings, there could be two natural notions of stability. And for each, we can ask about the existence of stable matchings, as follows. . A strong instability in a perfect matching S consists of a man m and a woman w, such that each of m and w prefers the other to their partner in S. Does there always exist a perfect matching with no instability? Either give an example of a set of men and women with preference lists for which each perfect matching has a strong instability or given an algorithm that is guaranteed to find a perfect matching with no strong instability .A weak instability in a perfect matching S consists of a man m and a woman w, such that their partners in S are and m', respectively and one of the following holds: - m prefers w to u, and w either prefers m tom or is indifferent between these two choices; or -w prefers m tom', and m either prefers to or is indifferent between these two choices. In other words, the pairing between m andwis 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 men and women with preference lists for which each perfect matching has a weak instability; or given an algorithm that is guaranteed to find a perfect matching with no weak instability 4. (page 24, Exercise 5, Chapter 1, 25 points) The Stable Matching Problem, as discussed in the text, assumes that all men and women have a fully ordered list of preferences. In this proble, we will consider a version of the problem in which men and women can be indifferent between certain options. As before we have a set of M of n men and a set W of n women Assume each man and each woman ranks the members of the opposite gender, but now we allow ties in the ranking. For example (with n = 4) a woman would say that m is ranked in the first place; second place is a tie between m2 and m (she has no preference between them); and m4 is in last place. We will say that w prefers m to m if m is ranked higher m' on her preference list (they are not tied) With indifferences in the rankings, there could be two natural notions of stability. And for each, we can ask about the existence of stable matchings, as follows. . A strong instability in a perfect matching S consists of a man m and a woman w, such that each of m and w prefers the other to their partner in S. Does there always exist a perfect matching with no instability? Either give an example of a set of men and women with preference lists for which each perfect matching has a strong instability or given an algorithm that is guaranteed to find a perfect matching with no strong instability .A weak instability in a perfect matching S consists of a man m and a woman w, such that their partners in S are and m', respectively and one of the following holds: - m prefers w to u, and w either prefers m tom or is indifferent between these two choices; or -w prefers m tom', and m either prefers to or is indifferent between these two choices. In other words, the pairing between m andwis 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 men and women with preference lists for which each perfect matching has a weak instability; or given an algorithm that is guaranteed to find a perfect matching with no weak instability