New Algorithms for the Fair and Efficient Allocation of Indivisible Chores

Discrete fair division has recently received significant attention due to its applications in a wide variety of multi-agent settings; see recent surveys [2, 27, 4]. Given a set of indivisible items and a set of n agents with diverse preferences, the goal is to find an allocation that is fair (i.e., acceptable by all agents) and efficient (i.e., non-wasteful). We assume that agents have additive valuations. The standard economic efficiency notion is Pareto-optimality (PO) and its strengthening fractional Pareto-optimality (fPO). Fairness notions based on envy [15] are most popular, where an allocation is said to be envy-free (EF) if every agent weakly prefers her bundle to any other agent's bundle. Since EF allocations need not exist (e.g., dividing one item among two agents), its relaxations envy-free up to any item (EFX) [10] and envy-free up to one item (EF1) [23, 9] are most widely used, where EF EFX EF1.