AIConfPaper
IJCAI 2024poster1 citations

Fair and Efficient Chore Allocation: Existence and Computation

Aniket Murhekar

Source ↗PDF ↗Scholar ↗

Abstract

We investigate the existence and computation of fair and efficient allocations of indivisible chores to agents with additive preferences. We consider the popular envy-based fairness notions of envy-freeness up to one chore (EF1) and the efficiency notion of Pareto-optimality (PO). The existence of an allocation of chores that is simultaneously EF1 and PO is regarded a major open problem in discrete fair division. We show that an EF1 and PO allocation can be computed in polynomial time for certain structured instances. These results comprise the first non-trivial positive results for the problem and reveal insights towards settling the problem in its full generality.

DC: Game Theory and Economic Paradigms
BibTeX
@inproceedings{ijcai2024p965,
  title     = {Fair and Efficient Chore Allocation: Existence and Computation},
  author    = {Murhekar, Aniket},
  booktitle = {Proceedings of the Thirty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-24}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Kate Larson},
  pages     = {8500--8501},
  year      = {2024},
  month     = {8},
  note      = {Doctoral Consortium},
  doi       = {10.24963/ijcai.2024/965},
  url       = {https://doi.org/10.24963/ijcai.2024/965},
}
Fair and Efficient Chore Allocation: Existence and Computation · IJCAI 2024