Reverse Auction Based Incentive Order Matching Mechanism for Real-Time Ride-Sharing

Ride-sharing has played an important role in reducing travel costs and global pollution. However, existing works of online matching passengers' orders with vehicles usually aims to minimize the total travel distance of drivers or maximize the profit made by the platform running the ride-sharing service. They ignore the fact that vehicle drivers are usually selfish and heterogeneous, and intend to maximize their own payoffs. In this paper, we intend to solve this online matching issue with the aim of maximizing the social welfare of the platform and vehicles. Specifically, we propose two incentive order matching mechanisms based reverse auction (i.e. MSWR-VCG and MSWR-GM), where the vehicle drivers bid for the orders published by the platform to accomplish the order while making profits. We theoretically prove the related properties of our mechanisms, such as truthfulness, individual rationality, budget-balance, etc. We then evaluate the performance of the mechanism based on the real order data of taxis in New York City and demonstrate that our mechanisms can achieve higher social welfare than the state-of-the-art method which is adopted by industry. Furthermore, we find MSWR-VCG can achieve higher payoff for drivers than MSWR-GM and MSWR-GM can balance the effectiveness of social welfare and computational efficiency well.