{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T01:30:29Z","timestamp":1781659829623,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ScaleOpt--757481"],"award-info":[{"award-number":["ScaleOpt--757481"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2127781, CCF-1942321"],"award-info":[{"award-number":["CCF-2127781, CCF-1942321"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swiss National Science Foundation","award":["200021200731\/1"],"award-info":[{"award-number":["200021200731\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585255","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1298-1310","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximating Nash Social Welfare by Matching and Local Search"],"prefix":"10.1145","author":[{"given":"Jugal","family":"Garg","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edin","family":"Husi\u0107","sequence":"additional","affiliation":[{"name":"USI Lugano, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenzheng","family":"Li","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"additional","affiliation":[{"name":"London School of Economics, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Vondr\u00e1k","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.02.020"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS).","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 Conference (ITCS). 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 Conference (ITCS)."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.147"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132522"},{"key":"e_1_3_2_1_5_1","volume-title":"The geometry of efficient fair division","author":"Barbanel Julius B","unstructured":"Julius B Barbanel . 2005. The geometry of efficient fair division . Cambridge University Press . Julius B Barbanel. 2005. The geometry of efficient fair division. Cambridge University Press."},{"key":"e_1_3_2_1_6_1","volume-title":"28th Annual European Symposium on Algorithms (ESA). 173","author":"Barman Siddharth","unstructured":"Siddharth Barman , Umang Bhaskar , Anand Krishna , and Ranjani G. Sundaram . 2020. Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations . In 28th Annual European Symposium on Algorithms (ESA). 173 , 11:1\u201311:17. Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram. 2020. Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations. In 28th Annual European Symposium on Algorithms (ESA). 173, 11:1\u201311:17."},{"key":"e_1_3_2_1_7_1","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. \t\t\t\t  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."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219176"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i5.20410"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511598975"},{"key":"e_1_3_2_1_11_1","volume-title":"Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D","unstructured":"2016. Handbook of Computational Social Choice , Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D . Procaccia (Eds.). Cambridge University Press . 2016. Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329574"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-009-0157-6"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.12911"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399511"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i6.16665"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1359134"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085109"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053682"},{"key":"e_1_3_2_1_22_1","volume-title":"Water allocation in transboundary river basins under water scarcity: a cooperative bargaining approach. Water resources management, 30, 12","author":"Degefu Dagmawi Mulugeta","year":"2016","unstructured":"Dagmawi Mulugeta Degefu , Weijun He , Liang Yuan , and Jian Hua Zhao . 2016. Water allocation in transboundary river basins under water scarcity: a cooperative bargaining approach. Water resources management, 30, 12 ( 2016 ), 4451\u20134466. Dagmawi Mulugeta Degefu, Weijun He, Liang Yuan, and Jian Hua Zhao. 2016. Water allocation in transboundary river basins under water scarcity: a cooperative bargaining approach. Water resources management, 30, 12 (2016), 4451\u20134466."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0436"},{"key":"e_1_3_2_1_24_1","volume-title":"On Optimal Tradeoffs between EFX and Nash Welfare. CoRR, abs\/2302.09633","author":"Feldman Michal","year":"2023","unstructured":"Michal Feldman , Simon Mauras , and Tomasz Ponitka . 2023. On Optimal Tradeoffs between EFX and Nash Welfare. CoRR, abs\/2302.09633 ( 2023 ). Michal Feldman, Simon Mauras, and Tomasz Ponitka. 2023. On Optimal Tradeoffs between EFX and Nash Welfare. CoRR, abs\/2302.09633 (2023)."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229055"},{"key":"e_1_3_2_1_26_1","unstructured":"Jugal Garg Martin Hoefer and Kurt Mehlhorn. 2017. Satiation in Fisher Markets and Approximation of Nash Social Welfare. arXiv preprint arXiv:1707.04428. \t\t\t\t  Jugal Garg Martin Hoefer and Kurt Mehlhorn. 2017. Satiation in Fisher Markets and Approximation of Nash Social Welfare. arXiv preprint arXiv:1707.04428."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.150"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451031"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.163"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1561\/102.00000049"},{"key":"e_1_3_2_1_31_1","volume-title":"A generalized Nash solution for two-person bargaining games with incomplete information. Management science, 18, 5-part-2","author":"Harsanyi John C","year":"1972","unstructured":"John C Harsanyi and Reinhard Selten . 1972. A generalized Nash solution for two-person bargaining games with incomplete information. Management science, 18, 5-part-2 ( 1972 ), 80\u2013106. John C Harsanyi and Reinhard Selten. 1972. A generalized Nash solution for two-person bargaining games with incomplete information. Management science, 18, 5-part-2 (1972), 80\u2013106."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01774658"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914191"},{"key":"e_1_3_2_1_34_1","volume-title":"Charging and rate control for elastic traffic. European transactions on Telecommunications, 8, 1","author":"Kelly Frank","year":"1997","unstructured":"Frank Kelly . 1997. Charging and rate control for elastic traffic. European transactions on Telecommunications, 8, 1 ( 1997 ), 33\u201337. Frank Kelly. 1997. Charging and rate control for elastic traffic. European transactions on Telecommunications, 8, 1 (1997), 33\u201337."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.05.004"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.01.012"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.69"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00012"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988792"},{"key":"e_1_3_2_1_40_1","first-page":"1","article-title":"Extension of Additive Valuations to General Valuations on the Existence of EFX","volume":"204","author":"Mahara Ryoga","year":"2021","unstructured":"Ryoga Mahara . 2021 . Extension of Additive Valuations to General Valuations on the Existence of EFX . In ESA. 204 , 66: 1 \u2013 66 :15. Ryoga Mahara. 2021. Extension of Additive Valuations to General Valuations on the Existence of EFX. In ESA. 204, 66:1\u201366:15.","journal-title":"ESA."},{"key":"e_1_3_2_1_41_1","volume-title":"Fair division and collective welfare","author":"Moulin Herv\u00e9","unstructured":"Herv\u00e9 Moulin . 2004. Fair division and collective welfare . MIT press . Herv\u00e9 Moulin. 2004. Fair division and collective welfare. MIT press."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907266"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M124397X"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382131"},{"key":"e_1_3_2_1_45_1","volume-title":"Cake-cutting algorithms: Be fair if you can","author":"Robertson Jack","unstructured":"Jack Robertson and William Webb . 1998. Cake-cutting algorithms: Be fair if you can . CRC Press . Jack Robertson and William Webb. 1998. Cake-cutting algorithms: Be fair if you can. CRC Press."},{"key":"e_1_3_2_1_46_1","volume-title":"Economics and computation. 4","author":"Rothe J\u00f6rg","unstructured":"J\u00f6rg Rothe . 2015. Economics and computation. 4 , Springer . J\u00f6rg Rothe. 2015. Economics and computation. 4, Springer."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90075-1"},{"key":"e_1_3_2_1_48_1","volume-title":"Equity: in theory and practice","author":"Young H Peyton","unstructured":"H Peyton Young . 1995. Equity: in theory and practice . Princeton University Press . H Peyton Young. 1995. Equity: in theory and practice. Princeton University Press."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10784-017-9351-3"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585255","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585255","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585255","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:02Z","timestamp":1750178822000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585255"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":49,"alternative-id":["10.1145\/3564246.3585255","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585255","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}