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 first lecture: Cake Cutting - I

  1. In the setting of Cake Cutting, which of the following is true?
    1. An envy-free allocation is also proportional.
    2. A proportional allocation is also envy-free.
    3. An allocation can be simultaneously envy-free and proportional.
    4. All of the above.
  2. Consider the Robertson Webb Query Model, for 2 agents, let the cut and evaluate queries be , (which returns ) and (which returns ). State true/false:
    1. , () and gives a proportional cake division.
    2. , () and gives both the agents a piece of cake that they like strictly more than .
  3. What is the query complexity of Dubins-Spanier protocol for proportional cake division?
  4. Consider a fair division problem involving agents. An agent receives a fair share implies:
    1. The agent receives a share that, in every agent’s opinion, has a value that is equal to 5% or more of the total.
    2. The agent receives a share that, in that agent’s own opinion, has a value that is exactly equal to 5% of the total.
    3. The agent receives a share that, in that agent’s own opinion, has a value that is at least 5% of the total.
    4. The agent receives at least of the total.
  5. Suppose there are agents fighting over a cake. Suppose cuts the cake into pieces say , such that she values them all equally, that is . Which of the following are true?
    1. If and , then, the under the allocation where gets respectively, is envious.
    2. If and , then, the allocation where gets respectively, is envy-free.
    3. If , and , then the allocation where gets can never be envy-free.
  6. Based on Q5c, suppose , and trims the piece into such that , then in order to achieve an envy-free allocation for the pieces , the correct picking order of the agents is:
    1. First , second , then
    2. First , second , then
    3. First , second , then
    4. None of the above orders will guarantee an envy-free allocation of the pieces
  7. Based on Q6, suppose get and are envy-free as yet and remains to be allocated.
    1. An envy-free division of among the agents combined with the envy free division where get may not be necessarily envy-free.
    2. will not be envious even if the entire goes to
    3. will not be envious even if the entire goes to
    4. If cuts into equal pieces (according to her) and , and pick one piece in that order, then all the agents are envy-free.
    5. If cuts into equal pieces (according to her) and , and pick one piece in that order, then all the agents are envy-free.