Matching in Dynamic Imbalanced Markets

Itai Ashlagi, Stanford University, Afshin Nikzad, University of Southern California, Philipp Strack, Yale University

We study dynamic matching in exchange markets with easy- and hard-to-match agents. A greedy policy, which attempts to match agents upon arrival, ignores the positive externality that waiting agents provide by facilitating future matchings. We prove that the trade-off between a “thicker” market and faster matching vanishes in large markets; the greedy policy leads to shorter waiting times and more agents matched than any other policy. We empirically confirm these findings in data from the National Kidney Registry. Greedy matching achieves as many transplants as commonly-used policies (1.8% more than monthly batching), and shorter waiting times (16 days faster than monthly batching).