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 |