New Algorithms for the Fair and Efficient Allocation of Indivisible Chores

Autor:	Garg, Jugal, Murhekar, Aniket, Qin, John
Rok vydání:	2022
Předmět:	Computer Science - Computer Science and Game Theory Computer Science - Multiagent Systems
Druh dokumentu:	Working Paper
DOI:	10.24963/ijcai.2023/302
Popis:	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 disutilities. 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. Comment: 43 pages. Accepted to IJCAI 2023. This version corrects a typo in Theorem 2
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2212.02440 Zobrazit plný text záznamu View this record from Arxiv