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.
Work partially supported by the Research Project GRID.IT, funded by the Italian Ministry of Education, University and Research.
Chapter PDF
Similar content being viewed by others
Keywords
References
Archer, A., Tardos, É.: Truthful mechanisms for one-parameter agents. In: Proc. 42nd IEEE Symp. on Foundations of Computer Science (FOCS 2001), pp. 482–491 (2001)
Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.: Linear-time pointermachine algorithms for least common ancestors, MST verification, and dominators. In: Andersson, S.I. (ed.) Summer University of Southern Stockholm 1993. LNCS, vol. 888, pp. 279–288. Springer, Heidelberg (1995)
Cisco Systems Inc.©, Internetworking Technologies Handbook, Cisco Press (2004)
Clarke, E.: Multipart pricing of public goods. Public Choice 8, 17–33 (1971)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. of the ACM 34(3), 596–615 (1987)
Groves, T.: Incentives in teams. Econometrica 41(4), 617–631 (1973)
Gualà, L., Proietti, G.: Optimal MST sensitivity analysis on a pointer machine, manuscript submitted for publication (2005)
Gualà, L., Proietti, G.: A truthful (2-2/k)-approximation mechanism for the Steiner tree problem with k terminals. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 390–400. Springer, Heidelberg (2005) (to appear)
Hershberger, J., Suri, S.: Vickrey prices and shortest paths: what is an edge worth? In: Proc. 42nd IEEE Symp. on Foundations of Computer Science (FOCS 2001), pp. 252–259 (2001)
Malik, K., Mittal, A.K., Gupta, S.K.: The k most vital arcs in the shortest path problem. Oper. Res. Letters 8, 223–227 (1989)
Nardelli, E., Proietti, G., Widmayer, P.: A faster computation of the most vital edge of a shortest path. Info. Proc. Letters 79(2), 81–85 (2001)
Nardelli, E., Proietti, G., Widmayer, P.: Swapping a failing edge of a single source shortest paths tree is good and fast. Algorithmica 36(4), 361–374 (2003)
Nardelli, E., Proietti, G., Widmayer, P.: Finding the most vital node of a shortest path. Theoretical Computer Science 296(1), 167–177 (2003)
Nardelli, E., Proietti, G., Widmayer, P.: Nearly linear time minimum spanning tree maintenance for transient node failures. Algorithmica 40(2), 119–132 (2004)
Nisan, N., Ronen, A.: Algorithmic mechanism design. Games and Economic Behaviour 35, 166–196 (2001)
Osborne, M.J., Rubinstein, A.: A course in Game Theory. MIT Press, Cambridge (1994)
Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Proc. 13th ACM Symp. on Discrete Algorithms (SODA 2002), pp. 267–276 (2002)
Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. of the ACM 49(1), 16–34 (2002)
Proietti, G., Widmayer, P.: A truthful mechanism for the non-utilitarian minimum radius spanning tree problem. In: 17th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA 2005) (2005) (to appear)
Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. of the ACM 22(2), 215–225 (1975)
Vickrey, W.: Counterspeculation, auctions and competitive sealed tenders. J. of Finance 16, 8–37 (1961)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gualà, L., Proietti, G. (2005). Efficient Truthful Mechanisms for the Single-Source Shortest Paths Tree Problem. In: Cunha, J.C., Medeiros, P.D. (eds) Euro-Par 2005 Parallel Processing. Euro-Par 2005. Lecture Notes in Computer Science, vol 3648. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11549468_103
Download citation
DOI: https://doi.org/10.1007/11549468_103
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28700-1
Online ISBN: 978-3-540-31925-2
eBook Packages: Computer ScienceComputer Science (R0)