Approximate mechanisms for the graphical TSP and other graph-traversal problems. (English) Zbl 1195.90015

Summary: Let \(G=(V,E)\) be a graph modeling a network in which each edge is owned by a selfish agent, which establishes the cost for traversing its edge (i.e., assigns a weight to its edge) by pursuing only its personal utility. In such a setting, we aim at designing approximate truthful mechanisms for several NP-hard traversal problems on \(G\), such as the graphical traveling salesman problem, the rural postman problem, and the mixed Chinese postman problem, each of which in general requires an edge of \(G\) to be used several times. Thus, in game-theoretic terms, these are one-parameter problems, but with a peculiarity: the workload of each agent is a natural number. In this paper we refine the classical notion of monotonicity of an algorithm so as to capture exactly this property, and we then provide a general mechanism-design technique that guarantees this monotonicity and that allows one to compute efficiently the corresponding payments. In this way, we show that the former two problems and the latter one admit a \(3/2\)- and a 2-approximate truthful mechanism, respectively. Thus, for the first two problems we match the best known approximation ratios holding for their corresponding centralized versions, while for the third one we are only a \(4/3\)-factor away from it.


90B10 Deterministic network models in operations research
90C60 Abstract computational complexity for mathematical programming problems
68M11 Internet topics
Full Text: DOI