A constant factor approximation for Nash social welfare with subadditive valuations

2023/09/09 by Shahar Dobzinski, Wenzheng Li, Dobzinski, Shahar +5 · 1 citation
Engineering · #Transportation and Mobility Innovations

paper · pdf · doi:10.48550/arxiv.2309.04656

Abstract

We present a constant-factor approximation algorithm for the Nash social welfare maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a template for NSW optimization by solving a configuration-type LP and using a rounding procedure for (utilitarian) social welfare as a blackbox, which could be applicable to other variants of the problem.

Cited by

• Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations

Related

• A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations
• Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
• Approximating Nash Social Welfare by Matching and Local Search
• Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations
• Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps