Dynamic Stochastic Matching Under Limited Time

Ali Aouad () and Ömer Sarıtaç ()
Additional contact information
Ali Aouad: Management Science and Operations, London Business School Regent’s Park, London NW1 4SA, United Kingdom
Ömer Sarıtaç: Management Science and Operations, London Business School Regent’s Park, London NW1 4SA, United Kingdom

Operations Research, 2022, vol. 70, issue 4, 2349-2383

Abstract: In centralized matching markets such as carpooling platforms and kidney exchange schemes, new participants constantly enter the market and remain available for potential matches during a limited period of time. To reach an efficient allocation, the “timing” of the matching decisions is a critical aspect of the platform’s operations. There is a fundamental tradeoff between increasing market thickness and mitigating the risk that participants abandon the market. Nonetheless, the dynamic properties of matching markets have been mostly overlooked in the algorithmic literature. In this paper, we introduce a general dynamic matching model over edge-weighted graphs, where the agents’ arrivals and abandonments are stochastic and heterogeneous. Our main contribution is to design simple matching algorithms that admit strong worst-case performance guarantees for a broad class of graphs. In contrast, we show that the performance of widely used batching algorithms can be arbitrarily bad on certain graph-theoretic structures motivated by carpooling services. Our approach involves the development of a host of new techniques, including linear programming benchmarks, value function approximations, and proxies for continuous-time Markov chains, which may be of broader interest. In extensive experiments, we simulate the matching operations of a car-pooling platform using real-world taxi demand data. The newly developed algorithms can significantly improve cost efficiency against batching algorithms.

Keywords: Market Analytics and Revenue Management; dynamic matching; approximation algorithms; Markov decision processes; car-pooling (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2293 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:4:p:2349-2383

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().