  We study the problem of allocating a group of indivisible chores among agents
while each chore has a binary marginal. We focus on the fairness criteria of
envy-freeness up to any item (EFX) and investigate the existence of EFX
allocations. We show that when agents have additive binary cost functions,
there exist EFX and Pareto-optimal (PO) allocations that can be computed in
polynomial time. To the best of our knowledge, this is the first setting of a
general number of agents that admits EFX and PO allocations, before which EFX
and PO allocations have only been shown to exist for three bivalued agents. We
further consider more general cost functions: cancelable and general monotone
(both with binary marginal). We show that EFX allocations exist and can be
computed for binary cancelable chores, but EFX is incompatible with PO. For
general binary marginal functions, we propose an algorithm that computes
(partial) envy-free (EF) allocations with at most $n-1$ unallocated items.
