NP-Hardness of Approximating Nash Social Welfare with Supermodular Valuations
Abstract
We study the problem of allocating a set of indivisible items to agents with supermodular utilities to maximize the Nash social welfare. We show that the problem is NP-hard for any approximation factor.