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

Thi Ngoc Anh Vu; Trung Thanh Nguyen; Khaled Elbassioni; Jörg Rothe

cs.GTOct 4, 2026

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

Authors: Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe

Organizations: Faculty of Computer Science, Phenikaa University, Hanoi 12116, Vietnam · DataOptLab, National Economics University, Hanoi 11616, Vietnam · Khalifa University of Science and Technology, Abu Dhabi 127788, UAE · Institut für Informatik, MNF, Heinrich-Heine-Universität Düsseldorf, 40225, Düsseldorf, Germany

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.

Figures & tables

Valuations	Additive	Submodular
$\{0,c\}$ , $c\geq 1$	P ( Golovin, 2005 )	P ( Babaioff et al., 2021 ; Viswanathan and Zick, 2023 )
$\{1,c\}$ , $c\geq 1$	P ( Cousins et al., 2023a )	P ( Cousins et al., 2023a )
$\{2,c\}$ , odd $c\geq 3$	P (Thm. 1 )	Open
$\{p,q\}$ , $0<p<q$	$\sqrt{\frac{3}{2}}$ -appr. (Thm. 3 )	No PTAS (Thm. 2 )
$\{0,1,c\}$ , $c\geq 2$	No $(2+\epsilon)$ -appr. Chan et al. (2016)	No $(2+\epsilon)$ -appr.
$\{p,q,r\}$ ,	$\mathrm{NP}$ -hard Cousins et al. (2023b)	$\mathrm{NP}$ -hard

Table 1: Complexity of

\mathsf{MEW}

with ternary valuations. Our new results are highlighted in bold.

Panel of Figure 1 — Figure 1: The decomposition $\mathcal{S}$ for $q=5$ ( $s=2$ ) and $T=17$ , so $K=4$ . Since $T$ is odd, $\mu_{1}=s$ becomes the lead single slot; the block $(\mu_{2},\mu_{3})=(s-1,s)$ becomes a pair slot; and the truncated last term $\mu_{4}=0$ becomes a tail single slot.

Panel of Figure 2 — Figure 2: The graph $G$ for $q=5$ , $T=17$ (decomposition of Figure 1 ) on an instance with $n=2$ agents and $m=4$ goods, where $H_{1}=\{g_{1},g_{2},g_{3}\}$ and $H_{2}=\{g_{2},g_{3},g_{4}\}$ . Each agent receives its own copy of the slot vertices: a lead vertex $\ell_{i}$ , pair vertices $u_{i},u_{i}^{\prime}$ joined by an internal edge of weight $1$ , and a tail vertex $t_{i}$ ; these are joined only to the goods in $H_{i}$ , with weights $s=2$ , $s=2$ and $0$ , respectively. The good vertices are shared, so a matching assigns each good to at most one agent; $g_{2}$ and $g_{3}$ are wanted by both agents. Relative to the baseline $1$ of the internal edge, a pair slot contributes $0$ , $s-1=1$ or $2s-1=3$ with $0$ , $1$ or $2$ goods.

Panel of Figure 3 — Figure 3: The graph $\mathcal{H}$ of Example 2 . Good–port edges have weight $3$ , dashed edges have weight $-1$ , and all other edges have weight $0$ . Small dashed boxes mark the extra absorbers $a_{1,0},a_{2,0}$ . Thick edges form the maximum-weight perfect matching of weight $8$ .

Panel of Figure 4 — Figure 4: The instance of Example 3 for the path $\mathcal{G}$ with edges $\{1,2\}$ and $\{2,3\}$ and $s=2$ . Each pair item $e_{u},e_{u}^{\prime}$ can be counted either by pair agent $u$ (value $c$ ) or by the collector (through the hidden sparse paving matroid, in which $P_{1}\cup P_{3}$ is dependent). Thick edges show the allocation for the clique $\{1,2\}$ : the collector receives $P_{1}\cup P_{2}$ and its dummies $D_{0}$ , pair agents $1$ and $2$ keep only their dummies, and pair agent $3$ keeps $P_{3}$ , its dummies, and all $H=3$ chores. Every agent has value $t=18$ .

Panel of Figure 5 — Figure 5: The instance of Example 4 for $\varphi=(x_{1}\vee\neg x_{2})\wedge(\neg x_{1}\vee x_{2})$ . Each dashed box is the cycle of a variable: vertical edges (every agent takes its left good) encode true , diagonal edges encode false . Solid thin edges join agents to goods they value at $1$ , dashed edges join agents to clause items they value at $0$ , and “vs. $g$ ” names the good forming a conflict pair with the agent’s clause item. Thick edges show the allocation for $x_{1}=x_{2}=\mathrm{true}$ , in which every agent has value $1$ .

Explore similar work

Simultaneously Efficient Allocation of Indivisible Items Across Multiple Dimensions
Jun 19, 2026Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin SanpuiWelfare Pareto Frontier
Chuo University, Tokyo, Japan · Indian Institute of Technology Kharagpur, Kharagpur, India
Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO
Jul 25, 2026Nicholas TehWelfare Submodular Functions
University of Oxford, UK
EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments
Sep 3, 2026Zih-Sian Yang, Yi-Hao Chen, Yu-Te Kuan +3Welfare Nash Equilibrium
National Taiwan Ocean University, Keelung City 202301, Taiwan · National Yang Ming Chiao Tung University, Hsinchu City 300, Taiwan

Jun 19, 2026, cs.GTJ/K move · Enter open · S save

Simultaneously Efficient Allocation of Indivisible Items Across Multiple Dimensions

Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui

Chuo University, Tokyo, Japan · Indian Institute of Technology Kharagpur, Kharagpur, India

Welfare Pareto Frontier Efficiency Value

Open paper AskPDF arXiv

Many allocation problems are intrinsically multidimensional, since an item may contribute differently to several criteria, and optimizing a single aggregate objective can hide severe losses in other dimensions. We study how much efficiency can be guaranteed simultaneously when indivisible items have multiple attributes. To this end, we introduce the \emph{multidimensional efficient allocation} (MDEA) model, where each agent has an additive valuation in each dimension, and investigate simultaneous efficiency under utilitarian social welfare (USW) and egalitarian social welfare (ESW). Our results reveal a sharp worst-case frontier. For exact efficiency, maximizing the number of dimensions attaining the USW optimum admits a

c/\ell

-approximation for every fixed constant

c

, and this dependence on the number

\ell

of dimensions is essentially unavoidable; for ESW, even deciding whether two dimensions can be optimized simultaneously is NP-hard with binary valuations. For approximate simultaneous efficiency in every dimension, we identify a tight threshold of order

1/\ell

, showing that such guarantees always exist for both USW and ESW, while any asymptotically better dependence on

\ell

is impossible, even for binary valuations. Finally, we introduce three natural multidimensional Pareto notions and characterize both their relationships and their computational complexity.

Abstract

Explore similar work

Simultaneously Efficient Allocation of Indivisible Items Across Multiple Dimensions

Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO

EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments