Connected fair divisions exist for shared chores among any agents
Connected EF1 Allocations Exist in Discrete Chore Cutting
Computer Science and Game Theory
Summary
Deciding who does which chores fairly is a real challenge, especially when chores can't be split up nicely. This paper shows that it's always possible to divide chores so that everyone feels their share is almost fair, even if the chores are connected and indivisible. The researchers adapted methods that worked for sharing goods to now work for chores, overcoming tricky differences in how fairness is defined for chores versus goods. This means fair chore divisions can be guaranteed for any number of people.
What this means in practice
- •For resource allocation planners: Design chore assignment protocols ensuring near-fair shares for agents with indivisible connected tasks.
- •For task scheduling teams: Develop scheduling methods to assign connected chores fairly while keeping each person's load manageable.
A theory result. No direct application yet.
Authors
Ankang Sun, Bo Li
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, 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. [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 [2023] to accommodate any number of agents. However, these rounding techniques for goods do not directly apply to chores because the definitions of EF1 differ in the two settings. To overcome this asymmetry, we modify the existing rounding techniques and show that connected EF1 divisions exist for a discrete chore.