Papers for

task scheduling teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Connected fair divisions exist for shared chores among any agents

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, 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.

Sat 26 SeptComputer Science and Game Theory

The gist

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.

Open → 2609.32545v1