  We consider the problem of implementing an individually rational,
asymptotically Pareto optimal allocation in a barter-exchange economy where
agents are endowed with goods and have preferences over the goods of others,
but may not use money as a medium of exchange. Because one of the most
important instantiations of such economies is kidney exchange -- where the
"input"to the problem consists of sensitive patient medical records -- we ask
to what extent such exchanges can be carried out while providing formal privacy
guarantees to the participants. We show that individually rational allocations
cannot achieve any non-trivial approximation to Pareto optimality if carried
out under the constraint of differential privacy -- or even the relaxation of
\emph{joint} differential privacy, under which it is known that asymptotically
optimal allocations can be computed in two-sided markets, where there is a
distinction between buyers and sellers and we are concerned only with privacy
of the buyers~\citep{Matching}. We therefore consider a further relaxation that
we call \emph{marginal} differential privacy -- which promises, informally,
that the privacy of every agent $i$ is protected from every other agent $j \neq
i$ so long as $j$ does not collude or share allocation information with other
agents. We show that, under marginal differential privacy, it is possible to
compute an individually rational and asymptotically Pareto optimal allocation
in such exchange economies.
