The Rideshare Dispatch Problem (Aka Online Bipartite Matching with Supply Externalities)
summary
Model has n stations, K identical cars, Poisson origin-destination arrivals and zero trip times; objective is long-run miss rate when supply can be pulled for free along a bipartite compatibility graph (supply externalities). A state-independent policy from an elevated flow relaxation is computable and guarantees performance within 1 + n/K (order 1/√K with travel times); a family of scaled max-weight state-dependent policies—weights found by a convex program—achieves optimal exponential decay of drop probability under a strict Hall condition; proofs use large deviations and Lyapunov methods and include matching converses.
AI-written summary · about
chapters (12)
- 0:00Intro
- 1:42the dispatch problem
- 2:26(stochastic) model for ridesharing
- 8:07intermezzo the many schools of modeling
- 10:53intermezzo the joy of theory
- 12:04formal problem
- 14:40what can we show
- 20:31alternate view: walking in the simplex
- 22:17complete resource pooling (strong Hall's condition)
- 23:57the MaxWeight policy
- 25:57main result: achievability
- 27:25implications of our results
related talks
01h 38mRidesharing
44mComputational Complexity of Matching in Ride Sharing
41mDynamic Pricing in Ride-Sharing Platforms
53mCarpooling and the Economics of Self-Driving Cars
43mRebalancing in Bike-Sharing Systems – Incentives and Other Stories
50mDiversity in Matching Markets
44mFacilitating the Search for Partners on Matching Platforms
44mOnline Advertisements and Online Algorithms