Barter Exchange with Asymmetric Item Valuations

Agents enter barter exchanges to swap items they have for items they want. We study Barter Exchange with Asymmetric Valuations (BAV), a centralized barter exchange where each agent has an individual valuation over items. Given a reallocation of items, let an agent's profit be their received value minus their value given away, according to said agent's valuation of items. The goal of the clearinghouse (the party facilitating the exchange) is to output a reallocation of items that maximizes welfare (sum of agent profits) subject to each agent receiving non-negative profit. BAV is a natural extension of the barter exchange model studied in (Luque et al., WWW '24), which assumes agents necessarily agree on item values. We prove BAV is strongly NP-hard and design a polynomial-time randomized algorithm with optimal expected welfare, non-negative expected profit for every agent, and that, with probability 1, every agent is at most the value of two items away from positive profit. Since valuations may be private and revealed by self-interested agents, we also study BAV from a mechanism design lens.