# An Introduction to Fair Division

Lectures by Rohit Vaish

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

### Questions based on the fourth lecture: Algorithms for Indivisible Goods

1. List all the Pareto Optimal allocations () in the following input with agents. How many of them are ?
2.  3 1 8 0 5 0 7 3
3. An allocation under binary additive valuations maximises the Nash Welfare
1. If and only if there is no directed path from an agent to an agent in such that .
2. If and only if there is no directed path from an agent to an agent in such that .
3. If and only if there is no directed path from an agent to an agent in such that .
4. If and only if there is no directed path from an agent to an agent in such that .
4. Construct a fair division instance where an allocation that maximizes nash welfare may not be envy-free.
5. Prove that an allocation that maximizes nash welfare is .
6. (Hint: Suppose it violates , then show that there exists an allocation which has a higher nash welfare)