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