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

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≥3, already with exactly three high-valued goods per agent. We also give an √3/2-approximation for common positive bi-valued additive valuations. For mixed additive valuations in -p,0,c, where p∈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.