Item

Abstract

We consider the problem of maximizing the Nash social welfare when allocating
a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We
study instances, in which all agents have 2-value additive valuations: The
value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is
$v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly,
we design an algorithm to compute an optimal allocation in polynomial time if
$p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ after appropriate
scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p
\ge 3$.
In terms of approximation, we present positive and negative results for
general $p$ and $q$. We show that our algorithm obtains an approximation ratio
of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with
a lower bound of $1.000015$ achieved at $p/q = 4/5$.