TY - GEN
T1 - New Algorithms for the Fair and Efficient Allocation of Indivisible Chores
AU - Garg, Jugal
AU - Murhekar, Aniket
AU - Qin, John
N1 - Publisher Copyright:
© 2023 International Joint Conferences on Artificial Intelligence. All rights reserved.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85170373417&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85170373417&partnerID=8YFLogxK
U2 - 10.24963/ijcai.2023/302
DO - 10.24963/ijcai.2023/302
M3 - Conference contribution
AN - SCOPUS:85170373417
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 2710
EP - 2718
BT - Proceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
A2 - Elkind, Edith
PB - International Joint Conferences on Artificial Intelligence
T2 - 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
Y2 - 19 August 2023 through 25 August 2023
ER -