A Study of Proxies for Shapley Allocations of Transport Costs by Dr Nick Mattei
Date: Friday,13 June 2014
Venue: Civil & Environmental Engineering Building H20, Level G, Room G8
Time: 2:00 – 3:00pm
Guest Speaker: Dr Nick Mattei, PhD, Researcher in the Optimisation Group at NICTA, Adjunct lecturer at UNSW Australia
Abstract :
We consider the travelling 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.
Hosted by:
Research Centre for Integrated Transport Innovation (rCITI)
School of Civil and Environmental Engineering & Computer Science and Engineering
