# An Introduction to Fair Division

— **Lectures by Rohit Vaish**

### Questions based on the second lecture: Indivisible Goods

- For the setting of indivisible goods, which of the following is true?
- A proportional allocation of the goods can always be achieved.
- An allocation of the goods can always be achieved.
- All allocations are proportional.
- All proportional allocations are .
- The utility of an -fair share for any agent is always at least as much as that of a proportional fair share.
- The utility of a proportional fair share for any agent is always at least as much as that of an -fair share.
- Show that even with two agents and identical valuations, deciding the existence of an envy-free allocation is -Complete.
- Prove or disprove: An allocation is also an - allocation.
- Show the step-by-step implementation of the envy-graph algorithm for the following instance and construct the allocation based on the procedure.
- 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.

0 | 2 | 0 | 1 | 1 | |

1 | 2 | 5 | 10 | 1 | |

1 | 4 | 2 | 10 | 1 |