The Third Conference on Auctions, Market Mechanisms and Their Applications

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
Sanmay Das1, John Dickerson2,*, Zhuoshu Li1, Tuomas Sandholm2
  • 1: Washington University in St. Louis
  • 2: CMU
*Contact email: dickerson@cs.cmu.edu

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.