Computational limits of fair item allocation with three value levels
Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations
Computer Science and Game TheoryArtificial Intelligence
Summary
This paper looks at how to fairly divide a set of indivisible items among people when each item can have only a few different value levels for each person. The authors find which cases can be solved quickly by a computer and which are much harder, even impossible to approximate well. They explore different types of value settings, including positive-only values, mixed positive and negative values, and more complex valuation types. Their results settle long-standing questions about how hard it is to find the fairest allocation under these conditions.
What this means in practice
- •For resource allocation system designers: Identify which max-min fair allocation problems with simple item values can be solved efficiently and which cannot, guiding system design choices.
- •For combinatorial auction engineers: Understand computational hardness boundaries for auctions where bidders have limited complexity valuations with three possible marginal values.
A theory result. No direct application yet.
Authors
Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
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.