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