1. 40 marks Matching markets Answer the following questions. (a) 5 marks Construct a two-sided matching problem in which there is more than one stable matching. (b) 5 marks Consider a two-sided matching market with men on one side and women on the other. If all men have a different top choice, how many rounds does it take for the deferred acceptance algorithm to converge? (c) 5 marks Consider a two-sided matching market with men on one side and women on the other. If all men have have the exact same preferences, how many rounds does it take for the men-proposing deferred acceptance algorithm to converge? (d) 5 marks Decide if you think the following statement is true or false. If true, give a brief justification. If false, give a counterexample. Consider a two-sided stable matching problem in which there is a man m and a woman w, such that m is w's top choice and wis m's top choice. Then every stable matching contains the pair (m, w). (e) 10 marks Consider a two-sided market with four women on one side and four men on the other. In decreasing order of preference, the preferences for everybody are given as follows: W ms, M, M2, M4, M3 w2 m3, m2, m4, mi, m5 W3 M, M3, M4, M5, M W M, M5, M4, M3, M ws: M, M, M5, M3, M m : W, W, W4, W5, W3 m2 W4, W2, W1, W3, ws m3: W, W5, W3, W, W m W, W, W3, W2, W5 m5: W, W, W, W5, W3 Find a stable matching using the DA algorithm when the woman make proposals. Find a stable matching using the DA algorithm when the men make proposals. (f) [10 marks Consider the following one-sided matching market. That is, anyone can match with anyone (this is often referred to as the "roommate" problem). There are four people, Ann, Barry, Clara, and Dan. They must pair off as each will share a two-bed room. Each has preferences over which of the others they would like to have as a room mate. In decreasing order of preference, the preferences for everybody are given as follows: