{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T05:03:31Z","timestamp":1769749411031,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":69,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,7]]},"DOI":"10.1145\/3736252.3742562","type":"proceedings-article","created":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:49:32Z","timestamp":1751482172000},"page":"412-440","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximability Landscape of Welfare Maximization within Fair Allocations"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-3997-4650","authenticated-orcid":false,"given":"Xiaolin","family":"Bu","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5287-2247","authenticated-orcid":false,"given":"Zihao","family":"Li","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5786-6938","authenticated-orcid":false,"given":"Shengxin","family":"Liu","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4847-9183","authenticated-orcid":false,"given":"Jiaxin","family":"Song","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Champaign, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4098-844X","authenticated-orcid":false,"given":"Biaoshuai","family":"Tao","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}]}],"member":"320","published-online":{"date-parts":[[2025,7,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1257\/000282805774670167"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597799"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v39i13.33476"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103965"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.02.020"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3670865.3673582"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.07.006"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2781776"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2484920.2484976"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2022.10.013"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2020.07.005"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i6.16647"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64946-3_25"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331927"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219176"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v26i1.8243"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103436"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-021-10039-8"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i5.20410"},{"key":"e_1_3_2_1_20_1","volume-title":"17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23)","author":"Bhardwaj Romil","year":"2023","unstructured":"Romil Bhardwaj, Kirthevasan Kandasamy, Asim Biswal, Wenshuo Guo, Benjamin Hindman, Joseph Gonzalez, Michael Jordan, and Ion Stoica. 2023. Cilantro: Performance-Aware Resource Allocation for General Objectives via Online Feedback. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). USENIX Association, Boston, MA, 623\u2013643. https:\/\/www.usenix.org\/conference\/osdi23\/presentation\/bhardwaj"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511598975"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI'12)","author":"Brams Steven J.","unstructured":"Steven J. Brams, Michal Feldman, John K. Lai, Jamie Morgenstern, and Ariel D. Procaccia. 2012. On maxsum fair cake divisions. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI'12). AAAI Press, Toronto, Ontario, Canada, 1285\u20131291."},{"key":"e_1_3_2_1_23_1","volume-title":"Procaccia","author":"Brandt Felix","year":"2016","unstructured":"Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D. Procaccia. 2016. Handbook of Computational Social Choice (1st ed.). Cambridge University Press, USA."},{"key":"e_1_3_2_1_24_1","unstructured":"Xiaolin Bu Zihao Li Shengxin Liu Jiaxin Song and Biaoshuai Tao. 2025. Approximability Landscape of Welfare Maximization within Fair Allocations. arXiv:2205.14296 [cs.GT] https:\/\/arxiv.org\/abs\/2205.14296"},{"key":"e_1_3_2_1_25_1","volume-title":"Frontiers of Algorithmics","author":"Bu Xiaolin","unstructured":"Xiaolin Bu, Jiaxin Song, and Ziqi Yu. 2023. EFX Allocations Exist for Binary Valuations. In Frontiers of Algorithmics. Springer Nature Switzerland, Cham, 252\u2013262."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.102.5.2237"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2023\/284"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329574"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9359-y"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3616009"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467605"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1359134"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597764"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2024\/300"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI'11)","author":"Cohler Yuga J.","unstructured":"Yuga J. Cohler, John K. Lai, David C. Parkes, and Ariel D. Procaccia. 2011. Optimal envy-free cake cutting. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI'11). AAAI Press, San Francisco, California, 626\u2013631."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085125"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13779"},{"key":"e_1_3_2_1_42_1","unstructured":"Ulle Endriss. 2017. Trends in Computational Social Choice. Lulu.com."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367073"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113932"},{"key":"e_1_3_2_1_45_1","unstructured":"Jugal Garg Aniket Murhekar and John Qin. 2024. Constant-Factor EFX Exists for Chores. arXiv:2407.03318 [cs.GT] https:\/\/arxiv.org\/abs\/2407.03318"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation","author":"Ghodsi Ali","year":"2011","unstructured":"Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. 2011. Dominant resource fairness: fair allocation of multiple resource types. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (Boston, MA) (NSDI'11). USENIX Association, USA, 323\u2013336."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V39I13.33519"},{"key":"e_1_3_2_1_48_1","volume-title":"Proceedings of the Twenty-First European Conference on Artificial Intelligence (Prague, Czech Republic) (ECAI'14)","author":"Gourv\u00e8s Laurent","year":"2014","unstructured":"Laurent Gourv\u00e8s, J\u00e9r\u00f4me Monnot, and Lydia Tlilane. 2014. Near fairness in matroids. In Proceedings of the Twenty-First European Conference on Artificial Intelligence (Prague, Czech Republic) (ECAI'14). IOS Press, NLD, 393\u2013398."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_3_2_1_51_1","unstructured":"Vishwa Prakash HV Pratik Ghosal Prajakta Nimbhorkar and Nithin Varma. 2025. EFX Exists for Three Types of Agents. arXiv:2410.13580 [cs.GT] https:\/\/arxiv.org\/abs\/2410.13580"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875607"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/11600930_10"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501161"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/3635637.3662975"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V32I1.11484"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988792"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.0044"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-economics-080218-025559"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i6.16703"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M124397X"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-018-1128-6"},{"key":"e_1_3_2_1_64_1","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","unstructured":"Vijay V. Vazirani. 2010. Approximation Algorithms. Springer Publishing Company, Incorporated, USA."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_3_2_1_67_1","volume-title":"Karma: Resource Allocation for Dynamic Demands. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23)","author":"Vuppalapati Midhul","year":"2023","unstructured":"Midhul Vuppalapati, Giannis Fikioris, Rachit Agarwal, Asaf Cidon, Anurag Khandelwal, and \u00c9va Tardos. 2023. Karma: Resource Allocation for Dynamic Demands. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). USENIX Association, Boston, MA, 645\u2013662. https:\/\/www.usenix.org\/conference\/osdi23\/presentation\/vuppalapati"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.104037"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2007.V003A006"}],"event":{"name":"EC '25: 26th ACM Conference on Economics and Computation","location":"Stanford University Stanford CA USA","acronym":"EC '25","sponsor":["SIGecom ACM Special Interest Group on Economics and Computation"]},"container-title":["Proceedings of the 26th ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736252.3742562","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:49:56Z","timestamp":1751482196000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736252.3742562"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,2]]},"references-count":69,"alternative-id":["10.1145\/3736252.3742562","10.1145\/3736252"],"URL":"https:\/\/doi.org\/10.1145\/3736252.3742562","relation":{},"subject":[],"published":{"date-parts":[[2025,7,2]]},"assertion":[{"value":"2025-07-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}