Fair Allocations
COMP 4418 – Assignment 3
Due 21 November 2025, 17:00
Total Marks: 100
Late Penalty: 20 marks per day
Worth: 15% of the course
Note: For ALL the questions, a complete solution must be provided. Proofs or justifying
calculations are required to obtain full marks. Answers stated without adequate explanation
will receive at most half credit.
Question 1 (20 marks) Consider a fair division instance ⟨N,M,v⟩ with n agents and m
items. For each of the following statements, please decide whether it is true or false.
Support your answer with an example or a proof, as needed.
1. (5 marks) Any Pareto Optimal allocation must also maximize Utilitarian Social Wel-
fare (USW).
2. (5 marks) An allocation that is MMS must maximize Egalitarian Social Welfare
(ESW).
3. (5 marks) Any allocation that satisfies PROP is also MMS.
4. (5 marks) Every EF1 allocation must give each agent ⌈mn ⌉ or ⌊mn ⌋ number of items.
Question 2 (20 marks) Consider the following instance with n= 4 and m= 8.
g1 g2 g3 g4 g5 g6 g7 g8
v1 5 5 10 10 0 0 5 5
v2 5 5 10 5 0 0 5 0
v3 5 5 5 5 0 1 1 1
v4 10 5 8 9 3 0 5 4
For this instance, consider running the standard round robin algorithm to find an EF1 alloca-
tion. We shall look at how different orderings over agents can lead to different allocations.
For each sub-question, show what would be the choices of each agent in each round to lead
to this allocation. For the given instance, identify:
1. (10 marks) The ordering over agents which leads to the following allocation: A =
(A1,A2,A3,A4), where A1 = {g1,g5}, A2 = {g4,g8}, A3 = {g3,g7} and A4 = {g2,g6}.
2. (5 marks) An alternate EF1 allocation that can result from the same ordering which
would Pareto dominate A.
1
Due Date: 21 Nov. 2025 COMP 4418 – Assignment 3
3. (5 marks) An alternate ordering for the standard round robin algorithm that would
result in the allocation identified in the previous part.
Question 3 (20 marks) Consider an indivisible item setting with m> n where each agent
has the same value for all items. That is, for any i ∈ N and g ̸= g′ ∈ M, we have that
vi(g) = vi(g′)> 0. However, agent valuations are not (guaranteed to be) identical. That is,
there may be i ̸= j and g ∈M, s.t. vi(g) ̸= v j(g). For this setting:
1. (5 marks) Prove that there always exists a maximum USW allocation that gives every
item to the same agent.
2. (5 marks) Prove that an EF1 allocation will always be MMS.
3. (10 marks) Give examples of instances such that:
a. A PROP allocation does not exist.
b. No leximin optimal allocation is MMS.
Question 4 (20 marks) Find the random assignment as a result of the following rules.
1. Probabilistic Serial (PS)
Consider the random assignment problem with 4 agents {1,2,3,4}with the following
preferences over 4 items {o1,o2,o3,o4}.
≻1: o3 ≻1 o1 ≻1 o4 ≻1 o2
≻2: o1 ≻2 o2 ≻2 o4 ≻2 o3
≻3: o1 ≻3 o4 ≻3 o2 ≻3 o3
≻4: o2 ≻4 o3 ≻4 o1 ≻4 o4
(10 marks) Compute the random assignment of the PS rule.
2. Random Serial Dictator (RSD)
Consider the random assignment problem with 3 agents {1,2,3} with the following
preferences over 3 items {o1,o2,o3}.
≻1: o3 ≻1 o1 ≻1 o2
≻2: o3 ≻2 o1 ≻2 o2
≻3: o1 ≻3 o3 ≻3 o2
(10 marks) Compute the random assignment of the RSD rule.
Question 5 (5 marks) Prove or disprove that reassignment stability implies Pareto opti-
mality (PO).
2
Due Date: 21 Nov. 2025 COMP 4418 – Assignment 3
Question 6 (15 marks) Consider the following instance with n= 4 and m= 8. Consider
the allocation A in which A1 = {g1}, A2 = {g2}, A3 = {g4}, and A4 = {g3}.
g1 g2 g3 g4
v1 6 4 5 2
v2 4 7 2 5
v3 2 6 1 5
v4 3 1 3 5
1. (3 marks) Prove or disprove that the allocation is envy-free.
2. (12 marks) Prove or disprove that the allocation is envy-freeable. Compute the corre-
sponding envy-graph with the amount of envy on the edge weights. Find the subsidy
needed to be given to each agent in order to make the allocation envy-free or show
that no such subsidy exists.
SUBMISSION
• Submit your solution directly via Moodle in the assessment hub at the end of the
Moodle page. Please make sure that your manuscript contains your name and zID.
• Your answers are to be submitted in a single PDF file. We will NOT accept any other
file formats. Please make sure that your solutions are clearly readable.
• The deadline for this submission is 21 November 2025, 17: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

学霸联盟