{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:24:03Z","timestamp":1792070643454,"version":"4.4.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,2,11]],"date-time":"2024-02-11T00:00:00Z","timestamp":1707609600000},"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"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,2,29]]},"abstract":"<jats:p>\n            We study the problem of distributing a set of indivisible goods among agents with additive valuations in a\n            <jats:italic>fair<\/jats:italic>\n            manner. The fairness notion under consideration is envy-freeness up to\n            <jats:italic>any<\/jats:italic>\n            good (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this article, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture of Caragiannis et\u00a0al. by showing an instance with three agents for which there is a partial EFX allocation (some goods are not allocated) with higher Nash welfare than that of any complete EFX allocation.\n          <\/jats:p>","DOI":"10.1145\/3616009","type":"journal-article","created":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T12:19:47Z","timestamp":1693829987000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["EFX Exists for Three Agents"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0213-6142","authenticated-orcid":false,"given":"Bhaskar Ray","family":"Chaudhury","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana\u2013Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6439-7308","authenticated-orcid":false,"given":"Jugal","family":"Garg","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana\u2013Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4020-4334","authenticated-orcid":false,"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarland Informatics Campus, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,2,11]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"www.spliddit.org"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3147173"},{"key":"e_1_3_2_4_2","first-page":"1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (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 Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917). 1\u201312."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.147"},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","unstructured":"Artem Baklanov Pranav Garimidi Vasilis Gkatzelis and Daniel Schoepflin. 2021. Achieving proportionality up to the maximin item with indivisible goods. In Thirty-Fifth AAAI Conference on Artificial Intelligence AAAI 5143\u20135150.","DOI":"10.1609\/aaai.v35i6.16650"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085136"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219176"},{"key":"e_1_3_2_9_2","first-page":"259","volume-title":"Autonomous Agents and Multi-Agent Systems","author":"Bouveret Sylvain","year":"2016","unstructured":"Sylvain Bouveret and Michel Lema\u00eetre. 2016. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems 30, 2 (2016), 259\u2013290."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2016.1544"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329574"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940726"},{"key":"e_1_3_2_14_2","first-page":"Article 25, 17","volume-title":"Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201918)","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\u201918). Article 25, 17 pages."},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","unstructured":"Bhaskar Ray Chaudhury Jugal Garg and Kurt Mehlhorn. 2020. EFX exists for three agents. In Proceedings of the 21st ACM Conference on Economics and Computation (EC) 1\u201319.","DOI":"10.1145\/3391403.3399511"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.162"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085109"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053682"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.150"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.163"},{"key":"e_1_3_2_21_2","first-page":"Article 20","volume-title":"Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA\u201919)","volume":"69","author":"Garg Jugal","year":"2019","unstructured":"Jugal Garg, Peter McGlaughlin, and Setareh Taki. 2019. Approximating maximin share allocations. In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA\u201919), Vol. 69. Article 20, 20:1\u201320:11."},{"key":"e_1_3_2_22_2","doi-asserted-by":"crossref","unstructured":"Jugal Garg and Setareh Taki. 2020. An improved approximation algorithm for maximin shares. In Proceedings of the 21st ACM Conference on Economics and Computation (EC) 379\u2013380.","DOI":"10.1145\/3391403.3399526"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219238"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","unstructured":"Jonathan R. Goldman and Ariel D. Procaccia. 2014. Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges 13 2 (2014) 41\u201346.","DOI":"10.1145\/2728732.2728738"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","unstructured":"Daniel Halpern Ariel D. Procaccia Alexandros Psomas and Nisarg Shah. 2020. Fair division with binary valuations: One rule to rule them all. In WINE Lecture Notes in Computer Science. Vol. 12495 Springer 370\u2013383.","DOI":"10.1007\/978-3-030-64946-3_26"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3274641"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3140756"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.01.012"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988792"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","unstructured":"Herve Moulin. 2019. Fair division in the internet age. Annual Review of Economics 11 2019.","DOI":"10.1146\/annurev-economics-080218-025559"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.165"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382131"},{"issue":"1","key":"e_1_3_2_33_2","first-page":"101","article-title":"The problem of fair division","volume":"16","author":"Steinhaus Hugo","year":"1948","unstructured":"Hugo Steinhaus. 1948. The problem of fair division. Econometrica 16, 1 (1948), 101\u2013104.","journal-title":"Econometrica"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3616009","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3616009","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:29Z","timestamp":1750178189000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3616009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,11]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2,29]]}},"alternative-id":["10.1145\/3616009"],"URL":"https:\/\/doi.org\/10.1145\/3616009","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,11]]},"assertion":[{"value":"2021-03-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}