More Like this

1. A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations

   https://doi.org/10.1145/3618260  

   Dobzinski, Shahar ; Li, Wenzheng ; Rubinstein, Aviad ; Vondrak, Jan ( June 2024 , ACM)

   Mohar, Bojan ; Shinkar, Igor ; O'Donnell, Ryan (Ed.)

   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 that (1) solve a conguration-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. 

   more » « less
2. Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings

   https://doi.org/10.1137/1.9781611975994.163  

   Garg, Jugal ; Kulkarni, Pooja ; Kulkarni, Rucha ( January 2020 , Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms)

   We study the problem of approximating maximum Nash social welfare (NSW) when allocating m indivisible items among n asymmetric agents with submodular valuations. The NSW is a well-established notion of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For special cases of the problem with symmetric agents and additive(-like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with factor independent of m is known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(-like) valuations. In this paper, we extend our understanding of the NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations respectively. Both algorithms are simple to understand and involve non-trivial modifications of a greedy repeated matchings approach. Allocations of high valued items are done separately by un-matching certain items and re-matching them, by processes that are different in both algorithms. We show that these approaches achieve approximation factors of O(n) and O(n log n) for additive and submodular case respectively, which is independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envy-free up to one item (EF1). Furthermore, we show that the NSW problem under submodular valuations is strictly harder than all currently known settings with an e/(e-1) factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of e/(e-1), hence resolving it completely. 

   more » « less
3. Approximating nash social welfare under rado valuations

   https://doi.org/10.1145/3476436.3476444  

   Garg, Jugal ; Husić, Edin ; Végh, László A. ( June 2021 , ACM SIGecom Exchanges)

   The Nash social welfare problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents' valuations. We give an overview of the constant-factor approximation algorithm for the problem when agents have Rado valuations [Garg et al. 2021]. Rado valuations are a common generalization of the assignment (OXS) valuations and weighted matroid rank functions. Our approach also gives the first constant-factor approximation algorithm for the asymmetric Nash social welfare problem under the same valuations, provided that the maximum ratio between the weights is bounded by a constant. 

   more » « less
4. A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations

   https://doi.org/10.1109/FOCS52979.2021.00012  

   Li, Wenzheng ; Vondrak, Jan ( February 2022 , 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS))

   Nisheeth K. Vishnoi (Ed.)

   We present a 380-approximation algorithm for the Nash Social Welfare problem with submodular valuations. Our algorithm builds on and extends a recent constant-factor approximation for Rado valuations [15]. 

   more » « less
5. Fair Division of Indivisible Goods for a Class of Concave Valuations

   https://doi.org/10.1613/jair.1.12911  

   Chaudhury, Bhaskar Ray ; Cheung, Yun Kuen ; Garg, Jugal ; Garg, Naveen ; Hoefer, Martin ; Mehlhorn, Kurt ( May 2022 , Journal of Artificial Intelligence Research)

   We study the fair and efficient allocation of a set of indivisible goods among agents, where each good has several copies, and each agent has an additively separable concave valuation function with a threshold. These valuations capture the property of diminishing marginal returns, and they are more general than the well-studied case of additive valuations. We present a polynomial-time algorithm that approximates the optimal Nash social welfare (NSW) up to a factor of e1/e ≈ 1.445. This matches with the state-of-the-art approximation factor for additive valuations. The computed allocation also satisfies the popular fairness guarantee of envy-freeness up to one good (EF1) up to a factor of 2 + ε. For instances without thresholds, it is also approximately Pareto-optimal. For instances satisfying a large market property, we show an improved approximation factor. Lastly, we show that the upper bounds on the optimal NSW introduced in Cole and Gkatzelis (2018) and Barman et al. (2018) have the same value. 

   more » « less