Efficient Dynamic Barter Exchange

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. Funding: The second author acknowledges the research support of the National Science Foundation [Grant SES-1254768]. Supplemental Material: 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
1. Introduction Thousands of incompatible patient-donor pairs enroll at kidney exchange clearinghouses every year around the world in order to swap donors. Kidney exchange is just one example of a [...]