Budget-Feasible Matching and Pricing for Multi-Passenger Ride-Sharing

Abstract

In this paper, we propose an integrated matching and pricing algorithm for multi-passenger ride-sharing systems. While ride-sharing is a promising solution for reducing traffic congestion and CO2 emissions, existing mechanisms, particularly the Vickrey-Clarke-Groves (VCG) mechanism, often fail to ensure budget feasibility (i.e., they may result in a budget deficit), which poses a significant challenge to sustainable operation. To address this issue, we formulate the matching and pricing problem as a single optimization problem incorporating a novel budget-feasibility constraint that explicitly prevents system deficits. We prove that the proposed mechanism simultaneously satisfies three critical economic properties: strategy-proofness, individual rationality, and budget feasibility. Furthermore, numerical simulations in the Yokohama area demonstrate that the proposed method maintains a nonnegative system balance even in scenarios where the standard VCG mechanism incurs a deficit, with only a marginal loss in overall social efficiency.