Technical Note—On Traveling Salesman Games with Asymmetric Costs
Alejandro Toriello, Nelson A. Uhan
Operations Research · 2013 · Volume 61 · Issue 6
Abstract
We consider cooperative traveling salesman games with nonnegative asymmetric costs satisfying the triangle inequality. We construct a stable cost allocation with budget balance guarantee equal to the Held-Karp integrality gap for the asymmetric traveling salesman problem, using the parsimonious property and a previously unknown connection to linear production games. We also show that our techniques extend to larger classes of network design games. We then provide a simple example showing that our cost allocation does not necessarily achieve the best possible budget balance guarantee, even among cost allocations stable for the game defined by the Held-Karp relaxation, and discuss its implications on future work on traveling salesman games.
Keywords
games/group decisions, cooperative game, networks/graphs, traveling salesman problem, integer programming, integrality gap
Enable JavaScript for citation tools and additional paper interactions.