{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T00:17:00Z","timestamp":1775607420505,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":69,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1942321"],"award-info":[{"award-number":["CCF-1942321"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451031","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1412-1425","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Approximating Nash social welfare under rado valuations"],"prefix":"10.1145","author":[{"given":"Jugal","family":"Garg","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6708-5112","authenticated-orcid":false,"given":"Edin","family":"Husi\u0107","sequence":"additional","affiliation":[{"name":"London School of Economics and Political Science, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"additional","affiliation":[{"name":"London School of Economics and Political Science, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS)","volume":"67","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), Vol. 67. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 36."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.147"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3070694"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/080723491"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132522"},{"key":"e_1_3_2_1_6_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."},{"key":"e_1_3_2_1_7_1","volume-title":"Tight Approximation Algorithms for $p$-Mean Welfare Under Subadditive Valuations. arXiv preprint arXiv:2005.07370","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. arXiv preprint arXiv:2005.07370 (2020)."},{"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.1017\/CBO9780511598975"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Felix Brandt Vincent Conitzer Ulle Endriss J\u00e9r\u00f4me Lang and Ariel D. Procaccia (Eds.). 2016. Handbook of Computational Social Choice. Cambridge University Press.","DOI":"10.1017\/CBO9781107446984.002"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329574"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-009-0157-6"},{"key":"e_1_3_2_1_14_1","first-page":"1","article-title":"On Fair Division for Indivisible Items. In Proceedings of the 38th IARCS annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","volume":"25","author":"Chaudhury Bhaskar Ray","year":"2018","unstructured":"Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn. 2018. On Fair Division for Indivisible Items. In Proceedings of the 38th IARCS annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Springer, 25:1\u201317.","journal-title":"Springer"},{"key":"e_1_3_2_1_15_1","volume-title":"Fair and Efficient Allocations under Subadditive Valuations. arXiv preprint arXiv:2005.06511","author":"Chaudhury Bhaskar Ray","year":"2020","unstructured":"Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta. 2020. Fair and Efficient Allocations under Subadditive Valuations. arXiv preprint arXiv:2005.06511 (2020)."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746589"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.167"},{"key":"e_1_3_2_1_18_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."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch7"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.7.4.337"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706369"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680977"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.463.16393"},{"key":"e_1_3_2_1_24_1","volume-title":"Satiation in Fisher Markets and Approximation of Nash Social Welfare. arXiv preprint arXiv:1707.04428","author":"Garg Jugal","year":"2017","unstructured":"Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. 2017. Satiation in Fisher Markets and Approximation of Nash Social Welfare. arXiv preprint arXiv:1707.04428 (2017)."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.150"},{"key":"e_1_3_2_1_26_1","volume-title":"V\u00e9gh","author":"Garg Jugal","year":"2019","unstructured":"Jugal Garg, Edin Husi\u0107, and L\u00e1szl\u00f3 A. V\u00e9gh. 2019. Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands and their Applications. arXiv preprint arXiv:1908.07948 (2019)."},{"key":"e_1_3_2_1_27_1","volume-title":"V\u00e9gh","author":"Garg Jugal","year":"2020","unstructured":"Jugal Garg, Edin Husi\u0107, and L\u00e1szl\u00f3 A. V\u00e9gh. 2020. Approximating Nash Social Welfare under Rado Valuations. arXiv preprint arXiv:2009.14793 (2020)."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.163"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11618"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2728732.2728738"},{"key":"e_1_3_2_1_31_1","volume-title":"Geometric algorithms and combinatorial optimization","author":"Gr\u00f6tschel Martin","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 2012. Geometric algorithms and combinatorial optimization. Vol. 2. Springer Science & Business Media."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"e_1_3_2_1_33_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."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Harold Houba Gerard van der Laan and Yuyu Zeng. 2013. Asymmetric Nash solutions in the river sharing problem. (2013).","DOI":"10.2139\/ssrn.2243424"},{"key":"e_1_3_2_1_35_1","volume-title":"Polyhedral aspects of submodularity, convexity and concavity. arXiv preprint arXiv:1506.07329","author":"Iyer Rishabh","year":"2015","unstructured":"Rishabh Iyer and Jeff Bilmes. 2015. Polyhedral aspects of submodularity, convexity and concavity. arXiv preprint arXiv:1506.07329 (2015)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01774658"},{"key":"e_1_3_2_1_37_1","volume-title":"The Nash social welfare function. Econometrica: Journal of the Econometric Society","author":"Kaneko Mamoru","year":"1979","unstructured":"Mamoru Kaneko and Kenjiro Nakamura. 1979. The Nash social welfare function. Econometrica: Journal of the Econometric Society (1979), 423\u2013435."},{"key":"e_1_3_2_1_38_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."},{"key":"e_1_3_2_1_39_1","volume-title":"Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society","author":"Kelso Alexander S","year":"1982","unstructured":"Alexander S Kelso Jr and Vincent P Crawford. 1982. Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society (1982), 1483\u20131504."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118759.3119047"},{"key":"e_1_3_2_1_41_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Khot Subhash","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_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.05.004"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_3_2_1_44_1","volume-title":"EC'18 Tutorial: \"Gross Substitutes: Combinatorial Structure and Algorithms\". https:\/\/www.youtube.com\/watch?v=FJF0Py48wK4&t=424s.","author":"Leme Renato Paes","year":"2018","unstructured":"Renato Paes Leme. 2018 (accessed April, 2020). EC'18 Tutorial: \"Gross Substitutes: Combinatorial Structure and Algorithms\". https:\/\/www.youtube.com\/watch?v=FJF0Py48wK4&t=424s."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.69"},{"key":"e_1_3_2_1_46_1","volume-title":"Fair division and collective welfare","author":"Moulin Herv\u00e9","unstructured":"Herv\u00e9 Moulin. 2004. Fair division and collective welfare. MIT press."},{"key":"e_1_3_2_1_47_1","series-title":"SIAM monographs on discrete mathematics and applications","volume-title":"Discrete convex analysis","author":"Murota Kazuo","unstructured":"Kazuo Murota. 2003. Discrete convex analysis. SIAM monographs on discrete mathematics and applications, Vol. 10. SIAM."},{"key":"e_1_3_2_1_48_1","unstructured":"Kazuo Murota. 2015 (accessed February 2020). Lecture \"Extensions and Ramifications of Discrete Convexity Concepts\". https:\/\/www.youtube.com\/watch?v=E-WjIrVm5Yk&t=8s."},{"key":"e_1_3_2_1_49_1","unstructured":"Kazuo Murota. 2015 (accessed February 2020). Problems for \"Discrete Convex Analysis\". https:\/\/www.him.uni-bonn.de\/uploads\/media\/HIMSummerSchool15MurotaProblem.pdf."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.22574\/jmid.2016.12.005"},{"key":"e_1_3_2_1_51_1","volume-title":"The bargaining problem. Econometrica: Journal of the econometric society","author":"Nash John F","year":"1950","unstructured":"John F Nash. 1950. The bargaining problem. Econometrica: Journal of the econometric society (1950), 155\u2013162."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-018-0195-5"},{"key":"e_1_3_2_1_53_1","volume-title":"Magnus Roos, and J\u00f6rg Rothe.","author":"Nguyen Nhan-Tam","year":"2014","unstructured":"Nhan-Tam Nguyen, Trung Thanh Nguyen, Magnus Roos, and J\u00f6rg Rothe. 2014. Computational complexity and approximability of social welfare optimization in multiagent resource allocation. Autonomous agents and multi-agent systems 28, 2 (2014), 256\u2013289."},{"key":"e_1_3_2_1_54_1","volume-title":"Algorithmic game theory","author":"Nisan Noam","unstructured":"Noam Nisan, Tim Roughgarden, \\'Eva Tardos, and Vijay V Vazirani. 2007. Algorithmic game theory. Cambridge University Press."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806731"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.3982\/TE1840"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2017.10.016"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/os-13.1.83"},{"key":"e_1_3_2_1_59_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."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"crossref","unstructured":"J\u00f6rg Rothe (Ed.). 2016. Economics and Computation An Introduction to Algorithmic Game Theory Computational Social Choice and Fair Division. Springer.","DOI":"10.1007\/978-3-662-47904-9"},{"key":"e_1_3_2_1_61_1","volume-title":"Combinatorial optimization: Polyhedra and efficiency","author":"Schrijver Alexander","unstructured":"Alexander Schrijver. 2003. Combinatorial optimization: Polyhedra and efficiency. Vol. 24. Springer Science & Business Media."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800090106"},{"key":"e_1_3_2_1_63_1","volume-title":"The finite matroid-based valuation conjecture is false. arXiv preprint arXiv:1905.02287","author":"Tran Ngoc Mai","year":"2019","unstructured":"Ngoc Mai Tran. 2019. The finite matroid-based valuation conjecture is false. arXiv preprint arXiv:1905.02287 (2019)."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90075-1"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160160"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/140978296"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_3_2_1_68_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."},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10784-017-9351-3"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451031","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451031","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451031","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451031"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":69,"alternative-id":["10.1145\/3406325.3451031","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451031","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}