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
Available on ECCH
No
