  A major open question in fair allocation of indivisible items is whether
there always exists an allocation of chores that is Pareto optimal (PO) and
envy-free up to one item (EF1). We answer this question affirmatively for the
natural class of bivalued utilities, where each agent partitions the chores
into easy and difficult ones, and has cost $p > 1$ for chores that are
difficult for her and cost $1$ for chores that are easy for her. Such an
allocation can be found in polynomial time using an algorithm based on the
Fisher market.
  We also show that for a slightly broader class of utilities, where each agent
$i$ can have a potentially different integer $p_i$, an allocation that is
maximin share fair (MMS) always exists and can be computed in polynomial time,
provided that each $p_i$ is an integer. Our MMS arguments also hold when
allocating goods instead of chores, and extend to another natural class of
utilities, namely weakly lexicographic utilities.
