The world's unsolved problems
993 open questions across 14 fields, gathered from Wikipedia. Pick one and start thinking.
Showing all 993 problems · surprise me
-
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 → -
For two agents with additive valuations, the answer is yes
we can round a connected envy-free cake-cutting (e.g., found by divide and choose).
Read on Wikipedia → -
For n agents with additive valuations, we can find an "EF minus 2" allocation by rounding a connected envy-free cake-cutting, and there…
For n 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 (proof using a variant of Sperner's lemma).
Read on Wikipedia → -
For n agents with additive binary valuations (every item value is either 0 or 1), an "EF minus 2" allocation is also EF1, so the answer is…
For n agents with additive binary valuations (every item value is either 0 or 1), an "EF minus 2" allocation is also EF1, so the answer is yes.
Read on Wikipedia → -
A connected envy-free cake-cutting might take infinitely many queries to find. An EF1 allocation can always be found in finite time by…
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.
Read on Wikipedia → -
The upper bound is O(n)
by either Round-robin or maximum Nash welfare.
Read on Wikipedia → -
The lower bound is O(\sqrt n).
Read on Wikipedia →
Data last refreshed 2026-10-20 03:01 UTC.