An Improved Mechanism for Pricing Ride-Hailing Fares

Abstract

Pricing strategies in ride-hailing platforms present complex optimization challenges, attracting considerable research attention in computer science. Hikima et al. (AAAI 2021) introduced a model for this problem and achieved a $1/3$-approximation for maximizing platform profit. This was later improved to a $(1-1/e)$-approximation by Brubach et al. (NeurIPS 2022). In this paper, we extend the problem to a more general and realistic setting.

Firstly, we consider an online stochastic model where customer requests arrive sequentially in a random order. This better reflects real-world scenarios than the offline assumption of known requests. Secondly, we frame the problem within the context of mechanism design, allowing us to benchmark our algorithm against the optimal Bayesian mechanism rather than the more restrictive posted-price mechanisms used in prior work.

Our main contributions include developing a $(1-1/e)$-approximation algorithm under these generalized settings, which we regard as stronger due to the comparison with a more powerful benchmark. The key technical innovation is a novel rounding procedure for fractional matchings. This allows us to devise a new Contention Resolution Scheme (CRS) for transversal matroids, leading to improved approximation guarantees for posted-price mechanisms in combinatorial environments. Specifically, we enhance the ratio from the previous $1/(k+1)$ to $(1-e^{-k})/k$ for the intersection of $k$ transversal matroids.