1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Sep 27 at 20:59
  • $\begingroup$ @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 $\endgroup$
    – eden hartman
    Sep 28 at 19:39

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – eden hartman
    Aug 28 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.