We present a constant-factor approximation algorithm for the Nash Social Welfare (NSW) maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a framework for NSW optimization which assumes two subroutines which (1) solve a configuration-type LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constant-factor approximation for submodular valuations with value queries can also be derived from our framework.
No takes yet. Share an insight, caveat, or question.
Dobzinski et al. (2024) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: