Dynamic matching algorithms

We study marketplaces in which participants arrive over time, looking to interact with each other. While such interactions have historically been decentralized, the past few years have seen a dramatic increase in the number of internet-enabled platforms which facilitate the process of connecting together, or matching, sets of two or more participants. We will focus mainly on centralized matching markets such as kidney exchange and carpooling platforms. In such platforms, the algorithm which determines whom to match and when to do so plays an important role in the efficiency of the marketplace. In the first part, we study the interface between the participant heterogeneity, the types of matchings that are allowed, and the frequency at which the platform computes the allocations. We provide an empirical analysis of the effect of match frequency based on data from major US Kidney exchange programs. We then study models that enable us to compare the participants' match rates and waiting times under varying matching policies. We show both in theory and in practice that matching quickly can be beneficial, compared to policies which try to increase opportunities for optimization through artificial waiting. Until now, the theory of matching algorithms has focused mostly on static environments and little is known in the case where all participants arrive and depart dynamically. In our second part, we help bridge this gap by introducing a new theoretical problem for dynamic matching when anyone can arrive online. We provide new algorithms with state-of-the-art theoretical guarantees, both in the case of adversarial and random order inputs. Finally, we show that these algorithms perform well on kidney exchange and carpooling data.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Burq, Maximilien.

Advisor dc:contributor.advisor

• Itai Ashlagi and Patrick Jaillet.

• Operations Research Center.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/121713

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/121713