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