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

Jun 19, 2026cs.GT

Simultaneously Efficient Allocation of Indivisible Items Across Multiple Dimensions

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.

Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui

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

Welfare Pareto Frontier Efficiency Value

Ask PDF

Jul 25, 2026cs.GT

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

We study whether strictly positive marginal values restore the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) for indivisible goods. For two agents, we identify the exact threshold in the number of goods. Every instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO, without any submodularity assumption. In contrast, we construct an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations in which every EF1 allocation is strictly Pareto dominated. Thus, eight goods are necessary and sufficient for a two-agent counterexample. Finally, we strengthen the three-agent NP-hardness result of Chandramouleeswaran and Nimbhorkar (2026): deciding whether an EF1 and PO allocation exists remains NP-hard for normalized, integer-valued, monotone submodular valuations even when zero marginals are confined to eight fixed agent-good pairs, all involving a single agent.

Nicholas Teh

University of Oxford, UK

Welfare Submodular Functions Pareto Frontier Algorithmic Fairness Value Decision Thresholds+1

Ask PDF

Sep 3, 2026cs.GT

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

We study the allocation of indivisible goods among agents with identical additive valuations, focusing on envy-freeness up to one good (EF1) and Nash social welfare (NSW). Since every maximum-NSW allocation is EF1 under additive valuations, the associated threshold problem inherits the known strong NP-hardness of NSW maximization under identical additive valuations and is strongly NP-complete. We therefore focus on welfare guarantees satisfied by arbitrary EF1 allocations. Although every such allocation is known to achieve an

e^{-1/e}

-approximation to the unrestricted optimal NSW, we identify conditions yielding stronger guarantees. Under uniform valuations, every EF1 allocation is NSW-optimal. Under an

\varepsilon

-small-item condition, every EF1 allocation achieves an explicit approximation ratio

ρ_n(\varepsilon)

satisfying

ρ_n(\varepsilon) = 1-O(\varepsilon^2)

\varepsilon\to 0

for fixed

n

. We further consider the stronger sequential requirement that

\operatorname{EF1}

be maintained after every item assignment. For this setting, we introduce \emph{PriorityNet}, a deep reinforcement learning framework trained with Proximal Policy Optimization (PPO) and equipped with prospective

\operatorname{EF1}

action masking, which guarantees prefix-wise

\operatorname{EF1}

by construction. Across 3,000 test instances in each of the offline full-information and random-order online regimes (

n\in[2,20]

m\in[5,100]

), PriorityNet achieves mean normalized

\operatorname{NSW}

values of

0.9911

and

0.9701

, respectively. Relative to the offline Longest Processing Time (LPT) heuristic and the online least-valued-bundle rule, it attains instance-wise win-minus-loss rates of

+27.10\%

and

+17.87\%

. Its aggregate welfare matches the offline LPT baseline to four decimal places and modestly improves upon the online baseline, from

0.9694

0.9701

Zih-Sian Yang, Yi-Hao Chen, Yu-Te Kuan +3

National Taiwan Ocean University, Keelung City 202301, Taiwan · National Yang Ming Chiao Tung University, Hsinchu City 300, Taiwan

Welfare Nash Equilibrium Proximal Policy Optimization

Ask PDF