z-logo
Premium
Efficient truthful mechanisms for the single‐source shortest paths tree problem
Author(s) -
Gualà L.,
Proietti G.
Publication year - 2007
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.1167
Subject(s) - combinatorics , binary logarithm , enhanced data rates for gsm evolution , network topology , tree (set theory) , valuation (finance) , graph , computer science , undirected graph , mathematics , time complexity , node (physics) , discrete mathematics , mathematical optimization , computer network , artificial intelligence , physics , finance , economics , quantum mechanics
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here