Mix and Match: Markov Chains and Mixing Times for Matching in Rideshare

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationWeb and Internet Economics - 15th International Conference, WINE 2019, Proceedings
EditorsIoannis Caragiannis, Vahab Mirrokni, Evdokia Nikolova
PublisherSpringer
Pages129-141
Number of pages13
ISBN (Print)9783030353889
DOIs
StatePublished - 2019
Event15th Conference on Web and Internet Economics, WINE 2019 - New York City, United States
Duration: Dec 10 2019Dec 12 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11920 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Conference on Web and Internet Economics, WINE 2019
Country/TerritoryUnited States
CityNew York City
Period12/10/1912/12/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Mix and Match: Markov Chains and Mixing Times for Matching in Rideshare'. Together they form a unique fingerprint.

Cite this