An Introduction to Fair Division

Lectures by Rohit Vaish

Lectures ⸱ Practice Questions: Part 1 | Part 2 | Part 3 | Part 4

Questions based on the second lecture: Indivisible Goods

1. For the setting of indivisible goods, which of the following is true?
1. A proportional allocation of the goods can always be achieved.
2. An allocation of the goods can always be achieved.
3. All allocations are proportional.
4. All proportional allocations are .
5. The utility of an -fair share for any agent is always at least as much as that of a proportional fair share.
6. The utility of a proportional fair share for any agent is always at least as much as that of an -fair share.
2. Show that even with two agents and identical valuations, deciding the existence of an envy-free allocation is -Complete.
3. Prove or disprove: An allocation is also an - allocation.
4. Show the step-by-step implementation of the envy-graph algorithm for the following instance and construct the allocation based on the procedure.
5.  0 2 0 1 1 1 2 5 10 1 1 4 2 10 1
6. Suppose we want to fairly allocate a set M of indivisible chores, for which each agent has negative utility, i.e., . What is the natural analogue of EF1 allocation in this case? Design a polynomial-time algorithm to obtain an EF1 allocation when agents have additive valuations.