Proceedings

Connected EF1 Allocations Exist in Discrete Chore Cutting

Ankang Sun, Bo Li

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 3532-3540.

https://doi.org/10.24963/ijcai.2026/393

Keywords

  • Game Theory and Economic Paradigms: Fair division
  • Game Theory and Economic Paradigms: Computational social choice

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 upon the powerful Simmons-Su framework, 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. For allocations of goods, existing works have introduced rounding techniques that convert an envy-free fractional division into a connected integral EF1 division for any number of agents with monotone valuations. 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.

Ankang Sun, and Bo Li. 2026. Connected EF1 Allocations Exist in Discrete Chore Cutting. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 3532–3540. https://doi.org/10.24963/ijcai.2026/393
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards