Approximating the utilitarian welfare minus a constant

Assume we have $$n$$ agents and $$m$$ indivisible goods that need to be allocated among the agents such that their sum of utilities is maximized.

Denote the set of allocations by $$\mathcal{A}$$ and the utility of agent $$i$$ by $$u_i \colon \mathcal{A} \to R_{\geq 0}$$, then the problem is to find an allocation $$A^{opt}$$ such that: $$\sum_{i=1}^n u_i(A^{opt}) = \max_{A \in \mathcal{A}}\sum_{i=1}^n u_i(A)$$

In many cases, e.g., when the utilities are monotone and submodular, finding such an allocation is NP-hard but there are known algorithms to find an allocation that approximates this value (in polynomial time). That is, it possible to find an allocation $$A'$$ such that $$\sum_{i=1}^n u_i(A') \geq (1-\epsilon) \max_{A \in \mathcal{A}}\sum_{i=1}^n u_i(A)$$ for some $$\epsilon \in (0,1)$$.

Are there any known special cases where the problem is NP-hard but it is possible to approximate the utilitarian welfare minus a constant? More precisely, given some constant $$c \in \mathbb{R}_{> 0}$$,

are there any cases where we can find an allocation $$A'$$ such that $$\sum_{i=1}^n u_i(A')-c \geq (1-\epsilon) (\max_{A \in \mathcal{A}}\sum_{i=1}^n u_i(A)-c)$$

• If you could do this then you would be able to decide whether the optimum utility is \ge c or not but this would not be possible for an NP-Hard problem unless P=NP. Sep 27, 2023 at 20:59
• @ChandraChekuri Thanks! I only know that the optimization problem is NP-hard, not sure if the decision problem is. Are the optimization and decision variants are always in the same hardness class? I couldn't find an answer Sep 28, 2023 at 19:39

Define $$u_i^\prime(A) = u_i(A) - \frac{c}{n}$$, where $$c \in \mathbb{R}_{>0}$$ and approximate $$u_i^\prime$$ instead?
• The problem is that these new utilities, $u'_i$, are no longer non-negative. All the algorithms I found assume that the utility functions always return a non-negative value, so they won't work on these new utilities. I tried to find a solution for the case where the set of items is a mixture of goods and bads (and so utilities can be negative) but I didn't find any algorithm to approximate the sum of utilities in this case. Aug 28, 2023 at 22:37