1. (Opposing interets of men and women) Consider an arbitrary marriage problem. Let f be the men-proposing DA matching of this problem. Let f be an arbitrary stable matching of this problem. We show via the following steps that every woman finds her outcome at f no worse than her outcome at fM. (Similarly, you can show that every man finds his outcome at f no worse than his outcome at women-proposing DA matching.) (a) Suppose to the contrary that woman w finds her outcome at f worse than her outcome at fM. Argue that woman w must not be single at fM. (Hint: f is stable.) (b) Assume that woman w marries man m at fM. Argue that man mi's outcome at f is not to marry woman w, i.e., f(m) + w. (Hint: Woman w is happier at fM.) (c) Use the conclusion in the previous step to argue that man m cannot be indifferent between his outcome at f, f(m), and his outcome at fM, w. (d) Argue that man m cannot prefer w to f(m). (Hint: f is stable). (e) Argue that man m must prefer f(m) to w. Then find a contradiction to the result we have proved in class, that is, men-proposing DA algorithm is optimal for men.