{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T05:14:18Z","timestamp":1785906858780,"version":"3.56.0"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>We study the problem of fairly and efficiently allocating indivisible chores among agents with additive disutility functions. We consider the widely used envy-based fairness properties of EF1 and EFX in conjunction with the efficiency property of fractional Pareto-optimality (fPO). Existence (and computation) of an allocation that is simultaneously EF1\/EFX and fPO are challenging open problems, and we make progress on both of them. We show the existence of an allocation that is\n\n- EF1 + fPO, when there are three agents,\n\n- EF1 + fPO, when there are at most two disutility functions,\n\n- EFX + fPO, for three agents with bivalued disutility functions.\n\nThese results are constructive, based on strongly polynomial-time algorithms. We also investigate non-existence and show that an allocation that is EFX+fPO need not exist, even for two agents.<\/jats:p>","DOI":"10.24963\/ijcai.2023\/302","type":"proceedings-article","created":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:31:30Z","timestamp":1691742690000},"page":"2710-2718","source":"Crossref","is-referenced-by-count":9,"title":["New Algorithms for the Fair and Efficient Allocation of Indivisible Chores"],"prefix":"10.24963","author":[{"given":"Jugal","family":"Garg","sequence":"first","affiliation":[{"name":"UIUC"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aniket","family":"Murhekar","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Illinois Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}","theme":"Artificial Intelligence","location":"Macau, SAR China","acronym":"IJCAI-2023","number":"32","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2023,8,19]]},"end":{"date-parts":[[2023,8,25]]}},"container-title":["Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:44:48Z","timestamp":1691743488000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2023\/302"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2023\/302","relation":{},"subject":[],"published":{"date-parts":[[2023,8]]}}}