A famous result in the study of fair division is that it is possible to assign goods to agents such that the allocation is (a) Pareto-optimal (no allocation is better for everyone) and (b) envy-free (either exactly for divisible goods or up to one good for indivisible goods). Moreover, efficient algorithms exist to compute these allocations. A related open problem is to do the same for chores, i.e. goods which have negative utility. In this talk we will see the first non-trivial algorithmic result for fair division of chores, the computation of envy-free, Pareto-optimal chore allocations under bivalued utilities.
(Based on recent work by Jugal Garg, Aniket Murhekar, John Qin from AAAI 2022)