The initial idea of the paper was proposed by Ruijie Li, then a visiting student from Southwest Jiaotong University. He read about the mechanism design issues in ride-sharing, and was convinced that more research is needed in this direction.  In this paper we focus on a feature that many ridesharing users care about: the schedule displacement (i.e., the difference between the desired and actual arrival time) in matching.   By assuming the users bid for shared rides by reporting their valuation of the displacement, we are able to analyze the matching and pricing problem using the auction theory, including the well-known VCG scheme.    The paper was published in Transportation Science in 2020.    A preprint may be downloaded here.

Abstract: This paper considers a carpool matching (CaMa) problem in which participants price shared rides based on both operating cost and schedule displacement (i.e, the absolute difference between the desired and actual arrival times). By reporting their valuation of this displacement, each participant in effect bids for every possible shared ride that generates a unique value to her. The CaMa problem can be formulated as a mixed integer program (MIP) that maximizes the social welfare by choosing matching pairs and a departure time for each pair. We show the optimal departure time can be determined for each pair a prior, independent of the matching problem. This result reduces the CaMa problem to a standard bipartite matching problem. We prove that the classical Vickrey-Clarke-Groves (VCG) pricing policy ensures no participant is worse off or has the incentive to misreport their valuation of schedule displacement. To control the large deficit created by the VCG policy, we develop a single-side reward (SSR) pricing policy, which only compensates participants who are forced by the system to endure a schedule displacement. Under the assumption of overpricing tendency (i.e., no participant would want to underreport their value), we show the SSR policy not only generates substantial profits, but also retains the other desired properties of the VCG policy, notably truthful reporting. Even though it cannot rule out underreporting, our simulation experiments confirm that the SSR policy is a robust and deficit-free alternative to the VCG policy. Specifically, we find that (1) underreporting is not a practical concern for a carpool platform as it never reduces the number of matched pairs and its impact on profits is largely negligible; and (2) participants have very little to gain by underreporting their value.