Tight Guarantees for Static Policies in Vehicle Sharing Networks
Abstract
We study pricing in a vehicle sharing network with N locations and C vehicles, motivated by on-demand bike, scooter, and car sharing, as well as robotaxi and ride sharing services. Customers request directed trips between locations, with travel times following general distributions, and leave without service if no vehicle is available. Pricing affects both demand for trips and the distribution of vehicles across locations. Computing an optimal dynamic pricing policy is challenging because the system state depends on the number of vehicles available at each location and in transit (including how long they have been traveling), motivating the use of simple static policies that offer a fixed price for each trip. For any number of vehicles and locations, we establish a tight performance guarantee for static pricing relative to optimal dynamic pricing. The guarantee holds for any concave objective functions (including revenue rate) and general travel time distributions. Our tight guarantee is bounded below by $ \frac{C}{C + \min \{ C -1, \sqrt{ CN} \} }$ (over 50%), achieving the first universal, non-asymptotic constant factor guarantee. We also prove that the optimal static policy can be efficiently computed by solving a convex optimization problem. Finally, we extend our performance guarantee to the setting with supply redirection.
Related
- Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies
- Quasi-Static Fault-Tolerant Feedback Control of a Quadrotor under Rotor Failure with Provable Safety Guarantees
- Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees
- HideOut - User Protection Against Localization with Throughput Guarantees in Mobile Networks
- The role of locality and weight sharing in convolutional neural networks
BibTeX
@misc{elmachtoub2026tight,
title = {{Tight Guarantees for Static Policies in Vehicle Sharing Networks}},
author = {Adam N. Elmachtoub and Jiaqi Shi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13089},
eprint = {2610.13089},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13089},
}
RIS
TY - UNPB
TI - Tight Guarantees for Static Policies in Vehicle Sharing Networks
AU - Adam N. Elmachtoub
AU - Jiaqi Shi
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13089
UR - https://arxiv.org/abs/2610.13089
AB - We study pricing in a vehicle sharing network with N locations and C vehicles, motivated by on-demand bike, scooter, and car sharing, as well as robotaxi and ride sharing services. Customers request directed trips between locations, with travel times following general distributions, and leave without service if no vehicle is available. Pricing affects both demand for trips and the distribution of vehicles across locations. Computing an optimal dynamic pricing policy is challenging because the system state depends on the number of vehicles available at each location and in transit (including how long they have been traveling), motivating the use of simple static policies that offer a fixed price for each trip. For any number of vehicles and locations, we establish a tight performance guarantee for static pricing relative to optimal dynamic pricing. The guarantee holds for any concave objective functions (including revenue rate) and general travel time distributions. Our tight guarantee is bounded below by $ \frac{C}{C + \min \{ C -1, \sqrt{ CN} \} }$ (over 50%), achieving the first universal, non-asymptotic constant factor guarantee. We also prove that the optimal static policy can be efficiently computed by solving a convex optimization problem. Finally, we extend our performance guarantee to the setting with supply redirection.
ER -