New Algorithms for the Fair and Efficient Allocation of Indivisible Chores

Jugal Garg, Aniket Murhekar, John Qin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 existence of an allocation that is • EF1+fPO, when there are three agents, • EF1+fPO, when there are at most two disutility functions, • EFX+fPO, for three agents with bivalued disutility functions. These 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
EditorsEdith Elkind
PublisherInternational Joint Conferences on Artificial Intelligence
Pages2710-2718
Number of pages9
ISBN (Electronic)9781956792034
StatePublished - 2023
Event32nd International Joint Conference on Artificial Intelligence, IJCAI 2023 - Macao, China
Duration: Aug 19 2023Aug 25 2023

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
Volume2023-August
ISSN (Print)1045-0823

Conference

Conference32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
Country/TerritoryChina
CityMacao
Period8/19/238/25/23

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'New Algorithms for the Fair and Efficient Allocation of Indivisible Chores'. Together they form a unique fingerprint.

Cite this