{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T14:52:31Z","timestamp":1781621551912,"version":"3.54.5"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T00:00:00Z","timestamp":1781568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"NSF","award":["2127781"],"award-info":[{"award-number":["2127781"]}]},{"name":"European Research Council","award":["757481"],"award-info":[{"award-number":["757481"]}]},{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["200021 200731\/1"],"award-info":[{"award-number":["200021 200731\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CCF-1942321 and CCF-2334461"],"award-info":[{"award-number":["CCF-1942321 and CCF-2334461"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>For any \u025b &gt; 0, we give a simple, deterministic (4+\u025b)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents\u2019 valuations, and give an e(\u03c9 + 2 + \u025b)-approximation if the ratio between the largest weight and the average weight is at most \u03c9.<\/jats:p>\n                  <jats:p>We also show that the 1\/2-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time that is both 1\/2-EFX and an (8+\u025b)-approximation to the symmetric NSW problem under submodular valuations.<\/jats:p>","DOI":"10.1145\/3807505","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T11:35:41Z","timestamp":1775561741000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Nash Social Welfare by Matching and Local Search"],"prefix":"10.1145","volume":"73","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","place":["Urbana, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6708-5112","authenticated-orcid":false,"given":"Edin","family":"Husi\u0107","sequence":"additional","affiliation":[{"name":"Istituto Dalle Molle di Studi sull'Intelligenza Artificiale, IDSIA","place":["Lugano, Switzerland"]},{"name":"Universit\u00e0 della Svizzera italiana","place":["Lugano, Switzerland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4972-7355","authenticated-orcid":false,"given":"Wenzheng","family":"Li","sequence":"additional","affiliation":[{"name":"Stanford University","place":["Stanford, United States"]},{"name":"Hertz Chair for Algorithms and Optimization, University of Bonn","place":["Stanford, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1152-200X","authenticated-orcid":false,"given":"L\u00e1szl\u00f3","family":"V\u00e9gh","sequence":"additional","affiliation":[{"name":"Mathematics, London School of Economics and Political Science","place":["London, United Kingdom of Great Britain and Northern Ireland"]},{"name":"Hertz Chair for Algorithms and Optimization, University of Bonn","place":["London, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-6021-679X","authenticated-orcid":false,"given":"Jan","family":"Vondr\u00e1k","sequence":"additional","affiliation":[{"name":"Stanford University","place":["Stanford, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,16]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/4"},{"key":"e_1_3_2_3_2","first-page":"36:1\u201336:12","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference","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 Proceedings of the 8th Innovations in Theoretical Computer Science Conference36:1\u201336:12."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.147"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132522"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546679"},{"key":"e_1_3_2_7_2","first-page":"11:1\u201311:17","volume-title":"Proceedings of the 28th Annual European Symposium on Algorithms","author":"Barman Siddharth","year":"2020","unstructured":"Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram. 2020. Tight approximation algorithms for p-mean welfare under subadditive valuations. In Proceedings of the 28th Annual European Symposium on Algorithms11:1\u201311:17."},{"key":"e_1_3_2_8_2","first-page":"8:1\u20138:23","volume-title":"Proceedings of the 15th Innovations in Theoretical Computer Science.","author":"Barman Siddharth","year":"2024","unstructured":"Siddharth Barman, Anand Krishna, Pooja Kulkarni, and Shivika Narang. 2024. Sublinear approximation algorithm for nash social welfare with XOS valuations. In Proceedings of the 15th Innovations in Theoretical Computer Science.8:1\u20138:23."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22832-2_15"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219176"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978971.61"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3798129.3800909"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Ben Berger Avi Cohen Michal Feldman and Amos Fiat. 2022. Almost full EFX exists for four agents. In Proceedings of the AAAI Conference on Artificial Intelligence.4826\u20134833.","DOI":"10.1609\/aaai.v36i5.20410"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511598975"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107446984"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.52"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.41.601"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(68)80071-7"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329574"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-009-0157-6"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.12911"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399511"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i6.16665"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1359134"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085109"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746589"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11269-016-1431-6"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649740"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0436"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v38i9.28826"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718203"},{"key":"e_1_3_2_34_2","first-page":"63:1\u201363:9","volume-title":"Proceedings of the 51st Intl. Coll. Automata, Languages and Programming","author":"Feng Yuda","year":"2024","unstructured":"Yuda Feng and Shi Li. 2024. A note on approximating weighted nash social welfare with additive valuations. In Proceedings of the 51st Intl. Coll. Automata, Languages and Programming. 63:1\u201363:9."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229055"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.150"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2019.0129"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585255"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451031"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.163"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1561\/102.00000049"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.5.80"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01774658"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.2307\/1914191"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460080106"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.05.004"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.01.012"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.69"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00012"},{"key":"e_1_3_2_50_2","unstructured":"Richard J. Lipton Evangelos Markakis Elchanan Mossel and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce. ACM 125\u2013131."},{"key":"e_1_3_2_51_2","first-page":"66:1\u201366:15","volume-title":"Proceedings of the ESA","author":"Mahara Ryoga","year":"2021","unstructured":"Ryoga Mahara. 2021. Extension of additive valuations to general valuations on the existence of EFX. In Proceedings of the ESA. 66:1\u201366:15."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597685"},{"key":"e_1_3_2_53_2","volume-title":"Fair Division and Collective Welfare","author":"Moulin Herv\u00e9","year":"2004","unstructured":"Herv\u00e9 Moulin. 2004. Fair Division and Collective Welfare. MIT press."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.2307\/1907266"},{"key":"e_1_3_2_55_2","author":"Natura Bento","year":"2023","unstructured":"Bento Natura. 2023. Personal communication.","journal-title":"Personal communication"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399465"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.165"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382131"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781439863855"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47904-9"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90075-1"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1515\/9780691214054"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10784-017-9351-3"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3807505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T13:59:04Z","timestamp":1781618344000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3807505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,16]]},"references-count":62,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3807505"],"URL":"https:\/\/doi.org\/10.1145\/3807505","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,16]]},"assertion":[{"value":"2024-07-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}