Approximating Nash social welfare under rado valuations

DOI10.1145/3406325.3451031MaRDI QIDQ6065263zbMATH OpenOpenAlexFDO

Authors Jugal Garg, Edin Husić, László A. Végh

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.14793, http://eprints.lse.ac.uk/110989/1/main.pdf

zbMATH Keywords

approximation algorithmNash social welfareRado valuations

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to $n$ agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. This led to a flurry of work obtaining constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and $O(n)$-approximation algorithms for more general valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant.

Cited in

(16)

• Approximating Nash social welfare under binary XOS and binary subadditive valuations
• A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds
• An additive approximation scheme for the Nash social welfare maximization with identical additive valuations
• Radner's cost-benefit analysis in the small: an equivalence result
• Fair Division of Indivisible Goods for a Class of Concave Valuations
• Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
• Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
• Approximating Nash social welfare by matching and local search
• A constant-factor approximation for generalized malleable scheduling under \(M^{\natural }\)-concave processing speeds
• A note on approximating weighted Nash social welfare with additive valuations
• Weighted envy-freeness for submodular valuations
• An additive approximation scheme for the Nash social welfare maximization with identical additive valuations
• Sublinear approximation algorithm for Nash social welfare with XOS valuations
• A note on approximating weighted Nash social welfare with additive valuations
• On complete classes of valuated matroids
• Approximating Nash social welfare by matching and local search

This page was built for publication: Approximating Nash social welfare under rado valuations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065263)