Multi-agent Decision Making – Assignment 3

Multi-agent Decision Making
COMP 4418 – Assignment 3

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) Prove or disprove that the Condorcet winner always has the maximum Borda score among all the alternatives. Prove or disprove that the Condorcet winner
has at least half of the Borda score of the Borda winner.
1
Due Date: 26 Oct. 2018, 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 → 2
O
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 misport her
preference to get a better a match? 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 n agents have
positive and additive utilities over m items. Recall that the algorithm of Lipton et al. (2004)
takes time O(n
3m) to compute an EF1 (envy-free up to one item) allocation. Design an
algorithm that takes time O(nm) and computes an EF1 allocation. Prove the running time
of the algorithm. Prove that the algorithm always returns an EF1 allocation. Discuss any
advantage that the algorithm of Lipton et al. (2004) may have over the new algorithm.
2
Due Date: 26 Oct. 2018, 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 26 Oct. 2018, 15:00