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.

Exact and Approximate Truthful Mechanisms for the Shortest-Paths Tree Problem

PROIETTI, GUIDO
2007-01-01

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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: https://hdl.handle.net/11697/18690
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 3
social impact