  Several fairness concepts have been proposed recently in attempts to
approximate envy-freeness in settings with indivisible goods. Among them, the
concept of envy-freeness up to any item (EFX) is arguably the closest to
envy-freeness. Unfortunately, EFX allocations are not known to exist except in
a few special cases. We make significant progress in this direction. We show
that for every instance with additive valuations, there is an EFX allocation of
a subset of items with a Nash welfare that is at least half of the maximum
possible Nash welfare for the original set of items. That is, after donating
some items to a charity, one can distribute the remaining items in a fair way
with high efficiency. This bound is proved to be best possible. Our proof is
constructive and highlights the importance of maximum Nash welfare allocation.
Starting with such an allocation, our algorithm decides which items to donate
and redistributes the initial bundles to the agents, eventually obtaining an
allocation with the claimed efficiency guarantee. The application of our
algorithm to large markets, where the valuations of an agent for every item is
relatively small, yields EFX with almost optimal Nash welfare. To the best of
our knowledge, this is the first use of large market assumptions in the fair
division literature. We also show that our algorithm can be modified to
compute, in polynomial-time, EFX allocations that approximate optimal Nash
welfare within a factor of at most $2\rho$, using a $\rho$-approximate
allocation on input instead of the maximum Nash welfare one.
