Skip to main content

Please enter a keyword and click the arrow to search the site

Dynamic Stochastic Matching Under Limited Time


Management Science and Operations

Publishing details

Social Sciences Research Network

Authors / Editors

Aouad A;Saritac O


Publication Year



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.


Dynamic Matching; Approximation Algorithms; Markov Decision Processes


Social Sciences Research Network

Available on ECCH


Select up to 4 programmes to compare

Select one more to compare
subscribe_image_desktop 5949B9BFE33243D782D1C7A17E3345D0

Sign up to receive our latest news and business thinking direct to your inbox


Sign up to receive our latest course information and business thinking

Leave your details above if you would like to receive emails containing the latest thought leadership, invitations to events and news about courses that could enhance your career. If you would prefer not to receive our emails, you can still access the case study by clicking the button below. You can opt-out of receiving our emails at any time by visiting: or by unsubscribing through the link provided in our emails. View our Privacy Policy for more information on your rights.