Multi-agent Decision Making COMP 4418 – Assignment 3 Due 28 Nov. 2019, 15:00 Total Marks: 50 Late Penalty: 10 marks per day Worth: 15% of the course a b c d e f g Figure 1: Tournament Question 1 (10 marks) In the tournament in Figure 1, all the arcs missing from the figure are downward arcs. For the tournament in Figure 1, find the (a) the uncovered set (b) the top cycle (c) the set of Copeland winners (d) the set of Banks winners (e) the set of Condorcet winners and give arguments for your answers. Question 2 (10 marks) Consider the following preference profile of voters. 1 : b a c d 2 : c a b d 3 : d b a c Prove or disprove that the preference profile is single-peaked. Prove or disprove that a Condorcet winner exists for the preference profile. 1 Due Date: 28 Nov. 2019, 15:00 COMP 4418 – Assignment 3 Question 3 (10 marks) Consider a Shapley-Scarf housing market with a set of agents N = {1,2,3,4,5}, a set of items O= {o1,o2,o3,o4,o5}, an endowment functionω :N→ 2O such that ω(i) = {oi}. The preferences of the agents are as follows from left to right in decreasing order of preference. 1 : o5,o2,o1,o3,o4 2 : o5,o4,o3,o1,o2 3 : o4,o2,o3,o5,o1 4 : o2,o1,o5,o3,o4 5 : o2,o4,o1,o5,o3 Find the outcome of the TTC (top trading cycles) algorithm. Can agent 4 misreport her preference to get a more preferred allocation? Prove or disprove that the outcome is individually rational. Question 4 (10 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 Find the outcome matching of the student proposing deferred acceptance algorithm and explain how you found the matching. Prove or disprove that the resultant matching is Pareto optimal for the students. Question 5 (10 marks) Consider a resource allocation setting in which 2 agents have additive utilities over m divisible items. For any item, an agent can have positive or negative utility for it. Prove that there always exists an envy-free and Pareto optimal allocation of the divisible items. Design a O(m2) or faster algorithm that computes an envy-free and Pareto optimal allocation and prove that the algorithm returns an envy-free and Pareto optimal allocation. 2 Due Date: 28 Nov. 2019, 15:00 COMP 4418 – Assignment 3 SUBMISSION • You will need to answer the questions in a file named assn3.pdf. Submit using the command: give cs4418 assn3 assn3.pdf • Your answers are to be submitted in a single PDF file. • The deadline for this submission is 28. Nov 2019, 15:00 Academic Honesty and Plagiarism All work submitted for assessment must be your own work. Assignments must be com- pleted individually. We regard copying of assignments, in whole or part, as a very serious offence. Be warned that: • the submission of work derived from another person, or jointly written with someone else will, at the very least, result in automatic failure for COMP4418 with a mark of zero; • allowing another student to copy from you will, at the very least, result in a mark of zero for your own assignment; and • severe or second offences will result in automatic failure, exclusion from the Univer- sity, and possibly other academic discipline. • students are not allowed to derive solutions together as a group during such discus- sions. Students are also warned not to send solution fragments of the assignments to each other in any form (e.g. as email or listings). • In addition, copying/purchasing of solutions that is available on the web is also not permitted. Students are strongly advised to protect their work. Do not leave your terminal/computer unattended, or leave printouts at the printer for others to take. Read the study guide carefully for the rules regarding plagiarism. 3
