Complexity and approximation of welfare maximizations with few agent and item types
Maximizing $p$-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types
Computer Science and Game TheoryArtificial Intelligence
Summary
This paper looks at how hard it is to fairly divide items among people when both items and people come in a few different types, and you want to maximize a specific fairness measure called p-mean welfare. The authors show that finding the best distribution is usually very hard (NP-hard) for many cases, even if there are only two or three types of items or agents. They also provide efficient algorithms that can find nearly the best distribution when either the number of item types or the number of agent types is fixed.
What this means in practice
- •For resource allocation system designers: Understand computational limits of fair division algorithms with few item types and few agent types when handling large counts.
- •For marketplace platform engineers: Use approximation schemes for distributing digital goods among user groups when categories of goods or users are limited.
A theory result. No direct application yet.
Authors
Trung Thanh Nguyen, Khaled Elbassioni
Abstract
The $p$-mean welfare objective unifies several classical social welfare criteria for the allocation of indivisible goods. We study its maximization under additive nonnegative utilities when item and agent multiplicities are encoded in binary. For every fixed finite rational $p<1$, $p\neq0$, we show that the problem is $\mathsf{NP}$-hard with only two item types. Nash welfare ($p=0$) and egalitarian welfare ($p=-\infty$) are NP-hard with three item types. These results hold both for computing an optimal allocation and for rational-threshold decision, and the utilities and threshold can be required to be positive integers. We also show that maximizing $p$-mean social welfare is strongly NP-hard with one agent type and an unrestricted number of item types, for every fixed finite rational $p<1$ and for $p=-\infty$. A quantitative gap in this reduction rules out an FPTAS in the latter setting unless $\mathsf{P}=\mathsf{NP}$. On the positive side, for a fixed number of item types and an arbitrary number of agent types, we give an FPTAS for every fixed $p\in\mathbb Q\cup\{-\infty\}$. Its running time is polynomial in the compact input length and in $1/\varepsilon$, and it returns a compressed allocation. For a fixed number of agent types and an unrestricted number of item types, we give a PTAS for every fixed finite rational $p<1$, also in the fully compact model. We further give explicit compact-model proofs of the classical exact allocation algorithms for one item type, and for egalitarian welfare with two item types. These results essentially settle the complexity and approximability of $p$-mean welfare maximization with few item types and/or few agent types, leaving only the exact complexity of Nash welfare maximization with two item types unresolved in the small-item-type classification.