Connected EF1 Allocations Exist in Discrete Chore Cutting

摘要

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.