  We study the chore division problem where a set of agents needs to divide a
set of chores (bads) among themselves fairly and efficiently. We assume that
agents have linear disutility (cost) functions. Like for the case of goods,
competitive division is known to be arguably the best mechanism for the bads as
well. However, unlike goods, there are multiple competitive divisions with very
different disutility value profiles in bads. Although all competitive divisions
satisfy the standard notions of fairness and efficiency, some divisions are
significantly fairer and efficient than the others. This raises two important
natural questions: Does there exist a competitive division in which no agent is
assigned a chore that she hugely dislikes? Are there simple sufficient
conditions for the existence and polynomial-time algorithms assuming them?
  We investigate both these questions in this paper. We show that the first
problem is strongly NP-hard. Further, we derive a simple sufficient condition
for the existence, and we show that finding a competitive division is PPAD-hard
assuming the condition. These results are in sharp contrast to the case of
goods where both problems are strongly polynomial-time solvable. To the best of
our knowledge, these are the first hardness results for the chore division
problem, and, in fact, for any economic model under linear preferences.
