Tuesday, December 17, 2013 at 4:15pm
Frank H. T. Rhodes Hall, 253
ORIE Colloquium: Vahideh Manshadi (MIT) - Dynamic Matching in Systems with Stochastic Structures
Matching over time is at the heart of the operations of many systems such as kidney exchange, Internet advertising, and public housing. The classic study of matching algorithms is concerned with adversarial models in which the structure of the underlying graph and/or preferences is completely unknown. However, many real-world systems have structures that can be accurately modeled as stochastic processes with certain distributions. Such distributional information can be inferred through data analysis, and it can be exploited to design more efficient matching schemes tailored for the particular application. This motivates us to study stochastic variations of the matching problems such as dynamic matching on random graphs and online stochastic matching.
We consider the kidney exchange market as an example of systems with stochastic structures, and we study the design challenges in the current practice of kidney exchange. Current kidney exchange pools consist of many highly sensitized patients who are very unlikely to find a tissue-type compatible donor. Motivated by clinical data, we develop a dynamic random graph model that captures this sparsity feature. In this market, besides distributional information, we can collect further information by waiting for many incompatible pairs to join the pool before finding a match. In this way, we can increase matching opportunities for patients at the cost of waiting. We analyze an algorithm that periodically finds allocations and we study how the period length, as well as the technology (i.e., short cycles and chains), affects the number of matched patients. We support our theoretical findings with data-driven computational experiments, and our findings lead to policy recommendations.
Based on joint work with Itai Ashlagi and Patrick Jaillet.