论文库

原文摘要

The maximin share (MMS) guarantee has become one of the central fairness benchmarks for allocating indivisible items. Since Kurokawa, Procaccia, and Wang [EC'14, JACM'18] showed that exact MMS allocations need not exist, a substantial literature has developed around the existence and computation of approximate MMS allocations, including the recent work of Heidari, Kaviani, Seddighin, and Shahrezaei [SODA'26]. In contrast, a fundamental 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] established membership in the complexity class $Δ_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 complexity of MMS existence for additive and $k$-additive valuations was posed as open questions. We resolve this longstanding question by proving that deciding the existence of an MMS allocation for additive goods is $Δ_2^P$-complete, even for five agents. Additionally, we 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. Furthermore, our strong hardness construction yields 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.