Approximating Nash social welfare under submodular valuations through (un)matchings

Jugal Garg, Pooja Kulkarni, Rucha Kulkarni

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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−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.

Original languageEnglish (US)
Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
EditorsShuchi Chawla
PublisherAssociation for Computing Machinery
Pages2673-2687
Number of pages15
ISBN (Electronic)9781611975994
StatePublished - Jan 1 2020
Event31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States
Duration: Jan 5 2020Jan 8 2020

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2020-January

Conference

Conference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
CountryUnited States
CitySalt Lake City
Period1/5/201/8/20

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Approximating Nash social welfare under submodular valuations through (un)matchings'. Together they form a unique fingerprint.

Cite this