Let a communication network be modelled by an undirected graph G=(V,E) of n nodes and m edges, and assume that each edge is controlled by a selfish agent. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most used structures in communication networks, i.e., the single-source shortest paths tree. More precisely, we will show that under various realistic agents’ behavior scenarios, it can be guaranteed not only the existence, but also the efficiency (in terms of running time complexity) of such mechanisms. In particular, for the fundamental case in which the problem is utilitarian, we will show that a truthful mechanism can be computed in O(mn log α(m,n)) time, where α(m,n) is the classic inverse of the Ackermann’s function.
Guala', L., Proietti, G. (2005). Efficient Truthful Mechanisms for the Single-Source Shortest Paths Tree Problem. In Lecture Notes in Computer Science Volume 3648, 2005, Pages 941-951 11th International Euro-Par Conference, Euro-Par 2005. Springer [10.1007/11549468_103].
Efficient Truthful Mechanisms for the Single-Source Shortest Paths Tree Problem
GUALA', LUCIANO;
2005-01-01
Abstract
Let a communication network be modelled by an undirected graph G=(V,E) of n nodes and m edges, and assume that each edge is controlled by a selfish agent. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most used structures in communication networks, i.e., the single-source shortest paths tree. More precisely, we will show that under various realistic agents’ behavior scenarios, it can be guaranteed not only the existence, but also the efficiency (in terms of running time complexity) of such mechanisms. In particular, for the fundamental case in which the problem is utilitarian, we will show that a truthful mechanism can be computed in O(mn log α(m,n)) time, where α(m,n) is the classic inverse of the Ackermann’s function.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.