Score: 0
NP-Hardness of Approximating Nash Social Welfare with Supermodular Valuations
Published: October 30, 2025 |
arXiv ID: 2510.26055v1
By: Alon Bebchuk
Potential Business Impact:
Makes fair sharing of items impossible.
Business Areas:
Social
Community and Lifestyle
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.
Similar Papers
90%
Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
CS and Game Theory
Makes sharing items fairer for everyone.
13 Apr 2025
1
89%
Welfare Approximation in Additively Separable Hedonic Games
CS and Game Theory
Helps divide things fairly to make everyone happy.
8 Mar 2025
0
88%
Maximizing social welfare among EF1 allocations at the presence of two types of agents
CS and Game Theory
Divides things fairly, giving almost everyone what they want.
11 Sep 2025
0
Page Count
10 pages
Category
Computer Science:
CS and Game Theory