Matching and fair pricing of socially optimal, stable and financially sustainable ride-sharing in congestible networks

The paper deals with matching and fair pricing in urban peer-to-peer ride-sharing schemes where the following desirable properties hold: (i) matchings between passengers and drivers are decided by a social planner to minimize total car-kilometers travelled, (ii) matchings are stable, i.e. no pair of passenger and driver can both increase their fuel cost-related surplus from breaking the current partnership, and (iii) the scheme is financially sustainable, i.e. there is no need of subsidy. The case where travel times are affected by matchings, in the light of the reduced number of cars travelling on the network, is unexplored. The paper fills this gap. The matching optimization problem is formulated as linear programming problem with nonlinear equilibrium constraints and node-link network representation. Solution to the approximately equivalent mixed-integer linear programming formulation is obtained by available efficient off-the-shelf solvers. Duality theory is used to specify a stability compliant pricing scheme based on fair surplus division: the surplus gained by each traveler is exactly half way between the minimum and the maximum she can obtain from any stable solution. Computation of prices requires solution of two linear programming problems. The price paid by the passenger is received by the driver. Since surplus of each traveler is nonnegative, subsidies are not needed. A toy network and a small network are used to illustrate the theoretical findings, and to appraise the pricing-induced shares of trip cost that accrue to each traveler.