A Study of Proxies for Shapley Allocations of Transport Costs by Dr Nick Mattei

L- R: David Rey, Nick Mattei and Hanna Grzybowska

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

Click here to Download the attached flyer