Questions

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)