The world's unsolved problems
993 open questions across 14 fields, gathered from Wikipedia. Pick one and start thinking.
49 results in Fair division · clear · surprise me
-
Lower bound
\Omega(n^2)
Read on Wikipedia → -
Upper bound
O\left(n^{n^{n^{n^{n^{n}}}}}\right).
Read on Wikipedia → -
For n=3, there is an algorithm with 54 queries.
Read on Wikipedia → -
For n\geq 4, no finite algorithm is currently known.
Read on Wikipedia → -
For n=3, there is an algorithm that attains 1/3, which is optimal.
Read on Wikipedia → -
For n=4 (the smallest open case), there is an algorithm that attains 1/7.
Read on Wikipedia → -
For any n, there is an algorithm that attains 1/(3n).
Read on Wikipedia → -
For n\geq 3, a finite algorithm does not exist for n-1 cuts (1 piece per agent).
Read on Wikipedia → -
For n=3, Selfridge–Conway procedure solves the problem in finite time with 5 cuts (and at most 2 pieces per agent).
Read on Wikipedia → -
For n\geq 4, the Aziz-Mackenzie procedure solves the problem in finite time, but with many cuts (and many pieces per agent).
Read on Wikipedia → -
Smallest open case
three agents and 3 or 4 cuts; four agents and 2 pieces per agent.
Read on Wikipedia → -
Lower bound
2n-2
Read on Wikipedia → -
Upper bound
3n-4.
Read on Wikipedia → -
Smallest open case
n=3 agents with all different entitlements: 1/7, 2/7 and 4/7.
Read on Wikipedia → -
When all valuations are positive, or all valuations are negative, the Even-Paz protocol finds a connected proportional division using…
When all valuations are positive, or all valuations are negative, the Even-Paz protocol finds a connected proportional division using O(n\log n) queries, and this is optimal.
Read on Wikipedia → -
When valuations may be mixed, a moving-knife protocol can be used to find a connected proportional division using O(n^2) queries. Can this…
When valuations may be mixed, a moving-knife protocol can be used to find a connected proportional division using O(n^2) queries. Can this be improved to O(n\log n) ?
Read on Wikipedia → -
There are 3 or more agents with piecewise-uniform valuations, without free disposal.
Read on Wikipedia → -
There are 2 or more agents with piecewise-constant valuations, with or without free disposal (and without additional requirements such as…
There are 2 or more agents with piecewise-constant valuations, with or without free disposal (and without additional requirements such as connectivity or non-wastefulness).
Read on Wikipedia → -
Upper bound
{NP}^{NP} (which is \Sigma_2^P - level 2 in the polynomial hierarchy)
Read on Wikipedia → -
Lower bound
none (so it may be level 2 or 1 or even 0 of the hierarchy).
Read on Wikipedia → -
Calculating the 1-of-n MMS of a given agent is NP-hard even if all agents have additive preferences (reduction from partition problem).
Read on Wikipedia → -
Deciding whether a given allocation is 1-of-n MMS is co-NP complete for agents with additive preferences.
Read on Wikipedia → -
For two agents
r=1 by divide-and-choose.
Read on Wikipedia → -
For three agents, even with additive valuations
r<1. By a carefully crafted example.
Read on Wikipedia → -
For any number of agents with additive valuations
r\ge 3/4.
Read on Wikipedia → -
For any number of agents with additive negative valuations (i.e., for chores)
r\ge 9/11.
Read on Wikipedia → -
For two agents
N=2. By divide-and-choose.
Read on Wikipedia → -
For any number of agents with binary valuations
N=n. By round-robin. It gives EF1, which implies 1-of-n-MMS.
Read on Wikipedia → -
For n>2 agents
N>n. By a carefully crafted example.
Read on Wikipedia → -
For any number of agents with additive valuations
N\le 2n-1, by round-robin. It gives EF1, which implies 1-of-(2n-1)-MMS.
Read on Wikipedia →
Data last refreshed 2026-10-20 03:01 UTC.