{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:42:16Z","timestamp":1781077336406,"version":"3.54.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T00:00:00Z","timestamp":1695686400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1942321"],"award-info":[{"award-number":["CCF-1942321"]}]},{"name":"NSF","award":["CCF-1750436"],"award-info":[{"award-number":["CCF-1750436"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            We study the problem of approximating maximum Nash social welfare (NSW) when allocating\n            <jats:italic>m<\/jats:italic>\n            indivisible items among\n            <jats:italic>n<\/jats:italic>\n            asymmetric agents with submodular valuations. The\n            <jats:sans-serif>NSW<\/jats:sans-serif>\n            is a well-established notion of fairness and efficiency, defined as the weighted geometric mean of agents\u2019 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 of\n            <jats:italic>m<\/jats:italic>\n            was known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(-like) valuations before this work.\n          <\/jats:p>\n          <jats:p>\n            In this article, we extend our understanding of the\n            <jats:sans-serif>NSW<\/jats:sans-serif>\n            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 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 different processes in both algorithms. We show that these approaches achieve approximation factors of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) 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 envy-free up to one item (\n            <jats:sans-serif>EF1<\/jats:sans-serif>\n            ).\n          <\/jats:p>\n          <jats:p>\n            Furthermore, we show that the\n            <jats:sans-serif>NSW<\/jats:sans-serif>\n            problem under submodular valuations is strictly harder than all currently known settings with an\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\frac{\\mathrm{e}}{\\mathrm{e}-1}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            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\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\frac{\\mathrm{e}}{\\mathrm{e}-1}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , hence resolving it completely.\n          <\/jats:p>","DOI":"10.1145\/3613452","type":"journal-article","created":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T12:13:44Z","timestamp":1692188024000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6439-7308","authenticated-orcid":false,"given":"Jugal","family":"Garg","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1983-1317","authenticated-orcid":false,"given":"Pooja","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7636-6856","authenticated-orcid":false,"given":"Rucha","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,9,26]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"1","volume-title":"8th Innovations in Theoretical Computer Science Conf. (ITCS\u201917)","author":"Anari Nima","year":"2017","unstructured":"Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. 2017. Nash social welfare, matrix permanent, and stable polynomials. In 8th Innovations in Theoretical Computer Science Conf. (ITCS\u201917). 1\u201312."},{"key":"e_1_3_2_3_2","volume-title":"Proc. 29th Symp. on Discrete Algorithms (SODA\u201918)","author":"Anari Nima","year":"2018","unstructured":"Nima Anari, Tung Mai, Shayan Oveis Gharan, and Vijay V. Vazirani. 2018. Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. In Proc. 29th Symp. on Discrete Algorithms (SODA\u201918)."},{"key":"e_1_3_2_4_2","first-page":"1357","volume-title":"Proc. 26th Symp. on Discrete Algorithms (SODA\u201915)","author":"Annamalai Chidambaram","year":"2015","unstructured":"Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson. 2015. Combinatorial algorithm for restricted max-min fair allocation. In Proc. 26th Symp. on Discrete Algorithms (SODA\u201915). 1357\u20131372."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/080723491"},{"key":"e_1_3_2_6_2","first-page":"31","volume-title":"Symp. on Theory of Computing (STOC\u201906)","author":"Bansal Nikhil","year":"2006","unstructured":"Nikhil Bansal and Maxim Sviridenko. 2006. The Santa Claus problem. In Symp. on Theory of Computing (STOC\u201906). 31\u201340."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2020.11"},{"key":"e_1_3_2_8_2","article-title":"Sublinear approximation algorithm for Nash social welfare with XOS valuations","author":"Barman Siddharth","year":"2021","unstructured":"Siddharth Barman, Anand Krishna, Pooja Kulkarni, and Shivika Narang. 2021. Sublinear approximation algorithm for Nash social welfare with XOS valuations. arXiv preprint arXiv:2110.00767 (2021).","journal-title":"arXiv preprint arXiv:2110.00767"},{"key":"e_1_3_2_9_2","volume-title":"Proc. 19th Conf. on Economics and Computation (EC\u201918)","author":"Barman Siddharth","year":"2018","unstructured":"Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. 2018. Finding fair and efficient allocations. In Proc. 19th Conf. on Economics and Computation (EC\u201918)."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1120680.1120683"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_2_12_2","first-page":"305","volume-title":"Proc. 17th Conf. on Economics and Computation (EC\u201916)","author":"Caragiannis Ioannis","year":"2016","unstructured":"Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel Procaccia, Nisarg Shah, and Junxing Wang. 2016. The unreasonable fairness of maximum Nash welfare. In Proc. 17th Conf. on Economics and Computation (EC\u201916). 305\u2013322."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-009-0157-6"},{"key":"e_1_3_2_14_2","first-page":"5269","volume-title":"Proc. AAAI Conf. on Artificial Intelligence","author":"Chaudhury Bhaskar Ray","year":"2021","unstructured":"Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta. 2021. Fair and efficient allocations under subadditive valuations. In Proc. AAAI Conf. on Artificial Intelligence, Vol. 35. 5269\u20135276."},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1109\/FOCS.2010.60","volume-title":"2010 IEEE 51st Annual Symp. on Foundations of Computer Science","author":"Chekuri Chandra","year":"2010","unstructured":"Chandra Chekuri, Jan Vondrak, and Rico Zenklusen. 2010. Dependent randomized rounding via exchange properties of combinatorial structures. In 2010 IEEE 51st Annual Symp. on Foundations of Computer Science. IEEE, 575\u2013584."},{"key":"e_1_3_2_16_2","first-page":"25:1\u201325:17","volume-title":"Proc. 38th Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201918)","author":"Cheung Yun Kuen","year":"2018","unstructured":"Yun Kuen Cheung, Bhaskar Chaudhuri, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn. 2018. On fair division of indivisible items. In Proc. 38th Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201918). 25:1\u201325:17."},{"key":"e_1_3_2_17_2","volume-title":"Proc. 18th Conf. on Economics and Computation (EC\u201917)","author":"Cole Richard","year":"2017","unstructured":"Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay Vazirani, and Sadra Yazdanbod. 2017. Convex program duality, Fisher markets, and Nash social welfare. In Proc. 18th Conf. on Economics and Computation (EC\u201917)."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053682"},{"key":"e_1_3_2_19_2","volume-title":"Pro. 33rd AAAI Conf. on Artificial Intelligence (AAAI\u201919)","author":"Conitzer Vincent","year":"2019","unstructured":"Vincent Conitzer, Rupert Freeman, Nisarg Shah, and Jennifer Wortman Vaughan. 2019. Group fairness for the allocation of indivisible goods. In Pro. 33rd AAAI Conf. on Artificial Intelligence (AAAI\u201919)."},{"key":"e_1_3_2_20_2","first-page":"2748","volume-title":"Proc. 14th Annual ACM-SIAM Symp. on Discrete Algorithms","author":"Davies Sami","year":"2020","unstructured":"Sami Davies, Thomas Rothvoss, and Yihao Zhang. 2020. A tale of Santa Claus, hypergraphs and matroids. In Proc. 14th Annual ACM-SIAM Symp. on Discrete Algorithms. SIAM, 2748\u20132757."},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"2735","DOI":"10.1007\/s11269-018-1955-z","article-title":"Bankruptcy to surplus: Sharing transboundary river Basin\u2019s water under scarcity","volume":"32","author":"Degefu Dagmawi Mulugeta","year":"2018","unstructured":"Dagmawi Mulugeta Degefu, He Weijun, Yuan Liang, Min An, and Zhang Qi. 2018. Bankruptcy to surplus: Sharing transboundary river Basin\u2019s water under scarcity. Water Resources Management 32, 8 (2018), 2735\u20132751.","journal-title":"Water Resources Management"},{"key":"e_1_3_2_22_2","unstructured":"Jugal Garg Martin Hoefer and Kurt Mehlhorn. 2019. Approximating the Nash social welfare with budget-additive valuations. arxiv:1707.04428 (2019). Preliminary version appeared in the Proceedings of SODA 2018."},{"key":"e_1_3_2_23_2","article-title":"Approximating Nash social welfare by matching and local search","author":"Garg Jugal","year":"2022","unstructured":"Jugal Garg, Edin Husi\u0107, Wenzheng Li, L\u00e1szl\u00f3 A. V\u00e9gh, and Jan Vondr\u00e1k. 2022. Approximating Nash social welfare by matching and local search. arXiv:2211.03883 (2022).","journal-title":"arXiv:2211.03883"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"1412","DOI":"10.1145\/3406325.3451031","volume-title":"Proc. of the 53rd Annual ACM SIGACT Symp. on Theory of Computing","author":"Garg Jugal","year":"2021","unstructured":"Jugal Garg, Edin Husi\u0107, and L\u00e1szl\u00f3 A. V\u00e9gh. 2021. Approximating Nash social welfare under Rado valuations. In Proc. of the 53rd Annual ACM SIGACT Symp. on Theory of Computing. 1412\u20131425."},{"key":"e_1_3_2_25_2","first-page":"2673","volume-title":"Proc. 31st Symp. on Discrete Algorithms (SODA\u201920)","author":"Garg Jugal","year":"2020","unstructured":"Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. 2020. Approximating Nash social welfare under submodular valuations through (Un)Matchings. In Proc. 31st Symp. on Discrete Algorithms (SODA\u201920). 2673\u20132687."},{"key":"e_1_3_2_26_2","volume-title":"Proc. International Joint Conf. on Artificial Intelligence (IJCAI\u201919)","author":"Garg Jugal","year":"2019","unstructured":"Jugal Garg and Peter McGlaughlin. 2019. Improving Nash social welfare approximations. In Proc. International Joint Conf. on Artificial Intelligence (IJCAI\u201919)."},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1561\/102.00000049","article-title":"Asymmetric Nash solutions in the river sharing problem","volume":"4","author":"Houba H.","year":"2014","unstructured":"H. Houba, G. Van der Laan, and Y. Zeng. 2014. Asymmetric Nash solutions in the river sharing problem. Strategic Behavior and the Environment 4, 4 (2014), 321\u2013360.","journal-title":"Strategic Behavior and the Environment"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.5.80"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01774658"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460080106"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9105-7"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/978-3-540-74208-1_15","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Khot Subhash","year":"2007","unstructured":"Subhash Khot and Ashok Kumar Ponnuswami. 2007. Approximation algorithms for the max-min allocation problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 204\u2013217."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.05.004"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.01.012"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_3_2_36_2","first-page":"25","volume-title":"2021 IEEE 62nd Annual Symp. on Foundations of Computer Science (FOCS\u201922)","author":"Li Wenzheng","year":"2022","unstructured":"Wenzheng Li and Jan Vondr\u00e1k. 2022. A constant-factor approximation algorithm for Nash social welfare with submodular valuations. In 2021 IEEE 62nd Annual Symp. on Foundations of Computer Science (FOCS\u201922). IEEE, 25\u201336."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2954.001.0001"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.2307\/1907266"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.09.010"},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"Nisan Noam","year":"2007","unstructured":"Noam Nisan, \u00c9va Tardos, Tim Roughgarden, and Vijay Vazirani (Eds.). 2007. Algorithmic Game Theory. Cambridge University Press."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/100783352"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01769276"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90075-1"},{"key":"e_1_3_2_44_2","first-page":"67","volume-title":"Proc. 40th Symp. on Theory of Computing (STOC\u201908)","author":"Vondr\u00e1k Jan","year":"2008","unstructured":"Jan Vondr\u00e1k. 2008. Optimal approximation for the submodular welfare problem in the value oracle model. In Proc. 40th Symp. on Theory of Computing (STOC\u201908). 67\u201374."},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1007\/s10784-017-9351-3","article-title":"Nash bargaining solutions for international climate agreements under different sets of bargaining weights","volume":"17","author":"Yu S.","year":"2017","unstructured":"S. Yu, E. C. van Ierland, H.-P. Weikard, and X. Zhu. 2017. Nash bargaining solutions for international climate agreements under different sets of bargaining weights. International Environmental Agreements: Politics, Law and Economics 17, 5 (2017), 709\u2013729.","journal-title":"International Environmental Agreements: Politics, Law and Economics"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3613452","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3613452","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:30Z","timestamp":1750178190000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3613452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,26]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3613452"],"URL":"https:\/\/doi.org\/10.1145\/3613452","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,26]]},"assertion":[{"value":"2019-12-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-31","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}