All › Fair division › Runtime complexity of fair allocation with bounded sharing

More in “Runtime complexity of fair allocation with bounded sharing”

• 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.
• With k\geq n-1, the answer is always "yes", and an allocation can be found in polynomial time.
• With n=3 and k=1 and identical valuations, an allocation can be found in polynomial time if it exists.
• n=4 and k\in\{1,2\} and identical valuations.

Another random fair division problem →