  We study the mechanism design problem of allocating a set of indivisible
items without monetary transfers. Despite the vast literature on this very
standard model, it still remains unclear how do truthful mechanisms look like.
We focus on the case of two players with additive valuation functions and our
purpose is twofold. First, our main result provides a complete characterization
of truthful mechanisms that allocate all the items to the players. Our
characterization reveals an interesting structure underlying all truthful
mechanisms, showing that they can be decomposed into two components: a
selection part where players pick their best subset among prespecified choices
determined by the mechanism, and an exchange part where players are offered the
chance to exchange certain subsets if it is favorable to do so. In the
remaining paper, we apply our main result and derive several consequences on
the design of mechanisms with fairness guarantees. We consider various notions
of fairness, (indicatively, maximin share guarantees and envy-freeness up to
one item) and provide tight bounds for their approximability. Our work settles
some of the open problems in this agenda, and we conclude by discussing
possible extensions to more players.
