Efficient truthful mechanisms for the single‐source shortest paths tree problem

Let a communication network be modeled by an undirected graph $G=(V,E)$ of n nodes and m edges, and assume that edges are controlled by selfish agents, which privately hold the length of each owned edge. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most popular network topologies, i.e. the single‐source shortest paths tree . More precisely, we study several realistic scenarios, in which each agent can own either a single edge or multiple edges of G . In particular, for the single‐edge scenario, we show that in the utilitarian case the problem can be efficiently solved in $O(mn \log{}\alpha(m,n))$ time, while in a meaningful non‐utilitarian case, namely that in which agents' valuation functions depend only on the edge lengths, it can be solved in $O(m + n \log n)$ time. On the other hand, for the multiple‐edge scenario, in the utilitarian case we show an $O(mn+n^2 \log n)$ time truthful mechanism, while in the same non‐utilitarian case we provide an n ‐approximate truthful mechanism which can be implemented in $O(m n \,\alpha(m,n))$ time. We also show that in the special case in which, for every agent, the owned edges are all incident to the same node, then this latter mechanism has an almost optimal $O(m\,\alpha(m,n))$ runtime. Copyright © 2007 John Wiley & Sons, Ltd.