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
-
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 → -
A PROPx allocation of goods (even without Pareto-efficiency) may not exist.
Read on Wikipedia → -
A PROPx allocation of bads (without Pareto-efficiency) always exists.
Read on Wikipedia → -
A PROP1 and Pareto-efficient allocation of either goods or bads always exists.
Read on Wikipedia → -
With three or fewer goods
always yes.
Read on Wikipedia → -
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.
Read on Wikipedia → -
With five or more goods
no for two agents with general valuations.
Read on Wikipedia → -
When there are two agents with additive valuations, CE for almost all incomes exists for any number of goods.
Read on Wikipedia → -
When there are three agents, even with additive valuations, CE for almost all incomes might not exist.
Read on Wikipedia → -
With k=0 and identical valuations, for any n\geq 2, the problem is equivalent to the partition problem, and therefore it is NP-complete.
Read on Wikipedia → -
With k\geq n-1, the answer is always "yes", and an allocation can be found in polynomial time.
Read on Wikipedia → -
With n=3 and k=1 and identical valuations, an allocation can be found in polynomial time if it exists.
Read on Wikipedia → -
n=3 and k=1 and different valuations.
Read on Wikipedia → -
n=4 and k\in\{1,2\} and identical valuations.
Read on Wikipedia →
Data last refreshed 2026-10-20 03:01 UTC.