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.
NP-Hardness of Approximating Nash Social Welfare with Supermodular Valuations
Related papers
Ranked by semantic similarity — how closely each paper's abstract matches this one (100% = near-identical topic).
- Greedy Algorithms for Maximizing Nash Social Welfare (2018)72% match
- Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations (2024)72% match
- Estimating the Nash Social Welfare for coverage and other submodular valuations (2021)72% match
- Maximizing Nash Social Welfare in 2-Value Instances (2021)71% match
- Improved Hardness Results for Nash Social Welfare, Budgeted Allocation and GAP via the Unique Games Conjecture (2026)70% match
- Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps (2025)70% match
- Approximating One-Sided and Two-Sided Nash Social Welfare With Capacities (2024)70% match
- Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations (2020)70% match