marketplace platform designers

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.

Abstract: We study envy-freeness with subsidies for indivisible items beyond additive valuations. Assuming that every single-item marginal value lies in $[-1,1]$, we prove that a total subsidy of $O(n^{3/2}\sqrt{\log n})$ suffices to achieve envy-freeness among $n$ agents whenever all agents assign nonnegative values to every bundle or all assign nonpositive values to every bundle. These valuation classes include monotone goods and monotone chores, respectively, but do not require monotonicity. Our result establishes the first subquadratic total-subsidy bound for general monotone valuations that holds for every number of agents.