Computing Epistemtic EF1 and Pareto-Optimal Allocations of Indivisible Chores

Computing Epistemtic EF1 and Pareto-Optimal Allocations of Indivisible Chores

Jugal Garg, Aniket Murhekar

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence
Main Track. Pages 3427-3435. https://doi.org/10.24963/ijcai.2026/381

We study the allocation of m indivisible chores among n agents with additive disutilities under the fairness notion of envy-freeness up to one chore (EF1) and the efficiency notion of Pareto-optimality (PO). Although the existence of an allocation satisfying both EF1 and PO was recently established using a highly non-constructive fixed-point argument, an effective algorithm for computing such an allocation remains elusive, prompting the study of meaningful relaxations of these desiderata. Prior work introduced a natural relaxation through the concept of epistemic fairness: an allocation is said to be epistemic EF1 (EEF1), if for every agent i, it is possible to re-allocate the bundles of agents other than i such that i becomes EF1. In this work, we present a pseudo-polynomial time algorithm for computing an allocation of chores that is both EEF1 and PO. This gives an efficient polynomial-time algorithm for most practical settings where disutility values are integral and polynomially bounded in m and n. Our result employs the competitive equilibrium framework and relies on several technical insights that both utilize the distinct structure of epistemic EF1 and address the challenges it introduces.
Keywords:
Game Theory and Economic Paradigms: Fair division
Game Theory and Economic Paradigms: Computational social choice