  Ride-sharing or vehicle-pooling allows commuters to team up spontaneously for
transportation cost sharing. This has become a popular trend in the emerging
paradigm of sharing economy. One crucial component to support effective
ride-sharing is the matching mechanism that pairs up suitable commuters.
Traditionally, matching has been performed in a centralized manner, whereby an
operator arranges ride-sharing according to a global objective (e.g., total
cost of all commuters). However, ride-sharing is a decentralized
decision-making paradigm, where commuters are self-interested and only
motivated to team up based on individual payments. Particularly, it is not
clear how transportation cost should be shared fairly between commuters, and
what ramifications of cost-sharing are on decentralized ride-sharing. This
paper sheds light on the principles of decentralized ride-sharing and
vehicle-pooling mechanisms based on stable matching, such that no one would be
better off to deviate from a stable matching outcome. We study various fair
cost-sharing mechanisms and the induced stable matching outcomes. We compare
the stable matching outcomes with a social optimal outcome (that minimizes
total cost) by theoretical bounds of social optimality ratios, and show that
several fair cost-sharing mechanisms can achieve high social optimality. We
also corroborate our results with an empirical study of taxi sharing under fair
cost-sharing mechanisms by a data analysis on New York City taxi trip dataset,
and provide useful insights on effective decentralized mechanisms for practical
ride-sharing and vehicle-pooling.
