Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability

We study the problem of allocating a set of indivisible goods among a set of agents with 2-value additive valuations. In this setting, each good is valued either 1 or p/q, for some fixed co-prime numbers p,q∈ mathbbN such that 1≤ q < p. Our goal is to find an allocation maximizing the Nash social welfare (NSW), i.e., the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of NSW maximization that solely depends on the values of q. We start by providing a rather simple polynomial-time algorithm to find a maximum NSW allocation when the valuation functions are integral, that is, q=1. We then exploit more involved techniques to get an algorithm producing a maximum NSW allocation for the half-integral case, that is, q=2. Finally, we show it is classNP-hard to compute an allocation with maximum NSW whenever q≥3.