Efficient Dynamic Barter Exchange

• 成果类型: Article
• 署名作者: Anderson, Ross; Ashlagi, Itai; Gamarnik, David; Kanoria, Yash
• 署名单位: Alphabet Inc.; Google Incorporated; Stanford University; Massachusetts Institute of Technology (MIT); Columbia University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1644
• 发表日期: 2017
• 页码: 1446-1459
• 关键词: Kidney exchange; MARKET; compatibility; allocation; house

摘要

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.& para;& para;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.