---
title: "Computing Epistemtic EF1 and Pareto-Optimal Allocations of Indivisible Chores"
authors:
  - "Jugal Garg"
  - "Aniket Murhekar"
doi: "10.24963/ijcai.2026/381"
url: "https://ijcai.org/proceedings/2026/381"
pdf: "https://ijcai.org/proceedings/2026/0381.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "3427-3435"
track: "Main Track"
keywords:
  - "Game Theory and Economic Paradigms: Fair division"
  - "Game Theory and Economic Paradigms: Computational social choice"
---

# 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*, pages 3427-3435. DOI: [10.24963/ijcai.2026/381](https://doi.org/10.24963/ijcai.2026/381)

## Abstract

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.