Abstract
The dispatch problems is a critical primitive of ridesharing systems: upon receiving a ride request, the platform must choose a nearby car to serve the ride, while ensuring that it maximizes vehicle availability in the future. The problem has close connections to optimal control of stochastic processing networks, as well as to online stochastic bipartite-matching and the k-server problems. I will talk about some recent work where we developed new state-independent and state-dependent control policies for this problem, with strong approximation guarantees. These results are based on using ideas from product-form Markov chains and large-deviations theory; I will briefly describe these new techniques, and outline some open questions and potential connections with other online decision problems.
Joint work with Daniel Freund and Thodoris Lykouris, and Yash Kanoria and Pengyu Qian.