Multi-agent Decision Making
COMP 4418 – Assignment 2
Due 02 Nov. 2021, 15:00
Total Marks: 100
Late Penalty: 20 marks per day
Worth: 15% of the course
Question 1 (20 marks)
1. Prove or disprove that a Condorcet winner is the plurality winner.
2. Prove that a Condorcet winner may not exist.
3. Prove or disprove that the Condorcet winner has at least 3/4-th of the Borda score of
the Borda winner.
4. Prove or disprove that the Condorcet winner has at least 1/4-th of the Borda score of
the Borda winner.
Question 2 (20 marks) Consider the following preference profile of voters.
1 : c � d � b � a
2 : d � c � b � a
3 : a � d � c � b
1. Prove or disprove that the preference profile is single-peaked with respect to some
order of alternatives.
2. Prove or disprove that a Condorcet winner exists for the preference profile.
3. Compute the pairwise majority graph for the preference profile.
4. Compute the Top Cycle set for the preference profile.
Question 3 (20 marks) Consider a resource allocation setting in which n agents have
positive additive utilities over m > n invisible items. The items are allocated to agents in
the following manner. The agents come in order (1,2,3, . . . ,n,n,n− 1,n− 2, . . . ,1)∗ and
are given a most preferred unallocated item.
1. Prove or disprove that the algorithm returns a Pareto optimal allocation.
2. Prove or disprove that the algorithm returns an envy-free allocation.
3. Prove or disprove that the algorithm returns a proportional allocation.
1
Due Date: 02 Nov. 2021, 15:00 COMP 4418 – Assignment 2
4. Prove or disprove that the algorithm returns an EF1 allocation.
5. Prove or disprove that the algorithm is strategyproof.
Question 4 (20 marks) Consider Shapley-Scarf housing markets in which we are only
allowed to obtain allocations in which each agent can be a part of at most of one trading
cycle, and each trading cycle can involve at most two agents. Such as allocations are called
feasible.
1. Does the top trading cycles algorithm return a feasible allocation as defined above?
Justify your answer.
2. Discuss at least three axiomatic properties that you consider to be desirable for the
problem and explain why.
3. Prove or disprove that the following algorithm is strategyproof: take an ordering of
agents and each agent i in its turn exchanges items with some remaining agent who
has the item that is most preferred by i among the remaining items.
4. Design an algorithm that satisfies at least two desirable axiomatic properties for the
problem.
Question 5 (20 marks) Consider the following school choice problem with four students
1, 2, 3, 4 and four schools c1, c2, c3, c4 with each school having exactly one seat. Suppose
the preferences of agents and the priorities of the institutions are represented in the ordered
list in decreasing order of preference/priority.
1 : c2,c1,c3,c4 c1 : 1,3,2,4
2 : c1,c2,c3,c4 c2 : 2,1,3,4
3 : c1,c2,c3,c4 c3 : 2,3,1,4
4 : c4,c1,c2,c3 c4 : 4,3,2,1
1. Compute the outcome of the agent/student proposing deferred acceptance algorithm
2. Is the outcome Pareto optimal (for the agents)? Justify your answer.
3. Compute the set of all matchings that satisfy the following properties: each agent is
matched to a school and justified envy-freeness is satisfied. Justify your answer.
4. For the school choice problem, present a polynomial-time algorithm to compute an
allocation that is Pareto optimal (from the perspective of agents).
2
Due Date: 02 Nov. 2021, 15:00 COMP 4418 – Assignment 2
SUBMISSION
• You will need to answer the questions in a file named assn2.pdf. Submit using
the command:
give cs4418 assn2 assn2.pdf
• Your answers are to be submitted in a single PDF file.
• The deadline for this submission is 02 Nov. 2021, 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