User:Erel Segal/Open questions in fair division

In addition to the List of unsolved problems in fair division, here are some more open questions that I find interesting. As far as I know, they were not published yet.

Open questions in fair cake-cutting

Multi-cake cutting

Consider a cake made of m pairwise-disjoint sub-cakes (e.g., an archipelago made of m islands). It should be divided among n agents. Each agent needs to get a piece overlapping at most k islands, so that they do not have to "jump" too much to get from one part of their plot to another.

What is the largest value that can be guaranteed to each agent, as a function of m, n and k?

Known cases:

• Lower bound (algorithm): $k/(m+nk-k)$
• Upper bound: $\min(1/n,k/(m+n-1))$
• Upper bound can be attained when $k\leq 2$ or $n\leq 2$ or all agents have the same ranking on islands.
• Smallest open case: $n=3$ agents with three different rankings on islands, $k=3$ pieces per agent and $m=4$ islands: the lower bound is 3/10 and the upper bound is 1/3.

Open questions in fair allocation of indivisible items

Approximate fairness with a specified "lucky agent"

In any allocation, after removing envy-cycles, there is at least one agent who does not envy; henceforth "lucky".

Can we find an approximately-fair allocation such that a given agent is lucky?

This question has several interesting applications:

• Suppose a division of similar items is done repeatedly, e.g. house-chores are divided every day anew. Even if the division in each day is approximately-fair, it seems unfair that the same agent is lucky each time. It is fairer to let a different agent in turn be the lucky agent.
• A common approach to indivisible fair division is fair random assignment. If we give each good to an agent selected uniformly at random, then the division is ex-ante envy-free, but might be very unfair ex-post. Is there an algorithm that is fair ex-ante and approximately-fair ex-post? One such algorithm is to select an agent at random, and then find an approximately-fair allocation in which this agent is lucky.

Known cases:

• EF1 for additive valuations can be found by round-robin: the first agent is lucky.
• EF1 for arbitrary valuations and two agents can be found by rounded divide-and-choose: the chooser is lucky.
• EF1+EFX for arbitrary identical valuations can be found. At least one bundle is EF, so the agent who gets it is lucky.

Smallest open case: PROP1 or EF1, for 3 agents, with non-additive and non-identical valuations.

Applications

The questions below relate to various applications of fair division; they are quite soft and should be filled in with details.

Fair load-shedding

In many villages in developing countries, supply of electricity is much lower than the demand. Therefore, some households must sometimes be disconnected from electricity in order to reduce the load on the power plants. These disconnections are called load shedding.

What is a fair way to arrange this load-shedding?

Fair journalism

ּSuppose we want to create a newspaper that will give various opinions their fair share of exposition. Different people might have different preferences about when and how much they want to expose their opinions.

What is a fair way to manage such a newspaper?

Fair division of attention

Consider an aspiring politician who wants to serve his/her prospective voters better, by listening to their requests. However, there are much more requests than a single person can handle. Different requests have different levels of importance, different number of supporters, and require a different amount of attention. What is a fair way for choosing which requests to handle?

Fair division of cabinet ministries

Each time after an election, even when the identity of the prime-minister and the parties in the coalition is known, many weeks are wasted in negotiations regarding how the cabinet ministries should be divided among the parties, as well as regarding other policy and legislation issues. Is there a procedure for fairly dividing ministries (and other issues) among the parties in the coalition, based on their size?