On approximately fair cost allocation in Euclidean TSP games

We consider the problem of allocating the cost of an optimal traveling salesman tour in a fair way among the nodes visited; in particular, we focus on the case where the distance matrix of the underlying TSP problem satisfies the triangle inequality. We thereby use the model of TSP games in the sense of cooperative game theory. We give examples showing that the core of such games may be empty, even for the case of Euclidean distances. On the positive, we develop an LP-based allocation rule guaranteeing that no coalition pays more than α times its own cost, where α is the ratio between the optimal TSP-tour and the optimal value of its Held–Karp relaxation, which is also known as the solution over the ‘subtour polytope’. A well-known conjecture states that α ≤ 4/3. We also exhibit examples showing that this ratio cannot be improved below 4/3.