  We consider the problem of allocating indivisible objects to agents when
agents have strict preferences over objects. There are inherent trade-offs
between competing notions of efficiency, fairness and incentives in assignment
mechanisms. It is, therefore, natural to consider mechanisms that satisfy two
of these three properties in their strongest notions, while trying to improve
on the third dimension. In this paper, we are motivated by the following
question: Is there a strategy-proof and envy-free random assignment mechanism
more efficient than equal division?
  Our contributions in this paper are twofold. First, we further explore the
incompatibility between efficiency and envy-freeness in the class of
strategy-proof mechanisms. We define a new notion of efficiency that is weaker
than ex-post efficiency and prove that any strategy-proof and envy-free
mechanism must sacrifice efficiency even in this very weak sense. Next, we
introduce a new family of mechanisms called Pairwise Exchange mechanisms and
make the surprising observation that strategy-proofness is equivalent to
envy-freeness within this class. We characterize the set of all neutral and
strategy-proof (and hence, also envy-free) mechanisms in this family and show
that they admit a very simple linear representation.
