  We study several fairness notions in allocating indivisible chores (i.e.,
items with non-positive values) to agents who have additive and submodular cost
functions. The fairness criteria we are concern with are envy-free up to any
item (EFX), envy-free up to one item (EF1), maximin share (MMS), and pairwise
maximin share (PMMS), which are proposed as relaxations of envy-freeness in the
setting of additive cost functions. For allocations under each fairness
criterion, we establish their approximation guarantee for other fairness
criteria. Under the additive setting, our results show strong connections
between these fairness criteria and, at the same time, reveal intrinsic
differences between goods allocation and chores allocation. However, such
strong relationships cannot be inherited by the submodular setting, under which
PMMS and MMS are no longer relaxations of envy-freeness and, even worse, few
non-trivial guarantees exist. We also investigate efficiency loss under these
fairness constraints and establish their prices of fairness.
