  In barter exchanges agents enter seeking to swap their items for other items
on their wishlist. We consider a centralized barter exchange with a set of
agents and items where each item has a positive value. The goal is to compute a
(re)allocation of items maximizing the agents' collective utility subject to
each agent's total received value being comparable to their total given value.
Many such centralized barter exchanges exist and serve crucial roles; e.g.,
kidney exchange programs, which are often formulated as variants of directed
cycle packing. We show finding a reallocation where each agent's total given
and total received values are equal is NP-hard. On the other hand, we develop a
randomized algorithm that achieves optimal utility in expectation and where, i)
for any agent, with probability 1 their received value is at least their given
value minus $v^*$ where $v^*$ is said agent's most valuable owned and
wished-for item, and ii) each agent's given and received values are equal in
expectation.
