<p>Define <span class="math-container">$u_i^\prime(A) = u_i(A) - \frac{c}{n}$</span>, where <span class="math-container">$c \in \mathbb{R}_{&gt;0}$</span> and approximate <span class="math-container">$u_i^\prime$</span> instead?</p>

CC BY-SA 4.0
2023-08-28T22:37:36.603Z
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.
eden hartman
CC BY-SA 4.0
2023-08-28T19:00:07.127Z
2023-08-28T19:00:07.127Z
ndrwnaguib
<p>Assume we have <span class="math-container">$n$</span> agents and <span class="math-container">$m$</span> indivisible goods that need to be allocated among the agents such that their sum of utilities is maximized.</p>
<p>Denote the set of allocations by <span class="math-container">$\mathcal{A}$</span> and the utility of agent <span class="math-container">$i$</span> by <span class="math-container">$u_i \colon \mathcal{A} \to R_{\geq 0}$</span>, then the problem is to find an allocation <span class="math-container">$A^{opt}$</span> such that:
<span class="math-container">$$
\sum_{i=1}^n u_i(A^{opt}) = \max_{A \in \mathcal{A}}\sum_{i=1}^n u_i(A) 
$$</span></p>
<p>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 <span class="math-container">$A'$</span> such that
<span class="math-container">$$
\sum_{i=1}^n u_i(A') \geq (1-\epsilon) \max_{A \in \mathcal{A}}\sum_{i=1}^n u_i(A)
$$</span>
for some <span class="math-container">$\epsilon \in (0,1)$</span>.</p>
<p>Are there any known special cases where the problem is NP-hard but it is possible to approximate the utilitarian welfare <em>minus a constant</em>?
More precisely, given some constant <span class="math-container">$c \in \mathbb{R}_{&gt; 0}$</span>,</p>
<p>are there any cases where we can find an allocation <span class="math-container">$A'$</span> such that
<span class="math-container">$$
\sum_{i=1}^n u_i(A')-c \geq (1-\epsilon) (\max_{A \in \mathcal{A}}\sum_{i=1}^n u_i(A)-c)
$$</span></p>

CC BY-SA 4.0
2023-09-27T20:59:13.953Z
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.
Chandra Chekuri
CC BY-SA 4.0
2023-09-28T19:39:33.953Z
@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
eden hartman
<approximation-algorithms><optimization><gt.game-theory><combinatorial-game-theory><mechanism-design>
Approximating the utilitarian welfare minus a constant
eden hartman
# Approximating the utilitarian welfare minus a constant

(Asked by: username_0 on 2023-08-28)

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)
$$

**Tags:** approximation-algorithms, optimization, gt.game-theory, combinatorial-game-theory, mechanism-design

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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  

---

## 1 answers

### Answer by username_2 on 2023-08-28. Score: 0

Define $u\_i^\prime(A) = u\_i(A) - \frac{c}{n}$, where $c \in \mathbb{R}\_{>0}$ and approximate $u\_i^\prime$ instead?

> **Comments:**
> **username_0**: 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.  

---

