Sharing the Shared Rides: Multi-Party Carpooling Supported Strategy-Proof Double Auctions

Abstract

Multi-party carpooling emerges as a burgeoning shared transportation scheme whereby the trip shared by each driver is shared among multi-party riders whose itineraries coincide. Confronting the information asymmetry and the voluntary self-interested nature of bilateral participants in matching and pricing operations, this study designs Multi-party cArpooling SupporTed stratEgy-pRoof (MASTER) double auction mechanisms considering personalized carpooling constraints. First, in a scheduled carpooling scenario, two $\mathrm{MASTE}{\mathrm{R}}^{\mathrm{S}}$ mechanisms that masterfully blend the ideas of the famed trade reduction method and multi-stage approach are proposed which implement distinct group bid determination approaches for responding to different market conditions. Second, in an on-demand carpooling scenario, two parameterized $\mathrm{MASTE}{\mathrm{R}}^{\mathrm{O}}$ mechanisms that integrate frustration-based promotion to proactively prioritize matching and deferentially compensate riders based on their waits are contrived which also endow the platform with operational flexibility to agilely pursue alterable operational objectives by adjusting promotion strength. We prove theoretically that the proposed mechanisms satisfy strategy proofness, budget balance, individual rationality, and asymptotic efficiency under mild conditions. Experimental results reveal that multi-party carpooling constitutes a multi-win solution under higher rider-driver ratios whilst it could be detrimental to drivers otherwise, which can be ameliorated by favoring the driver side in determining promotion strength. Simulation studies manifest that our proposed auction mechanisms could bring benefits concerning allocation efficiency and service responsiveness compared with their academic and practical counterparts. We also shed light on choosing among alternative mechanisms according to market conditions and operational orientations.