Research Article
Competing Dynamic Matching Markets
@INPROCEEDINGS{10.4108/eai.8-8-2015.2260742, author={Sanmay Das and John Dickerson and Zhuoshu Li and Tuomas Sandholm}, title={Competing Dynamic Matching Markets}, proceedings={The Third Conference on Auctions, Market Mechanisms and Their Applications}, publisher={ACM}, proceedings_a={AMMA}, year={2015}, month={8}, keywords={matching markets dynamic matching greedy matching trade frequency kidney exchange}, doi={10.4108/eai.8-8-2015.2260742} }
- Sanmay Das
John Dickerson
Zhuoshu Li
Tuomas Sandholm
Year: 2015
Competing Dynamic Matching Markets
AMMA
ICST
DOI: 10.4108/eai.8-8-2015.2260742
Abstract
While dynamic matching markets are usually modeled in isolation, assuming that every agent to be matched enters that market, in many real-world settings there exist rival matching markets with overlapping pools of agents. We extend a framework of dynamic matching due to Akbarpour et al. [2014] to characterize outcomes in cases where two such rival matching markets compete with each other. One market matches quickly while the other builds market thickness by matching slowly. We give an analytic bound on the loss---the expected fraction of unmatched vertices---of this two-market environment relative to one in which all agents enter either one market or the other, and numerically quantify its exact loss, demonstrating that rival markets increase overall loss compared to a single market that builds thickness. We then look at two competing kidney exchanges, where patients with end-stage renal failure swap willing but incompatible donors, and show that matching with rival barter exchanges performs qualitatively the same as matching with rival matching markets---that is, rival markets increase global loss.