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 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.