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.

Gualà, 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

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.
Euro-Par 2005, Parallel Processing, 11th International Euro-Par Conference
Rilevanza internazionale
contributo
Settore INF/01 - Informatica
eng
https://link.springer.com/chapter/10.1007%2F11549468_103
Intervento a convegno
Gualà, 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].
Guala', L; Proietti, G
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/42767
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 6
social impact