Social optimality and stability of matchings in peer-to-peer ridesharing

Peer-to-peer ridesharing, where drivers are also travellers, can alleviate congestion and emissionsthat plague cities by increasing vehicle occupancy. We propose a socially optimal ridesharing scheme, where a social planner matches passengers and drivers in a way that minimizes travel costs (travel time and fuel) plus environmental costs. The contribution helps in computing the socially optimal ridesharing schemes for networks of any topology within a static framework of route choice with exogenously fixed travel times. A linear programming problem is formulated to compute the optimal matchings. Existence, integrality and uniqueness properties are investigated. The social planner receives a payment from passengers and rewards drivers for the higher costs they bear. Passengers and drivers never incur a loss because travelling alone remains always an option, but matchings may need to be subsidised. The socially optimal matching solution without environmental costs is proved to satisfy the stability property according to which no pair of passenger and driver prefers each other to any of the current partners. In the Sioux Falls network, when 20% of individuals are willing to rideshare, with 80% of passengers travelling by car and 20% by public transport, 17.37% optimally do so, resulting in a 7.05% decrease in CO2 emissions on the all-travel-alone scenario.