A Study of Proxies for Shapley Allocations of Transport Costs

Monday, May 5, 2014, 11:00am – 12:30pm
Presented by Casey Cahan, Haris Aziz, Charles Gretton, Phillip Kilby, Nicholas Mattei, and Toby Walsh
Located in TBD
In track CoopMAS2014

We consider the traveling salesperson game (TSG) in which agents correspond to a set of locations, and the cost of each subset of locations is the length of the optimal tour for that subset. The Shapley value, one of the most important normative division schemes in cooperative games, is a principled way of dividing transport costs among such locations. We prove that approximating the Shapley value of the TSG within a constant factor is NP-hard. In view of this negative result, we consider six proxies for the Shapley value which are easier to compute, with two of the proxies appealing to the well-known Held-Karp and Christofides TSP heuristics, respectively. We perform an experimental evaluation using synthetic Euclidean games as well as games derived from real-world tours calculated for fast-moving consumer goods scenarios. Our experiments show that several computationally tractable proxies give good approximations of Shapley allocations in practice.