In this problem, we will consider what happens in stable matching when we are guaranteed additional structure on the preferences. (a) Suppose that there is a "most popular" man, whom all women rank first. Describe who this man must be matched with in every stable matching, and explain why. (b) Use your insight from the previous part to analyze the case when all women have identical rank- ings Prove that in this case, there is a unique stable matching, and describe it. (c) For the case of the previous problem, describe a simpler algorithm than Gale-Shapley which never has to break any engagements, and computes the unique stable matching. Prove that your algorithm outputs a stable matching. (Your proof may heavily draw on the previous subproblems.)