A second-pricing based incentive-compatible mechanism for matching and pricing in ride-sharing

As a novel and economical transportation way, ride-sharing has attracted more and more passengers and drivers to participate. How to match passengers with drivers efficiently has become a key issue. Specifically, drivers are usually heterogeneous with different costs, and they may behave strategically (e.g. reveal their private cost information untruthfully) in order to make more profits. Drivers' strategic behavior may lead to inefficient matching, which results in the loss of social welfare of ride-sharing platforms and drivers. In this paper, an incentive-compatible and efficient mechanism is proposed to solve this issue, which can match passengers with drivers and determine the payments to drivers in order to maximize social welfare while ensuring drivers reveal their cost information truthfully. Specifically, an order matching algorithm with branch and bound based route planning is designed to accelerate the matching process. Meanwhile, the payments to drivers are computed based on the second-pricing algorithm. In so doing, a second-pricing based ride-sharing mechanism (SPRM) is proposed, which satisfies incentive compatibility, individual rationality, budget balance and computational efficiency. Based on the real Manhattan taxi order data and vehicle fuel consumption data, extensive experiments are conducted to evaluate the proposed mechanism. The experimental results show that SPRM can guarantee drivers' profits and improve the ratio of drivers' participation and the ratio of served orders, and eventually achieve greater social welfare than four typical benchmark approaches, GPri, ND, mTshare and mdp. The research of this paper can provide useful insights for designing efficient ride-sharing system to maximize the social welfare of all participants in the real life.