NP-Hardness of Approximating Nash Social Welfare with Supermodular Valuations
Published: Oct 30, 2025
Last Updated: Oct 30, 2025
Authors:Alon Bebchuk
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.