Pricing in On-Demand (and One-Way) Vehicle Sharing Networks

We consider the dynamic pricing problem that arises in the context of an on-demand vehicle sharing system with one-way trips. Waserhole and Jost (2016) and Banerjee et al. (2021) studied recently the effectiveness of static pricing policies. In particular, they showed that a static pricing policy that arises from solving a maximum flow relaxation of the problem guarantees a performance ratio that is bounded by K/(N + K - 1) when travel times are negligible and by (1 - 2 ( ln(K) / K )^(1/2) )( (Kln(K))^(1/2)/ ((Kln(K))^(1/2) + N - 1) - 3/(Kln(K))^(1/2) ) otherwise, where K is the number of vehicles and N is the number of locations. In this paper, we build on these results by providing an alternative approach to bounding the performance of static pricing policies. Our approach is startlingly simple, producing, upon the application of a well-known recursive relationship that relates system availability in a system with K vehicles to one with K-1 vehicles, a sequence of bounds that are increasingly tight. The worst of these bounds is given by K/(N + K - 1 + Λ/μ), where Λ is the total demand (sum of all trip requests) rate and 1/μ is the average trip travel time, implying a convergence rate that is at least of order 1- O(1/K) in the number of vehicles for fixed Λ/μ. The same recursive relationship can be used to obtain a bound that is independent of Λ/μ given by 1 - ( ( ((N-1) / (2K) + 1/(2(N+K)) + 1)^2 - 1 )^(1/2) - ( (N-1) / (2K) + 1/(2(N+K)) ) ), implying a convergence rate that is at least of order 1 - O(1/K^(1/2)). The approach also yields a parameterized family of static pricing policies that are asymptotically optimal and that generalize static pricing policies previously proposed in the literature. Moreover, the best static pricing policy this approach produces is optimal among those that require a demand balance constraint (e.g., as in Waserhole and Jost (2016) and Banerjee et al. (2021)) with a performance that can be significantly higher