  We study the problem of allocating indivisible items to budget-constrained
agents, aiming to provide fairness and efficiency guarantees. Specifically, our
goal is to ensure that the resulting allocation is envy-free up to any item
(EFx) while minimizing the amount of inefficiency that this needs to introduce.
We first show that there exist two-agent problem instances for which no EFx
allocation is Pareto efficient. We, therefore, turn to approximation and use
the Nash social welfare maximizing allocation as a benchmark. For two-agent
instances, we provide a procedure that always returns an EFx allocation while
achieving the best possible approximation of the optimal Nash social welfare
that EFx allocations can achieve. For the more complicated case of three-agent
instances, we provide a procedure that guarantees EFx, while achieving a
constant approximation of the optimal Nash social welfare for any number of
items.
