Approximating Nash Social Welfare in 2-Valued Instances

We consider the problem of maximizing the Nash social welfare when allocating a set $\mathcal{G}$ of goods to a set $\mathcal{N}$ of agents. We study instances, in which all agents have 2-valued additive valuations. In such an instance, the value of every agent $i \in \mathcal{N}$ for every item $j \in \mathcal{G}$ is $v_{ij} \in \{p,q\}$, for $p \le q \in \mathbb{N}$. We show that an optimal allocation can be computed in polynomial time if $p$ divides $q$. When $p$ does not divide $q$, we show an approximation ratio of at most $1.033$. It strictly decreases with the denominator of the irreducible fraction that equals $p/q$. Finally, we prove an APX-hardness result for the problem with a lower bound on the ratio of $1.000015$.