Fair Allocation of Indivisible Chores: Beyond Additive Valuations

In this work, we study the maximin share (MMS) fair allocation of indivisible chores. For additive valuations, Huang and Lu [EC, 2021] designed an algorithm to compute a 11/9-approximate MMS fair allocation, and Feige et al. [WINE, 2021] proved that no algorithm can achieve better than 44/43 approximation. Beyond additive valuations, unlike the allocation of goods, very little is known. We first prove that for submodular valuations, in contrast to the allocation of goods where constant approximations are proved by Barman and Krishnamurthy [TEAC, 2020] and Ghodsi et al [AIJ, 2022], the best possible approximation ratio is n. We then focus on two concrete settings where the valuations are combinatorial. In the first setting, agents need to use bins to pack a set of items where the items may have different sizes to different agents and the agents want to use as few bins as possible to pack the items assigned to her. In the second setting, each agent has a set of machines that can be used to process a set of items, and the objective is to minimize the makespan of processing the items assigned to her. For both settings, we design constant approximation algorithms, and show that if the fairness notion is changed to proportionality up to one/any item, the best approximation ratio is n.