2019/09/10 by Chaya Levinger, Noam Hazon, Levinger, Chaya +3
Economics, Econometrics and Finance · Engineering · Social Sciences · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #Multiagent Systems (cs.MA) #Transportation Planning and Optimization #Transportation and Mobility Innovations
paper · pdf · doi:10.48550/arxiv.1909.04713
openalex publication_date 2019/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Ride-sharing services are gaining popularity and are crucial for a sustainable environment. A special case in which such services are most applicable, is the last mile variant. In this variant it is assumed that all the passengers are positioned at the same origin location (e.g. an airport), and each have a different destination. One of the major issues in a shared ride is fairly splitting of the ride cost among the passengers. In this paper we use the Shapley value, which is one of the most significant solution concepts in cooperative game theory, for fairly splitting the cost of a shared ride. We consider two scenarios. In the first scenario there exists a fixed priority order in which the passengers are dropped-off (e.g. elderly, injured etc.), and we show a method for efficient computation of the Shapley value in this setting. Our results are also applicable for efficient computation of the Shapley value in routing games. In the second scenario there is no predetermined priority order. We show that the Shapley value cannot be efficiently computed in this setting. However, extensive simulations reveal that our approach for the first scenario can serve as an excellent proxy for the second scenario, outperforming other known proxies.