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 n=3 and k=1 and identical valuations, an allocation can be found in polynomial time if it exists.
• n=3 and k=1 and different valuations.
• n=4 and k\in\{1,2\} and identical valuations.

Another random fair division problem →