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 α(m,n)) time, where α(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+nlog n) time. Conversely, for the multiple-edges case, we will show in the utilitarian case an O(mP+nPlog 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<\frac{5+\sqrt{13}}{3+\sqrt{13}}\) .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Archer, A., Tardos, É.: Truthful mechanisms for one-parameter agents. In: Proc. 42nd IEEE Symp. on Foundations of Computer Science (FOCS’01), pp. 482–491 (2001)
Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.: Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators. In: Proc. 30th ACM Symp. on Theory of Computing (STOC’98), pp. 279–288 (1998)
Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann time complexity. J. ACM 47(6), 1028–1047 (2000)
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. ACM 34(3), 596–615 (1987)
Gabow, H.N.: A scaling algorithm for weighted matching on general graphs. In: Proc. 26th IEEE Symp. on Foundations of Computer Science (FOCS’85), pp. 90–100 (1985)
Groves, T.: Incentives in teams. Econometrica 41(4), 617–631 (1973)
Gualà, L., Proietti, G.: A truthful (2-2/k)-approximation mechanism for the Steiner tree problem with k terminals. In: Proc. 11th Int. Computing and Combinatorics Conference (COCOON’05). Lecture Notes in Computer Science, vol. 3595, pp. 390–400. Springer, New York (2005)
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’01), pp. 252–259 (2001)
Malik, K., Mittal, A.K., Gupta, S.K.: The k most vital arcs in the shortest path problem. Oper. Res. Lett. 8, 223–227 (1989)
Nardelli, E., Proietti, G., Widmayer, P.: A faster computation of the most vital edge of a shortest path. Inf. Process. Lett. 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. Theor. Comput. Sci. 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 Econ. Behav. 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’02), pp. 267–276 (2002)
Proietti, G., Widmayer, P.: A truthful mechanism for the non-utilitarian minimum radius spanning tree problem. In: Proc. 17th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA’05), pp. 195–202 (2005)
Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215–225 (1975)
Vickrey, W.: Counterspeculation, auctions and competitive sealed tenders. J. Finance 16, 8–37 (1961)
Author information
Authors and Affiliations
Corresponding author
Additional information
Work partially supported by the Research Project GRID.IT, funded by the Italian Ministry of Education, University and Research. Part of the results herein contained was presented at the 11th International Euro-Par Conference (Euro-Par’05), Lisbon, Portugal, 2005.
Rights and permissions
About this article
Cite this article
Gualà, L., Proietti, G. Exact and Approximate Truthful Mechanisms for the Shortest Paths Tree Problem. Algorithmica 49, 171–191 (2007). https://doi.org/10.1007/s00453-007-9016-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-007-9016-7