Mix and Match: Markov Chains & Mixing Times for Matching in Rideshare
This work addresses the reliability of dispatch models for rideshare platforms like Uber and Lyft, offering incremental improvements in convergence analysis for existing policies.
The paper tackles the problem of validating the limit assumption in Markov chain models for rideshare dispatch policies by characterizing convergence conditions and providing explicit bounds on mixing times. It demonstrates that these bounds hold on simulated and real data, even with relaxed assumptions, and shows the policies perform competitively against a profit-optimizing reinforcement learning algorithm.
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.