Multi-agent Decision Making COMP 4418 – Assignment 3
Due 25 Nov. 2020, 15:00
Total Marks: 50
Late Penalty: 10 marks per day
Worth: 15% of the course
Consider a resource allocation setting in which indivisible items are to be allocated to agents, and agents have positive and additive utilities over the items.
Prove or disprove the following:
1. If an allocation is proportional, it is envy-free.
2. If an allocation satisfies MmS fairness, it is proportional. 3. If an allocation is envy-free, it is Pareto optimal.
Question 2 (10 marks) Consider a Shapley-Scarf housing market with a set of agents N = {0,1,2,3,4}, a set of items O = {o0,o1,o2,o3,o4}, and 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.
0 : o0,o4,o2,o1,o3 1 : o0,o2,o4,o1,o3 2 : o3,o0,o2,o4,o1 3 : o0,o2,o3,o1,o4 4 : o3,o2,o1,o4,o0
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 3 (10 marks) Consider Shapley-Scarf housing markets in which we are only allowed to obtain allocations in which at most two agents are a part of a trading cycle and each agent can be a part of at most of one trading cycle. Discuss at least three axiomatic properties that you consider to be desirable for the problem and explain why. Design a polynomial-time algorithm for the problem and prove it satisfies two of these properties.
Question 4 (10 marks) Consider the following market with 10 students N = {0,1,2,3,4,5,6,7,8,9},
Question 1 (10 marks)
1
Due Date: 25 Nov. 2020, 15:00 COMP 4418 – Assignment 3
and three schools C = {c0,c1,c2}. All the schools have the same capacity 4. The prefer- ences of the students are as follows from left to right in decreasing order of preference.
≻0: c0,c2,c1 ≻1: c0,c2,c1 ≻2: c0,c2,c1 ≻3: c0,c1,c2 ≻4: c2,c0,c1 ≻5: c2,c0,c1 ≻6: c2,c0,c1 ≻7: c2,c0,c1 ≻8: c2,c0,c1 ≻9: c2,c1,c0
The priorities of the schools are as follows from left to right in decreasing order of priority.
≻c0:9,4,1,5,3,8,6,7,2,0 ≻c1:5,4,3,0,6,2,7,1,9,8 ≻c2:2,6,9,7,3,5,4,8,1,0
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 for the example is Pareto optimal for the students.
Question 5 (10 marks) Consider a resource allocation setting in which agents have ad- ditive positive utilities over indivisible items. Consider the sequential allocation rule in which the policy of turns is (1,2,…,n)∗ where the policy (1,2,…,n)∗ indicates the turns 1,2,…,n repeat. Prove or disprove that rule
1. returns a Pareto optimal allocation. 2. returns a proportional allocation. 3. returns an EF1 allocation.
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 25. Nov 2020, 15:00
2
Due Date: 25 Nov. 2020, 15:00 COMP 4418 – Assignment 3
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