Maximizing Nash Social Welfare in 2-Value Instances: A Simpler Proof for the Half-Integer Case

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} ($\text{NSW}$) of an allocation $X$ is defined as $$\text{NSW}(X)={(\prod _i{v}_i(X_i))}^{\text{sfrac}1n}\mathrm{.}$$ The \emph{$\text{NSW}$-allocation} maximizes the Nash Social Welfare. In~\cite{NSW-twovalues-halfinteger} it was shown that the $\text{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