  Envy-freeness up to any good (EFX) provides a strong and intuitive guarantee
of fairness in the allocation of indivisible goods. But whether such
allocations always exist or whether they can be efficiently computed remains an
important open question. We study the existence and computation of EFX in
conjunction with various other economic properties under lexicographic
preferences--a well-studied preference model in artificial intelligence and
economics. In sharp contrast to the known results for additive valuations, we
not only prove the existence of EFX and Pareto optimal allocations, but in fact
provide an algorithmic characterization of these two properties. We also
characterize the mechanisms that are, in addition, strategyproof, non-bossy,
and neutral. When the efficiency notion is strengthened to rank-maximality, we
obtain non-existence and computational hardness results, and show that
tractability can be restored when EFX is relaxed to another well-studied
fairness notion called maximin share guarantee (MMS).
