NP-Hardness of Approximating Nash Social Welfare with Supermodular Valuations
arXiv:2510.26055
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.