 Award ID(s):
 1942321
 NSFPAR ID:
 10317977
 Date Published:
 Journal Name:
 ACM SIGecom Exchanges
 Volume:
 19
 Issue:
 1
 ISSN:
 15519031
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Mohar, Bojan ; Shinkar, Igor ; O'Donnell, Ryan (Ed.)We present a constantfactor 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 congurationtype LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constantfactor approximation for submodular valuations with value queries can also be derived from our framework.more » « less

Mohar, Bojan ; Shinkar, Igor ; O'Donnell, Ryan (Ed.)We present a constantfactor 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 configurationtype LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constantfactor approximation for submodular valuations with value queries can also be derived from our framework.more » « less

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 wellestablished 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 nontrivial modifications of a greedy repeated matchings approach. Allocations of high valued items are done separately by unmatching certain items and rematching 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 envyfree 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/(e1) 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/(e1), hence resolving it completely.more » « less

We study the problem of approximating maximum Nash social welfare (NSW) when allocating
m indivisible items amongn asymmetric agents with submodular valuations. TheNSW is a wellestablished 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 a factor independent ofm was known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(like) valuations before this work.In this article, 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. Both algorithms are simple to understand and involve nontrivial modifications of a greedy repeated matchings approach. Allocations of highvalued items are done separately by unmatching certain items and rematching them by different processes in both algorithms. We show that these approaches achieve approximation factors ofO (n ) andO (n logn ) for additive and submodular cases, independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envyfree 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 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\(\frac{\mathrm{e}}{\mathrm{e}1}\) , hence resolving it completely.\(\frac{\mathrm{e}}{\mathrm{e}1}\)