Dynamic Stochastic Matching Under Limited Time

Aouad, A and Saritac, O (2022) Dynamic Stochastic Matching Under Limited Time. Operations Research, 70 (4). pp. 2349-2383. ISSN 0030-364X OPEN ACCESS

Abstract

In centralized matching markets such as car-pooling 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 trade-off 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 car-pooling 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.

More Details

Item Type: Article
Subject Areas: Management Science and Operations
Date Deposited: 13 Jun 2022 12:06
Date of first compliant deposit: 04 Mar 2022
Subjects: Management science
Last Modified: 24 Sep 2022 06:18
URI: https://lbsresearch.london.edu/id/eprint/2475
More

Export and Share


Download

Accepted Version - Text

Statistics

Altmetrics
View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item