  Fair distribution of indivisible tasks with non-positive valuations (aka
chores) has given rise to a large body of work in recent years. A popular
approximate fairness notion is envy-freeness up to one item (EF1), which
requires that any pairwise envy can be eliminated by the removal of a single
item. While an EF1 and Pareto optimal (PO) allocation of goods always exists
and can be computed via several well-known algorithms, even the existence of
such solutions for chores remains open, to date. We take an epistemic approach
utilizing information asymmetry by introducing dubious chores -- items that
inflict no cost on receiving agents, but are perceived costly by others. On a
technical level, dubious chores provide a more fine-grained approximation of
envy-freeness -- compared to relaxations such as EF1 -- which enables progress
towards addressing open problems on the existence and computation of EF1 and
PO. In particular, we show that finding allocations with optimal number of
dubious chores is computationally hard even for highly restricted classes of
valuations. Nonetheless, we prove the existence of envy-free and PO allocations
for $n$ agents with only $2n-2$ dubious chores and strengthen it to $n-1$
dubious chores in four special classes of valuations. Our experimental analysis
demonstrate that baseline algorithms only require a relatively small number of
dubious chores to achieve envy-freeness in practice.
