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

DOI10.1007/978-3-030-35389-6_10zbMATH Open1435.91126arXiv1912.00225OpenAlexW2991487268MaRDI QIDQ776248FDOQ776248

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

Publication date: 30 June 2020

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.

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

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

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)

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)