  We study the fair allocation of mixtures of indivisible goods and chores
under lexicographic preferences$\unicode{x2014}$a subdomain of additive
preferences. A prominent fairness notion for allocating indivisible items is
envy-freeness up to any item (EFX). Yet, its existence and computation has
remained a notable open problem. By identifying a class of instances with
"terrible chores", we show that determining the existence of an EFX allocation
is NP-complete. This result immediately implies the intractability of EFX under
additive preferences. Nonetheless, we propose a natural subclass of
lexicographic preferences for which an EFX and Pareto optimal (PO) allocation
is guaranteed to exist and can be computed efficiently for any mixed instance.
Focusing on two weaker fairness notions, we investigate finding EF1 and PO
allocations for special instances with terrible chores, and show that MMS and
PO allocations can be computed efficiently for any mixed instance with
lexicographic preferences.

Computer Science and Game Theory