Dynamic Stochastic Matching Under Limited Time

Subject

Management Science and Operations

Publishing details

Social Sciences Research Network

Authors / Editors

Aouad A; Saritac O

Biographies

Publication Year

2019

Abstract

In centralized matching markets, such as kidney exchange schemes, car-pooling platforms and public housing programs, new participants constantly enter the market and remain available for potential matches during a limited period. To reach an efficient allocation, the "time'" dimension is a critical parameter of the platform's matching decisions. There is a fundamental trade-off between increasing market thickness and mitigating the risk that some participants abandon the market. Such dynamic properties of matching markets have been mostly overlooked in the classic algorithmic literature. In this paper, we introduce a dynamic matching model that captures nuanced arrival and abandonment patterns. Specifically, we study an online stochastic matching problem on a broad class of graph-theoretic structures, where the agents' arrivals and abandonments are stochastic and heterogeneous. While the resulting Markov decision process is computationally intractable, we design simple matching policies that can be rigorously analyzed. We devise polynomial-time constant-factor approximations in both cost-minimization and reward-maximization settings. The matching algorithms are decentralized and possess a simple greedily-like structure. We derive generalizable insights that can inform the design of matching platforms in practice.

Keywords

Dynamic Matching; Approximation Algorithms; Markov Decision Processes

Series

Social Sciences Research Network