Dynamic stochastic matching under limited time

Aouad, A and Saritac, O (2020) Dynamic stochastic matching under limited time. [Conference proceeding]


Motivated by centralized matching markets, we study an online stochastic matching problem on edge-weighted graphs, where the agents' arrivals and abandonments are stochastic and heterogeneous. The problem is formulated as a continuous-time Markov decision process (MDP) under the average-cost criterion. While the MDP is computationally intractable, we design simple matching algorithms that achieve constant-factor approximations in cost-minimization and reward-maximization settings. Specifically, we devise a 3-approximation algorithm for cost minimization on graphs satisfying a metric-like property. We develop a (e-1)/(2e)-approximation algorithm for reward maximization on arbitrary bipartite graphs. Our algorithms possess a greedily-like structure informed by fluid relaxations. In extensive experiments, we simulate the matching operations of a car-pooling platform using real-world taxi demand data. The newly-developed algorithms have the potential to significantly improve cost efficiency in certain market conditions against the widely used batching algorithms.

More Details

Item Type: Conference proceeding
Subject Areas: Management Science and Operations
Additional Information:

© 2020 ACM Inc.

Date Deposited: 04 May 2021 09:59
Subjects: Algorithms
Last Modified: 23 Apr 2024 00:43
URI: https://lbsresearch.london.edu/id/eprint/1477

Export and Share


Full text not available from this repository.


View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item