1. (Opposing interets of men and women) Consider an arbitrary marriage problem. Let fM 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 w1 finds her outcome at f worse than her outcome at fM. Argue that woman w1 must not be single at fM. (Hint: f is stable.) (b) Assume that woman w1 marries man m1 at fM. Argue that man m1 's outcome at f is not to marry woman w1, i.e., f(m1)=w1. (Hint: Woman w1 is happier at fM.) (c) Use the conclusion in the previous step to argue that man m1 cannot be indifferent between his outcome at f,f(m1), and his outcome at fM,w1. (d) Argue that man m1 cannot prefer w1 to f(m1). (Hint: f is stable). (e) Argue that man m1 must prefer f(m1) to w1. Then find a contradiction to the result we have proved in class, that is, men-proposing DA algorithm is optimal for men. 1. (Opposing interets of men and women) Consider an arbitrary marriage problem. Let fM 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 w1 finds her outcome at f worse than her outcome at fM. Argue that woman w1 must not be single at fM. (Hint: f is stable.) (b) Assume that woman w1 marries man m1 at fM. Argue that man m1 's outcome at f is not to marry woman w1, i.e., f(m1)=w1. (Hint: Woman w1 is happier at fM.) (c) Use the conclusion in the previous step to argue that man m1 cannot be indifferent between his outcome at f,f(m1), and his outcome at fM,w1. (d) Argue that man m1 cannot prefer w1 to f(m1). (Hint: f is stable). (e) Argue that man m1 must prefer f(m1) to w1. Then find a contradiction to the result we have proved in class, that is, men-proposing DA algorithm is optimal for men