Cost-Sharing Mechanism Design for Social Cost Minimization in Ridesharing Systems.

Ridesharing, as an emerging efficient solution for transportation congestion, has achieved great business success in recent years. A critical issue in the ridesharing system is to determine a group of passengers to share a ride and the corresponding payments to charge them to cover the cost of drivers. We present the desired properties of a cost-sharing mechanism in ridesharing systems, namely economic efficiency, incentive compatibility, individual rationality and budget balance. However, the existing classic mechanisms do not achieve these properties even in a simple case. In this work, we formulate a cost-sharing model for ridesharing systems, and design two VCG-based mechanisms for the simple case and the general case, respectively. The simple case can capture the ridesharing problem with a symmetric cost function, while the general case describes a more general ridesharing problem with a submodular cost function. We theoretically demonstrate that these two mechanisms are approximately economic efficient with other desirable properties guaranteed. Finally, we evaluate the proposed mechanisms on a real-world dataset. The evaluation results show that our mechanism could increase the user experience of passengers as well as the efficiency of the ridesharing system.