Fair Interval Scheduling of Indivisible Chores
<|reference_start|>Fair Interval Scheduling of Indivisible Chores: We study the problem of fairly assigning a set of discrete tasks (or chores) among a set of agents with additive valuations. Each chore is associated with a start and finish time, and each agent can perform at most one chore at any given time. The goal is to find a fair and efficient schedule of the chores, where fairness pertains to satisfying envy-freeness up to one chore (EF1) and efficiency pertains to maximality (i.e., no unallocated chore can be feasibly assigned to any agent). Our main result is a polynomial-time algorithm for computing an EF1 and maximal schedule for two agents under monotone valuations when the conflict constraints constitute an arbitrary interval graph. The algorithm uses a coloring technique in interval graphs that may be of independent interest. For an arbitrary number of agents, we provide an algorithm for finding a fair schedule under identical dichotomous valuations when the constraints constitute a path graph. We also show that stronger fairness and efficiency properties, including envy-freeness up to any chore (EFX) along with maximality and EF1 along with Pareto optimality, cannot be achieved.<|reference_end|>
@article{equbal2024fair,
    title={Fair Interval Scheduling of Indivisible Chores},
    author={Sarfaraz Equbal, Rohit Gurjar, Yatharth Kumar, Swaprava Nath, Rohit
  Vaish},
    journal={arXiv preprint arXiv:2402.04353},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.04353},
    primaryClass={cs.GT}
}