Fair share allocation of indivisible chores

Abstract

Since initiated by Steinhaus at a meeting in Washington D.C. [Economet­rica, 1948], fair allocation has been broadly studied in the fields of economics, mathematics and computer science. A substantial body of works aimed at understanding the theory of fairly allocating a set of items to a set of agents have appeared consequently. In this thesis, we study the problem of fairly allocating m indivisible chores (i.e., undesired items with non-negative disu­tilities) to n agents, with particular focus on share-based fairness notions, where agents evaluate the fairness of an allocation by comparing their re­ceived disutilities with a benchmark share - a function only of her own disu­tility function and the number of agents. This share is called a guarantee if for any profile of disutility functions there is an allocation where every agent receives disutility no more than her own share. We first consider the notion of MaxMinShare (MMS) proposed by Budish [J. Political Econ., 2011] for indivisible goods (i.e., desired items with non-negative utilities). For indivisible chores, this notion becomes MinMaxShare, which is also abbreciated to MMS for consistency. In the literature, the majority of effort on finding MMS fair allocations for chores is devoted to additive disutility funtions; however, beyond additivity, very little is known. We prove that no algorithm can ensure better than min{n, log m/log log m} approxi­mation if the disutility functions are submodular. This result shows a sharp contrast to the allocation of goods where constant approximations exist as shown by Barman and Krishnamurthy [TEAC, 2020] and Ghodsi et al. [AIJ, 2022]. We then prove that for subadditive disutilities, there always exists an allocation that is min{n,"log m"}-approximation, and thus the approxi­mation ratio is asymptotically tight. Besides multiplicative approximation, we also consider the ordinal relaxation, 1-out-of-d MMS, which was recently proposed by Hosseini et al. [JAIR and AAMAS, 2022]. Our result implies that for any d ≥ 2, a 1-out-of-d MMS allocation may not exist. Due to these hardness results in the general subadditive setting, we study two specific problems, namely, job scheduling and bin packing. For both problems, we show that constant approximate allocations always exist for both multiplica­tive and ordinal relaxations of MMS. Since exact MMS fairness cannot be guaranteed as shown by Feige etal. [WINE, 2021], we turn to another share-based notion proposed by Hill [Ann. Probab., 1987], which is the worst-case MaxMinShare over all utility functions with the same largest possible single-item utility. Although Hill's share is more conservative than the MaxMinShare, it can always be guar­anteed and its computation is elementary, unlike that of the MaxMinShare which involves solving an NP-hard problem. We apply Hill's approach to the allocation of indivisible chores, and characterise the tight closed form of the worst-case MinMaxShare for a given disutility of the worst chore. We argue that Hill's share for allocating chores is effective in the sense of being close to the original MinMaxShare value, and there is much to learn about the guarantee an agent can be offered from the disutility of her worst single chore. Furthermore, we prove that the monotonic cover of Hill's share is the best guarantee that can be achieved in Hill's model for all allocation instances.