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

arXiv: https://arxiv.org/abs/2610.05237 · HTML: https://mlsanity.com/paper/2610.05237/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 4 Oct 2026.

## Builds on (most cited first, 15 of 15)

- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [Maximum Nash Welfare and Other Stories About EFX](https://mlsanity.com/paper/2001.09838/) (2020)
- [Fair and Truthful Mechanisms for Dichotomous Valuations](https://mlsanity.com/paper/2002.10704/) (2020)
- [Fair Division with Binary Valuations: One Rule to Rule Them All](https://mlsanity.com/paper/2007.06073/) (2020)
- [Greedy Algorithms for Maximizing Nash Social Welfare](https://mlsanity.com/paper/1801.09046/) (2018)
- [Maximizing Nash Social Welfare in 2-Value Instances](https://mlsanity.com/paper/2107.08965/) (2021)
- [The Good, the Bad and the Submodular: Fairly Allocating Mixed Manna Under Order-Neutral Submodular Preferences](https://mlsanity.com/paper/2307.12516/) (2023)
- [On the Hardness of Fair Allocation under Ternary Valuations](https://mlsanity.com/paper/2403.00943/) (2024)
- [Combinatorial Algorithm for Restricted Max-Min Fair Allocation](https://mlsanity.com/paper/1409.0607/) (2014)
- [A Tale of Santa Claus, Hypergraphs and Matroids](https://mlsanity.com/paper/1807.07189/) (2018)
- [Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations](https://mlsanity.com/paper/1912.00459/) (2019)
- [On Pareto-Optimal and Fair Allocations with Personalized Bi-Valued Utilities](https://mlsanity.com/paper/2507.18251/) (2025)
- [On (1,ε)-Restricted Assignment Makespan Minimization](https://mlsanity.com/paper/1410.7506/) (2014)
- [Restricted Max-Min Fair Allocation](https://mlsanity.com/paper/1804.10902/) (2018)
- [Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability](https://mlsanity.com/paper/2207.10949/) (2022)

## Abstract (arXiv)

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.