Efficient Computation and Estimation of the Shapley Value for Traveling Salesman Games

Abstract

The traveling salesman game (TSG) consists of dividing the cost of a round trip among several customers. One of the most significant solution concepts in cooperative game theory is the Shapley value, which provides a fair division of the costs for a variety of games including the TSG, based on the marginal costs attributed with each customer. In this paper, we consider efficient methods for computing the Shapley value for the TSG. There exist two major variants of the TSG. In the first variant, there exists a fixed order in which the customers are serviced. We show a method for efficient computation of the Shapley value in this setting. Our result is also applicable for efficient computation of the Shapley value in ride-sharing settings, when a number of passengers would like to fairly split their ride cost. In the second variant, there is no predetermined fixed order. We show that the Shapley value cannot be efficiently computed in this setting. However, extensive simulations reveal that our approach for the first variant can serve as an excellent proxy for the second variant, outperforming the state-of-the-art methods.

Keywords

• Shapley value
• traveling salesman games
• vehicle routing problem