Dynamic stochastic matching under limited time

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

Abstract

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: 10 Sep 2024 00:47
URI: https://lbsresearch.london.edu/id/eprint/1477
More

Export and Share


Download

Full text not available from this repository.

Statistics

Altmetrics
View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item