This page lists notable open problems related to fair division - a field in the intersection of mathematics, computer science, political science and economics.
In the problem of envy-free cake-cutting, there is a cake modeled as an interval, and
agents, an envy-free division can be found using two queries, via divide and choose.
agents, there are several open problems regarding the number of required queries.
First, assume that the entire cake must be allocated (i.e., there is no disposal), and pieces may be disconnected.
Next, assume that some cake may be left unallocated (i.e., there is free disposal), but the allocation must be proportional (in addition to envy-free): each agent must get at least
Next, assume there is free disposal, the allocation must still be proportional, but the pieces must be connected.
Next, assume there is free disposal, the pieces must be connected, but the allocation may be only approximately proportional (i.e., some agents may get less than
What value can be guaranteed to each agent using a finite envy-free protocol?
Finally, assume the entire cake must be allocated, and pieces may be disconnected, but the number of cuts (or number of pieces per agent) should be as small as possible.
How many cuts do we need in order to find an envy-free allocation in a finite number of queries?
When all agents have equal entitlements, a proportional cake-cutting can be implemented using
How many cuts are required for implementing an envy-free cake-cutting among
Known cases: An envy-free division of a partly burnt cake is guaranteed to exist if-and-only-if the number of agents is the power of a prime integer.
Given a small positive number D, an allocation is called D-envy-free if, for each agent, the allocation will become envy-free if we move the cuts by at most D (length units).
The main cases in which it is unknown whether a deterministic truthful fair mechanism exists are:[10] The 1-of-
What is the runtime complexity of deciding whether a given instance admits a 1-of-
Smallest open case: Note: there always exists an Approximate Competitive Equilibrium from Equal Incomes that guarantees the 1-of-(
[17] 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.
An EF1 allocation always exists and can be found by the envy cycles algorithm.
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.
A PO+EF1 allocation of bads (chores) is not known to exist, even when all valuations are additive.
[20] Known cases: Even when a contiguous EF1 allocation exists, the runtime complexity of finding it is unclear: The price of fairness is the ratio between the maximum social welfare (sum of utilities) in any allocation, and the maximum social welfare in a fair allocation.
An allocation is called EFx ("envy-free up to any good") if, for any two agents
[23] Known cases: An allocation of bads is called PROPx (aka FSx)[26]: Sec.7 if, for any agent
Related known cases: Competitive equilibrium (CE) is a very strong fairness notion - it implies Pareto-optimality and envy-freeness.
When the incomes are equal, CE might not exist even when there are two agents and one good.
What is the runtime complexity of deciding whether a proportional / envy-free allocation exists?