List of unsolved problems in fair division
This page lists notable open problems related to fair division - a field in the intersection of mathematics, computer science, political science and economics.
Open problems in [fair cake-cutting]
Query complexity of [envy-free cake-cutting]
In the problem of envy-free cake-cutting, there is a cake modeled as an interval, and ' agents with different value measures over the cake. The value measures are accessible only via queries of the form "evaluate a given piece of cake" or "mark a piece of cake with a given value". With ' agents, an envy-free division can be found using two queries, via divide and choose. With ' agents, there are several open problems regarding the number of required queries.1. First, assume that the entire cake must be allocated, and pieces may be disconnected. How many queries are required?
- Lower bound: ;
- Upper bound: .
- Lower bound: not known.
- Upper bound:.
- For , there is an algorithm with 54 queries.
- For , no finite algorithm is currently known.
- For, there is an algorithm that attains 1/3, which is optimal.
- For , there is an algorithm that attains 1/7.
- For any, there is an algorithm that attains.
- For, a finite algorithm does not exist for cuts.
- For, Selfridge–Conway procedure solves the problem in finite time with 5 cuts.
- For, the Aziz-Mackenzie procedure solves the problem in finite time, but with many cuts.
- Smallest open case: three agents and 3 or 4 cuts.
Number of cuts for cake-cutting with different entitlements">proportional cake-cutting with different entitlements">cake-cutting with different entitlements
How many cuts are required for implementing a proportional cake-cutting among agents with different entitlements?
- Lower bound: ;
- Upper bound:.
- Smallest open case: agents with all different entitlements:, and.
- Lower bound:, since envy-free implies proportional.
- Upper bound: not known.
Fair division of a partly burnt cake
A proportional division of such a cake always exists.
Known cases:
- When all valuations are positive, or all valuations are negative, the Even-Paz protocol finds a connected proportional division using queries, and this is optimal.
- When valuations may be mixed, a moving-knife protocol can be used to find a connected proportional division using queries. Can this be improved to ?
[Truthful cake-cutting]
Truthful cake-cutting is the design of truthful mechanisms for fair cake-cutting. The currently known algorithms and impossibility results are shown here. The main cases in which it is unknown whether a deterministic truthful fair mechanism exists are:- There are 3 or more agents with piecewise-uniform valuations, without free disposal.
- There are 2 or more agents with piecewise-constant valuations, with or without free disposal.
Open problems in fair allocation of indivisible items">fair item allocation">fair allocation of indivisible items
Approximate [maximin-share] fairness
The 1-of- maximin share of an agent is the largest utility the agent can secure by partitioning the items into bundles and receiving the worst bundle. For two agents, divide and choose gives each agent at least his/her 1-of-2 MMS. For agents, it is almost always, but not always, possible to give each agent his/her 1-of- MMS. This raises several kinds of questions.1. Computational complexity
What is the runtime complexity of deciding whether a given instance admits a 1-of- MMS allocation?- Upper bound:
- Lower bound: none.
- Calculating the 1-of- MMS of a given agent is NP-hard even if all agents have additive preferences.
- Deciding whether a given allocation is 1-of- MMS is co-NP complete for agents with additive preferences.
2. Cardinal approximation
- For two agents: by divide-and-choose.
- For three agents, even with additive valuations:. By a carefully crafted example.
- For any number of agents with additive valuations:.
- For any number of agents with additive negative valuations : .
3. Ordinal approximation
- For two agents:. By divide-and-choose.
- For any number of agents with binary valuations:. By round-robin. It gives EF1, which implies 1-of--MMS.
- For agents:. By a carefully crafted example.
- For any number of agents with additive valuations:, by round-robin. It gives EF1, which implies 1-of--MMS.
- For any number of agents with additive valuations:, using envy-free matching.
Note: there always exists an Approximate Competitive Equilibrium from Equal Incomes that guarantees the ''1-of- maximin-share. However, this allocation may have excess supply, and - more importantly - excess demand: the sum of the bundles allocated to all agents might be slightly larger than the set of all items. Such an error is reasonable when allocating course seats among students, since a small excess supply can be corrected by adding a small number of seats. But the classic fair division problem assumes that items may not be added.
Envy-free up to one item
An allocation is called EF1 if, for any two agents and, and for any subset of size at most one contained in the bundle of, if we remove that subset from 's bundle then does not envy. An EF1 allocation always exists and can be found by the envy cycles algorithm. Combining it with other properties raises some open questions.Pareto-optimal EF1 allocation (goods and bads)
When all items are good and all valuations are additive, a PO+EF1 always exists: the allocation maximizing the product of utilities is PO+EF1. Finding this maximizing allocation is NP-hard, but in theory, it may be possible to find other PO+EF1 allocations.What is the run-time complexity of finding a PO+EF1 allocation of goods?
A PO+EF1 allocation of bads is not known to exist, even when all valuations are additive.
Does a PO+EF1 allocation of bads always exist?
What is the run-time complexity of finding such allocation, if it exists?
Contiguous EF1 allocation
Often the goods are ordered on a line, for example, houses in a street. Each agent wants to get a contiguous block.Known cases:
- For two agents with additive valuations, the answer is yes: we can round a connected envy-free cake-cutting.
- For agents with additive valuations, we can find an "EF minus 2" allocation by rounding a connected envy-free cake-cutting, and there also exists an EF2 allocation.
- For agents with additive binary valuations, an "EF minus 2" allocation is also EF1, so the answer is yes.
- A connected envy-free cake-cutting might take infinitely many queries to find. An EF1 allocation can always be found in finite time by checking all possible allocations, but this algorithm requires exponential run-time.
Price of fairness
What is the price of EF1 fairness?
- The upper bound is - by either Round-robin or maximum Nash welfare.
- The lower bound is .
Existence of EFx allocation
Known cases:
- If at least valuations are identical: yes.
- Hence, for two agents: yes. This is true even for general monotone valuations.
- For three agents: yes, by a recent working paper.
Existence of Pareto-efficient PROPx allocation of bads
Does there always exist an allocation of bads that is both PROPx and Pareto-efficient?
Related known cases:
- A PROPx allocation of goods may not exist.
- A PROPx allocation of bads always exists.
- A PROP1 and Pareto-efficient allocation of either goods or bads always exists.
Competitive equilibrium for almost all incomes
Known cases:
- With three or fewer goods: always yes.
- With four goods: yes for 2 agents with general valuations, no for 3 agents with general valuations, no for 4 agents, even with additive valuations.
- With five or more goods: no for two agents with general valuations.
- When there are two agents with additive valuations, CE for almost all incomes exists for any number of goods.
- When there are three agents, even with additive valuations, CE for almost all incomes might not exist.
Fair division of partly divisible items
Runtime complexity of fair allocation with bounded sharing
Given agents, items and an integer , suppose at most items can be shared among two or more agents. What is the runtime complexity of deciding whether a proportional / envy-free allocation exists?Known cases:
- With ' and identical valuations, for any , the problem is equivalent to the partition problem, and therefore it is NP-complete.
- With ', the answer is always "yes", and an allocation can be found in polynomial time.
- With ' and ' and identical valuations, an allocation can be found in polynomial time iff it exists.
- ' and ' and different valuations.
- ' and ' and identical valuations.