Exact and Approximate Truthful Mechanisms for the 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. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most popular structures in communication networks, i.e., the single-source shortest paths tree. More precisely, we will study several realistic scenarios, in which each agent can own either a single or multiple edges of G. In particular, for the single-edge case, we will show that: (i) in the classic utilitarian case, the problem can be solved efficiently in O(mnlog alpha(m, n)) time, where alpha(m, n) is the inverse of the Ackermann's function; (ii) in a meaningful non-utilitarian case, namely that in which agents' valuation functions only depend on the edge lengths, the problem can be solved in O( m + n log n) time. Conversely, for the multiple- edges case, we will show in the utilitarian case an O(mP + nP log n) time truthful mechanism, where P = O( n) denotes the number of agents participating in the solution, while in the same non-utilitarian case we will prove a general lower bound to the approximation ratio that can be achieved by any truthful mechanism, by showing that no c-approximate mechanism can exist, for any fixed c < 5+root 13/3+root 13.