# An Introduction to Fair Division

— **Lectures by Rohit Vaish**

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

- List all the Pareto Optimal allocations () in the following input with agents. How many of them are ?
- An allocation under binary additive valuations maximises the Nash Welfare
- If and only if there is no directed path from an agent to an agent in such that .
- If and only if there is no directed path from an agent to an agent in such that .
- If and only if there is no directed path from an agent to an agent in such that .
- If and only if there is no directed path from an agent to an agent in such that .
- Construct a fair division instance where an allocation that maximizes nash welfare may not be envy-free.
- Prove that an allocation that maximizes nash welfare is .

3 | 1 | 8 | 0 | |

5 | 0 | 7 | 3 |

(Hint: Suppose it violates , then show that there exists an allocation which has a higher nash welfare)