Efficient Dynamic Barter Exchange
Ross Anderson, Itai Ashlagi, David Gamarnik, Yash Kanoria
Operations Research · 2017 · Volume 65 · Issue 6
Abstract
We study dynamic matching policies in a stochastic marketplace for barter, with agents arriving over time. Each agent is endowed with an item and is interested in an item possessed by another agent homogeneously with probability p , independently for all pairs of agents. Three settings are considered with respect to the types of allowed exchanges: (a) only two-way cycles, in which two agents swap items, (b) two-way or three-way cycles, (c) (unbounded) chains initiated by an agent who provides an item but expects nothing in return. We consider the average waiting time as a measure of efficiency and find that the cost outweighs the benefit from waiting to thicken the market. In particular, in each of the above settings, a policy that conducts exchanges in a greedy fashion is near optimal. Further, for small p , we find that allowing three-way cycles greatly reduces the waiting time over just two-way cycles, and conducting exchanges through a chain further reduces the waiting time significantly. Thus, a centralized planner can achieve the smallest waiting times by using a greedy policy, and by facilitating three-way cycles and chains, if possible. The online appendix is available at https://doi.org/10.1287/opre.2017.1644 .
Keywords
barter, matching, market design, random graphs, dynamics, kidney exchange, platform, control policy
Enable JavaScript for citation tools and additional paper interactions.