A dynamic model of barter exchange

We consider the problem of efficient operation of a barter exchange platform for indivisible goods. We introduce a dynamic model of barter exchange where in each period one agent arrives with a single item she wants to exchange for a different item. We study a homogeneous and stochastic environment: an agent is interested in the item possessed by another agent with probability p, independently for all pairs of agents. We consider three settings with respect to the types of allowed exchanges: a) Only two-way cycles, in which two agents swap their items, b) Two or three-way cycles, c) (unbounded) chains initiated by altruistic donors who provide an item but expect nothing in return. The goal of the platform is to minimize the average waiting time of an agent. Somewhat surprisingly, we find that in each of these settings, a policy that conducts exchanges in a greedy fashion is near optimal, among a large class of policies that includes batching policies. Further, we find that for small p, allowing three-cycles can greatly improve the waiting time over the two-cycles only setting, and the presence of altruistic donors can lead to a further large improvement in average waiting time. Specifically, we find that a greedy policy achieves an average waiting time of Θ(1/p2) in setting a), Θ(1/p3/2) in setting b), and Θ(1/p) in setting c). Thus, a platform can achieve the smallest waiting times by using a greedy policy, and by facilitating three cycles and chains, if possible. Our findings are consistent with empirical and computational observations which compare batching policies in the context of kidney exchange programs