Mix and match: Markov chains and mixing times for matching in rideshare

DOI10.1007/978-3-030-35389-6_10MaRDI QIDQ776248zbMATH OpenOpenAlexFDO

Authors John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, Yuhao Wan, Pan Xu, Michael T. Curry

Publication date 30 June 2020

Full work available at URL https://arxiv.org/abs/1912.00225

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Matching models (91B68)

Abstract: Rideshare platforms such as Uber and Lyft dynamically dispatch drivers to match riders' requests. We model the dispatching process in rideshare as a Markov chain that takes into account the geographic mobility of both drivers and riders over time. Prior work explores dispatch policies in the limit of such Markov chains; we characterize when this limit assumption is valid, under a variety of natural dispatch policies. We give explicit bounds on convergence in general, and exact (including constants) convergence rates for special cases. Then, on simulated and real transit data, we show that our bounds characterize convergence rates -- even when the necessary theoretical assumptions are relaxed. Additionally these policies compare well against a standard reinforcement learning algorithm which optimizes for profit without any convergence properties.

Recommendations

• Dynamic matching for real-time ride sharing
• Dynamic and stochastic rematching for ridesharing systems: formulations and reductions
• Dynamic stochastic matching under limited time
• Empty-car routing in ridesharing systems
• Technical note -- Online hypergraph matching with delays

Cites work

• An introduction to MCMC for machine learning
• Equation of state calculations by fast computing machines
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Monte Carlo sampling methods using Markov chains and their applications
• Online matching and ad allocation
• Online spatio-temporal matching in stochastic and dynamic domains
• The Monte Carlo Method

Cited in

(1)

• scientific article; zbMATH DE number 7204578 (Why is no real title available?)

This page was built for publication: Mix and match: Markov chains and mixing times for matching in rideshare

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776248)