Connected EF1 Allocations Exist in Discrete Chore Cutting
Abstract
In this paper, we prove the existence of an envy-free up to one item (EF1) division for a discrete chore. Our approach builds on the powerful framework of Simmons-Su [Am. Math. Mon. 1999], which leverages Sperner's lemma to guarantee the existence of a simplex corresponding to a sequence of similar fractional divisions, ensuring that each agent is satisfied with a different bundle. Bilò et al. [ITCS 2019, Games Econ. Behav. 2022] introduced a rounding technique that converts the fractional divisions into a connected integral EF1 division for goods when there are at most four agents, and this method was later extended by Igarashi [AAAI 2023] to accommodate any number of agents. However, the analogous problem for chores has remained unresolved, and existing rounding techniques fail due to the asymmetric definitions of EF1 for goods and chores. To overcome this asymmetry, we refine the existing rounding techniques and show that connected EF1 divisions exist for a discrete chore.
BibTeX
@inproceedings{ijcai2026_connectedef1allo,
title = {Connected EF1 Allocations Exist in Discrete Chore Cutting},
author = {Ankang Sun and Bo Li},
booktitle = {IJCAI 2026},
year = {2026}
}