Hardness of deciding exact fairness in dividing indivisible items
On the Hardness of Maximin Share Allocations
Computer Science and Game TheoryData Structures and Algorithms
Summary
Deciding whether it is possible to fairly divide indivisible items so that each person gets a guaranteed minimum share is a difficult problem. The authors show that figuring out if an exact fair division exists is computationally very hard, even in simple cases. They prove new boundaries on how tough this problem is in different scenarios, settling long-standing open questions. Their results also show that fast perfect algorithms to approximate fairness don’t exist under common assumptions.
What this means in practice
- •For marketplace platform designers: Avoid attempts to quickly decide exact fair allocations when distributing indivisible goods, as this problem is computationally very hard in general.
- •For resource allocation system engineers: Recognize limits on approximating exact fairness guarantees efficiently when allocating resources with complex valuations, guiding realistic system designs.
A theory result. No direct application yet.
Authors
Sushmita Gupta, Sanjay Seetharaman
Abstract
The maximin share (MMS) guarantee is a central fairness benchmark for allocating indivisible items. Since Kurokawa, Procaccia and Wang [EC'14, JACM'18] showed that exact MMS allocations need not exist, much work has studied existence and computation of approximate MMS allocations. In contrast, a basic complexity question posed more than a decade ago by Bouveret and Lemaître [JAAMAS'16] has remained unresolved: how hard is it to decide whether an exact MMS allocation exists? For additive valuations, Lonc and Truszczynski [JAIR'20] showed membership in $Δ_2^P$ (also known as $P^{NP}$), but no hardness result was known. For the more general class of 2-additive valuations, Bouveret and Lemaître established NP-hardness, leaving a substantial gap to the $Δ_2^P$ upper bound. Moreover, the (precise) complexity of MMS existence in additive and $k$-additive settings was posed as an open question. We make progress on all of these fronts: (1) For additive goods, we prove that deciding MMS existence is $D^P$-hard, giving the first hardness result for this longstanding problem. (2) For 2-additive valuations, we close the complexity gap by proving $Δ_2^P$-completeness on a class of instances of monotone submodular goods. To the best of our knowledge this is the first result of this kind. We also prove weak coNP-hardness for three agents, thereby establishing a precise dichotomy with the known existence guarantee for two agents; and strong coNP-hardness when the number of agents is unrestricted. Moreover, the strong hardness construction produces an inverse-polynomial gap in the optimal MMS approximation ratio, ruling out an FPTAS for approximating this ratio unless P=NP. Finally, we show that all these results for goods extend to the chores setting through a polynomial-time transformation that preserves MMS existence.