Technical Note—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. Existing results show 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-O\left(1/\sqrt{K}\right)$ 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+\mathrm{\Lambda }/\mu )$, where Λ is the total demand (sum of all trip requests) rate and $1/\mu$ is the average trip travel time, implying a convergence rate that is at least of order $1-O\left(1/K\right)$ in the number of vehicles for fixed $\mathrm{\Lambda }/\mu$. The same recursive relationship can be used to obtain a bound that is independent of $\mathrm{\Lambda }/\mu$ and that is tighter than previous bounds, implying a convergence rate that is at least of order $1-O\left(1/\sqrt{K}\right)$. 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 with a performance that can be significantly higher.

Funding: This work was supported by the National Science Foundation [Grant SCC-1831140].