CS Paper Radar

The Existence of Maximin Share Allocations is $Δ_2^P$-complete

Sushmita Gupta, Sanjay Seetharaman

cs.GT cs.DS ·submitted 2026-09-14 16:38 UTC · v3
theory

Abstract

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.

Comment
58 pages; this version strengthens the main result for additive valuations; abstract shortened to meet arXiv requirements

Closest papers

Nearest neighbours by meaning across the whole index.

Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

cs.GT cs.AI ·2026-10-04 ·Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
theory similarity 0.71
Abstract

We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong to a small set. For additive valuations with values in $\{p,q\}$, where $q>p>0$ and $\gcd(p,q)=1$, we give a polynomial-time algorithm when $p=2$ and prove constant-gap hardness when $p\geq3$, already with exactly three high-valued goods per agent. We also give an $\sqrt{3/2}$-approximation for common positive bi-valued additive valuations. For mixed additive valuations in $\{-p,0,c\}$, where $p\in\{1,2\}$ and $c$ is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of $\{-2,0,c\}$-valuations. For submodular valuations with marginals in $\{-2,0,c\}$, where $c$ is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for $\{-1,0,1\}$-submodular valuations, we prove that no finite multiplicative approximation exists unless $\p=\np$. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations.

0.04

Fair and Efficient Allocations: Decision Problems in the Gap of Polynomial Hierarchy

cs.GT ·2026-09-25 ·Xiaolin Bu, Biaoshuai Tao
published similarity 0.70
Abstract · Accepted by WINE'26

We consider the fair division problem with indivisible goods and study the following decision problem: given a fair division instance, does there exist an allocation that is envy-free and efficient? We consider two efficiency criteria: Pareto-optimality and social welfare optimality. We provide a complete landscape on the computational complexity of this decision problem, with the number of agents ranging from $2$ to $\infty$, both additive valuations and general valuations, and the more restricted class of $k$-ary valuation functions (where an item's marginal value is restricted to $\{0,1,\ldots,k-1\}$ for some constant $k\geq2$). One interesting observation is that many versions of the above-mentioned decision problems fall into the ``gap'' between the first and the second levels of the polynomial hierarchy. Specifically, assuming the polynomial hierarchy does not collapse to the first level (i.e., assuming $\text{NP}\neq\text{coNP}$), these problems are in $(Σ_2^{\text{p}}\capΠ_2^{\text{p}})\setminus(\text{NP}\cup\text{coNP})$. In particular, we provide a fine-grained complexity analysis across different parameter regimes, including the number of agents and the choice of valuation models. Depending on different parameters, many problems admit different complexity classifications, ranging from the intermediate classes $Θ_2^{\text{p}}$ and $Δ_2^{\text{p}}$ between the two levels to $Σ_2^{\text{p}}$-completeness. Finally, De Keijzer et al. show the $Σ_2^{\text{p}}$-completeness of the decision problem when considering Pareto-optimality as the efficiency criterion with additive valuations. Our main results extend this result to more restricted settings, such as instances with a constant number of agents or $3$-ary valuation functions, which resolves the open problem given by Bouveret and Lang.

0.16

Non-Existence of PMMS Allocations and a $4/3$-PMMS Guarantee for Additive Chores

cs.GT ·2026-09-09 ·Xiaohui Bei, Zehan Lin, Shengxin Liu, Rong Luan, Biaoshuai Tao
theory similarity 0.69
Abstract · 23 pages, no figure

We study pairwise maximin share (PMMS) fairness for indivisible items with additive preferences. We give a polynomial-time reduction from chores to goods that preserves the existence of a PMMS allocation. Together with known nonexistence results for chores, this yields nonexistence for additive goods. In addition, we show that deciding if a given instance admits a PMMS allocation is NP-hard. We also give explicit instances whose PMMS factors are $226/227$ for goods and $1.102065$ for chores, certified by exact enumeration. Complementing these impossibility results, we prove that every additive-chore instance admits a $4/3$-PMMS allocation.

0.38

Subjective Valuations Make It Hard to be Fair: The Complexity of Resource Allocation to Groups of Agents

cs.GT cs.CCcs.DS ·2026-10-20 ·Argyrios Deligkas, Eduard Eiben, Robert Ganian, Tiger-Lily Goldsmith, Marlene Gründel +1 more
similarity 0.67
Abstract

We study the parameterized complexity of finding an EF1 allocation of indivisible items in the group-sharing setting, which has received increasing attention in recent years. There, items are not allocated to individual agents but rather to one of two (or possibly more) groups, and agents within that group all share the assigned items. We consider both the "fixed" (EF1-Fix) and "variable" (EF1-Var) group cases, where in the former the assignments of agents to groups are prescribed. While both are NP-hard in the classical sense, we show that their algorithmic behavior differs significantly from the parameterized perspective. As our main results, we: (1) prove that both cases are NP-hard even when the number of agents is a small constant; (2) circumvent this hardness by establishing fixed-parameter tractability for EF1-Var w.r.t. the number of "subjective" items, that is, items which are viewed as chores or goods by different agents---but rule out an analogous result for EF1-Fix; and (3) establish fixed-parameter tractability for EF1-Fix w.r.t. the number of item types, but link the existence of an analogous fixed-parameter algorithm for EF1-Var to a fundamental open question in the setting of Integer Linear Programming.

0.19

Maximin Share Allocations Beyond Weakly Lexicographic Valuations

cs.GT ·2026-09-12 ·Nicholas Teh
theory similarity 0.67
Abstract

We study the fair division of indivisible goods among agents with nonnegative additive valuations. An agent's maximin share (MMS) is the value she can guarantee by partitioning the goods into as many bundles as there are agents and receiving a least-valued bundle. We prove the existence of exact MMS allocations for a valuation domain that generalizes several few-valued domains as well as weakly lexicographic valuations. For each agent, the lower-valued goods, after a positive rescaling, may take values in $\{0,1,d,d+1\}$, $\{0,1,2,2e\}$, or $\{0,1,2,3,4\}$, where $d,e\ge 2$ are integers. Above these goods, the valuation may contain arbitrarily many value classes, subject to the condition that a single good in each class is worth at least the total value of all strictly lower-valued goods. The value classes, scaling factors, and parameters may vary across agents. We give an algorithm that computes an MMS allocation in $O(nm\log^2(2+m))$ time, where $n$ is the number of agents and $m$ is the number of goods.

0.34

To EFX OR to MMS, That is the Question

cs.GT ·2026-08-11 ·Hadi Hosseini, Payas Khurana, Shraddha Pathak, Rohit Vaish
theory similarity 0.66
Abstract

We study the agent-wise disjunction of two central fairness notions for indivisible items, where every agent must be either envy-free up to any item (EFX) or maximin-share (MMS) satisfied. One might expect that having a flexible fairness requirement for individual agents will restore existence, especially because the existence of EFX itself resisted resolution for nearly a decade. Surprisingly, it does not. We construct counterexamples with three agents and eight submodular goods, and with three agents and seven submodular chores, significantly strengthening recent EFX impossibility results. On the positive side, we prove existence for additive mixed items with at most three valuation types when one type is a singleton. Additionally, we obtain polynomial-time approximation schemes for additive goods-only and chores-only instances. We also identify a clean separation between the disjunction and its constituents: For additive chores with two valuation types, EFX and MMS are both known to fail, whereas an EFX $\vee$ MMS allocation always exists. Finally, we show that identical additive valuations even admit the conjunction EFX $\wedge$ MMS for mixed items. Overall, our results show that allowing flexibility in choosing agent-specific fairness certificates expands the frontier of fair solutions while also uncovering surprising impossibilities.

0.32

Exact MMS Allocations under Personalized Bivalued Valuations: Goods and Chores

cs.GT cs.DS ·2026-08-16 ·Yuhao Zhang
benchmarktheory similarity 0.66
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible goods and chores. We study additive valuations in the personalized bivalued setting, where each agent assigns one of two agent-specific values to every item. Whether exact MMS allocations always exist in this setting has remained a major open question, as highlighted by Ebadian, Peters, and Shah and by Garg, Huang, and Segal-Halevi. We answer this question affirmatively: we prove that exact MMS allocations always exist for both goods and chores and can be computed in polynomial time. Our proof combines a quota-based reformulation with an envelope relaxation, a sparse extreme-point construction, and flow-based rounding that controls the total rounding loss.

0.40

On best of both worlds allocations with subadditive valuations

cs.GT ·2026-09-27 ·Uriel Feige
theory similarity 0.65
Abstract

We consider allocation of indivisible goods to agents with equal entitlements and subadditive valuations. As an ex-post fairness notion we consider the maximin share (MMS), and as an ex-ante fairness notion we consider the maximum expectation share (MES), which is always at least as large as the MMS, and sometimes much larger. We present a simple transformation that for every $0 < ρ\le 1$, given any algorithm that produces $ρ$-MMS allocations, transforms it into a randomized allocation algorithm that offers $ρ$-MMS ex-post simultaneously with $η$-MES ex-ante. We prove several new properties of MES, and use them to show that $η\ge \min[\fracρ{2 + ρ}, \frac{1}{4}]$. We also present cases in which the transformation results in a higher value of $η$. Applying our transformation to currently known allocation algorithms shows for subadditive valuations the existence of randomized allocations that are simultaneously $Ω(\frac{1}{\log\log n})$-MES ex-ante and $Ω(\frac{1}{\log\log n})$-MMS ex-post, and for XOS valuations the existence of randomized allocations that are simultaneously $\frac{4}{27}$-MES ex-ante and $\frac{4}{17}$-MMS ex-post.

0.26