New Algorithms for the Fair and Efficient Allocation of Indivisible Chores
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 the 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.
Cite
Text
Garg et al. "New Algorithms for the Fair and Efficient Allocation of Indivisible Chores." International Joint Conference on Artificial Intelligence, 2023. doi:10.24963/IJCAI.2023/302Markdown
[Garg et al. "New Algorithms for the Fair and Efficient Allocation of Indivisible Chores." International Joint Conference on Artificial Intelligence, 2023.](https://mlanthology.org/ijcai/2023/garg2023ijcai-new/) doi:10.24963/IJCAI.2023/302BibTeX
@inproceedings{garg2023ijcai-new,
title = {{New Algorithms for the Fair and Efficient Allocation of Indivisible Chores}},
author = {Garg, Jugal and Murhekar, Aniket and Qin, John},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2023},
pages = {2710-2718},
doi = {10.24963/IJCAI.2023/302},
url = {https://mlanthology.org/ijcai/2023/garg2023ijcai-new/}
}