Efficient Dynamic Barter Exchange

Ross Anderson (), Itai Ashlagi (), David Gamarnik () and Yash Kanoria ()
Additional contact information
Ross Anderson: Google, Mountain View, California 94043
Itai Ashlagi: Management Science and Engineering, Stanford University, Stanford, California 94305
David Gamarnik: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Yash Kanoria: Decision, Risk and Operations Division, Columbia Business School, New York, New York 10027

Operations Research, 2017, vol. 65, issue 6, 1446-1459

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.

Keywords: barter; matching; market design; random graphs; dynamics; kidney exchange; platform; control policy (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
https://doi.org/10.1287/opre.2017.1644 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:65:y:2017:i:6:p:1446-1459

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().