  We consider the fundamental problem of allocating a set of indivisible goods
among strategic agents with additive valuation functions. It is well known
that, in the absence of monetary transfers, Pareto efficient and truthful rules
are dictatorial, while there is no deterministic truthful mechanism that
allocates all items and achieves envy-freeness up to one item (EF1), even for
the case of two agents. In this paper, we investigate the interplay of fairness
and efficiency under a relaxation of truthfulness called non-obvious
manipulability (NOM), recently proposed by Troyan and Morrill. We show that
this relaxation allows us to bypass the aforementioned negative results in a
very strong sense. Specifically, we prove that there are deterministic and EF1
algorithms that are not obviously manipulable, and the algorithm that maximizes
utilitarian social welfare (the sum of agents' utilities), which is Pareto
efficient but not dictatorial, is not obviously manipulable for $n \geq 3$
agents (but obviously manipulable for $n=2$ agents). At the same time,
maximizing the egalitarian social welfare (the minimum of agents' utilities) or
the Nash social welfare (the product of agents' utilities) is obviously
manipulable for any number of agents and items. Our main result is an
approximation preserving black-box reduction from the problem of designing EF1
and NOM mechanisms to the problem of designing EF1 algorithms. En route, we
prove an interesting structural result about EF1 allocations, as well as new
"best-of-both-worlds" results (for the problem without incentives), that might
be of independent interest.
