Econ 4415: Problem Set #4 Qingmin Liu Columbia University April 8, 2021 Abstract Due on 10PM at April 14, 2015. See the syllabus for problem set policies. 1 Deferred Acceptance Algorithm (DA) Consider...

Attached


Econ 4415: Problem Set #4 Qingmin Liu Columbia University April 8, 2021 Abstract Due on 10PM at April 14, 2015. See the syllabus for problem set policies. 1 Deferred Acceptance Algorithm (DA) Consider the following one-to-one two-sided matching problem: There are three men and two women. Let the set of men be M = fm1;m2;m3g and the set of women be W = fw1; w2g. Their preferences are given by �m1 : w1; w2; �m2 : w1; �m3 : w2; w1; �w1 : m3;m2;m1; �w2 : m1;m3: Here, �x for x 2M[N; is the “preference order”of individual x; when we write �m1 : w1; w2; we mean m1 strictly prefers w1 to w2; when we write �m2 : w1; we mean w2 is not acceptable to man m2: A matching � speci…es who is matched with whom. For example, when we write � = f(m1; w1) ; (m2; w2) ; (m3;?)g ; we mean m3 is unmatched while man i is matched with woman i for i = 1; 2: We say that a matching � is individually rational if no individual strictly prefers to stay single rather than take the partner assigned to him/her by the given matching �. 1. Find all the individually rational matchings for this problem. [15pts] 2. Find all the stable matchings for this problem. [15pts] 3. Describe each round of the man-proposing DA as we have done in class (in each round, two kinds of events take place: men propose to women, and women reject o¤ers). Calculate the …nal result of the man-proposing DA. [15pts] 1 4. We say that a matching is weakly Pareto e¢ cient for men if there is no other individually rational matching that every man strictly prefers. Explain in words the di¤erence between the de…nitions of weakly Par- ento e¢ cient matching for men and theman-optimal stable matching. [15pts] 5. Is the result of the man-proposing DA you found above weakly Pareto e¢ cient for men? If your answer is yes, provide a proof. If you answer is no, explain why. [20pts] 6. We say that a matching is strongly Pareto e¢ cient for men if there is no other individually rational matching which every man weakly prefers to the former and at least one man strictly prefers. Is the result of the man-proposing DA you found above strongly Pareto e¢ cient for men? If your answer is yes, provide a proof. If you answer is no, explain why. [20pts] 2