hide
Free keywords:
Computer Science, Computer Science and Game Theory, cs.GT
Abstract:
A set of $m$ indivisible goods is to be allocated to a set of $n$ agents.
Each agent $i$ has an additive valuation function $v_i$ over goods. The value
of a good $g$ for agent $i$ is either $1$ or $s$, where $s$ is a fixed rational
number greater than one, and the value of a bundle of goods is the sum of the
values of the goods in the bundle. An \emph{allocation} $X$ is a partition of
the goods into bundles $X_1$, \ldots, $X_n$, one for each agent. The \emph{Nash
Social Welfare} ($\NSW$) of an allocation $X$ is defined as \[ \NSW(X) = \left(
\prod_i v_i(X_i) \right)^{\sfrac{1}{n}}.\] The \emph{$\NSW$-allocation}
maximizes the Nash Social Welfare. In~\cite{NSW-twovalues-halfinteger} it was
shown that the $\NSW$-allocation can be computed in polynomial time, if $s$ is
an integer or a half-integer, and that the problem is NP-complete otherwise.
The proof for the half-integer case is quite involved. In this note we give a
simpler and shorter proof
