Question 3 (20 marks) Consider the following school choice problem with five students 1, 2, 3,...

Transcribed Image Text:

Question 3 (20 marks) Consider the following school choice problem with five students 1, 2, 3, 4, 5 and five schools a, b, c, d, and e with each school having exactly one seat. The preferences of the students are as follows from left to right in decreasing order of preference. 1: e,b,a,c,d 2: b,a,c,d,e 3: a,b,c,d,e 4: a,b,c,d,e 5:d,b,c,a,e The priorities of the schools are as follows from left to right in decreasing order of priority. a: 2,4,3,5,1 b: 3,2,4,5,1 c: 3,2,4,5,1 d: 5,2,4,3,1 e: 1,2,3,4,5 1. Find the outcome matching of the student proposing deferred acceptance algorithm, showing working out. Prove or disprove that the resultant matching is Pareto optimal for the students. 2. Suppose that initially, student 1 is allocated to school a, student 2 is allocated to school b, student 3 is allocated to school c, student 4 is allocated to school d, and student 5 is allocated to school e. Apply the Top Trading Cycles (TTC) Algorithm with respect to the students' preferences here and find the output, showing working out. Note that we ignore the schools' priorities here. 3. Give three reasons, with examples if necessary, why the deferred acceptance algo- rithm is preferred for school choice over the TTC algorithm. 4. Give a reason, using an example if necessary, why TTC may be preferred for this school choice setting over the deferred acceptance algorithm. Question 3 (20 marks) Consider the following school choice problem with five students 1, 2, 3, 4, 5 and five schools a, b, c, d, and e with each school having exactly one seat. The preferences of the students are as follows from left to right in decreasing order of preference. 1: e,b,a,c,d 2: b,a,c,d,e 3: a,b,c,d,e 4: a,b,c,d,e 5:d,b,c,a,e The priorities of the schools are as follows from left to right in decreasing order of priority. a: 2,4,3,5,1 b: 3,2,4,5,1 c: 3,2,4,5,1 d: 5,2,4,3,1 e: 1,2,3,4,5 1. Find the outcome matching of the student proposing deferred acceptance algorithm, showing working out. Prove or disprove that the resultant matching is Pareto optimal for the students. 2. Suppose that initially, student 1 is allocated to school a, student 2 is allocated to school b, student 3 is allocated to school c, student 4 is allocated to school d, and student 5 is allocated to school e. Apply the Top Trading Cycles (TTC) Algorithm with respect to the students' preferences here and find the output, showing working out. Note that we ignore the schools' priorities here. 3. Give three reasons, with examples if necessary, why the deferred acceptance algo- rithm is preferred for school choice over the TTC algorithm. 4. Give a reason, using an example if necessary, why TTC may be preferred for this school choice setting over the deferred acceptance algorithm.