# On the Existence of Truthful Mechanisms for the Minimum-Cost Approximate Shortest-Paths Tree Problem

• Davide Bilò
• Luciano Gualà
• Guido Proietti
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)

## Abstract

Let a communication network be modeled by a graph G = (V,E) of n nodes and m edges, where with each edge is associated a pair of values, namely its cost and its length. Assume now that each edge is controlled by a selfish agent, which privately holds the cost of the edge. In this paper we analyze the problem of designing in this non-cooperative scenario a truthful mechanism for building a broadcasting tree aiming to balance costs and lengths. More precisely, given a root node rV and a real value λ≥1, we want to find a minimum cost (as computed w.r.t. the edge costs) spanning tree of G rooted at r such that the maximum stretching factor on the distances from the root (as computed w.r.t. the edge lengths) is λ. We call such a tree the Minimum-cost λ -Approximate Shortest-paths Tree (λ-MAST).

First, we prove that, already for the unit length case, the λ-MAST problem is hard to approximate within better than a logarithmic factor, unless NP admits slightly superpolynomial time algorithms. After, assuming that the graph G is directed, we provide a (1 + ε)(n – 1)-approximate truthful mechanism for solving the problem, for any ε> 0. Finally, we analyze a variant of the problem in which the edge lengths coincide with the private costs, and we provide: (i) a constant lower bound (depending on λ) to the approximation ratio that can be achieved by any truthful mechanism; (ii) a $$(1+ {{n-1}\over{\lambda}})$$-approximate truthful mechanism.

## Keywords

Algorithmic Mechanism Design Bicriteria Network Design Problems Broadcasting Tree Truthful Mechanisms

## References

1. 1.
Ambühl, C., Clementi, A., Penna, P., Rossi, G., Silvestri, R.: Energy consumption in radio networks: selfish agents and rewarding mechanisms. In: Proc. 10th Int. Colloquium on Structural Information Complexity (SIROCCO 2003). Proceedings in Informatics, vol. 17, pp. 1–16. Carleton Scientific (2003)Google Scholar
2. 2.
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)Google Scholar
3. 3.
Briest, P., Krysta, P., Vöcking, B.: Approximation techniques for utilitarian mechanism design. In: Proc. 37th Ann. ACM Symp. on Theory of Computing (STOC 2005), pp. 39–48 (2005)Google Scholar
4. 4.
Clarke, E.: Multipart pricing of public goods. Public Choice 8, 17–33 (1971)
5. 5.
Feige, U.: A threshold of ln n for approximating set cover. J. of the ACM 45(4), 634–652 (1998)
6. 6.
Groves, T.: Incentives in teams. Econometrica 41(4), 617–631 (1973)
7. 7.
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)
8. 8.
Gualà, L., Proietti, G.: Efficient truthful mechanisms for the single-source shortest paths tree problem. In: Cunha, J.C., Medeiros, P.D. (eds.) Euro-Par 2005. LNCS, vol. 3648, pp. 941–951. Springer, Heidelberg (2005)
9. 9.
Hassin, R.: Approximation schemes for restricted shortest path problems. Math. Oper. Res. 17(1), 36–42 (1992)
10. 10.
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)Google Scholar
11. 11.
Kao, M.-Y., Li, X.-Y., Wang, W.: Towards truthful mechanisms for binary demand games: a general framework. In: Proc. 6th ACM Conference on Electronic Commerce (EC 2005), pp. 213–222 (2005)Google Scholar
12. 12.
Khuller, S., Raghavachari, B., Young, N.E.: Balancing minimum spanning trees and shortest-path trees. Algorithmica 14(4), 305–321 (1995)
13. 13.
Marathe, M.V., Ravi, R., Sundaram, R., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Bicriteria network design problems. J. Algorithms 28(1), 142–171 (1998)
14. 14.
Nisan, N., Ronen, A.: Algorithmic mechanism design. Games and Economic Behaviour 35, 166–196 (2001)
15. 15.
Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (1994)
16. 16.
Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. of the ACM 49(1), 16–34 (2002)
17. 17.
Phillips, C.A.: The network inhibition problem. In: Proc. 25th Ann. ACM Symp. on Theory of Computing (STOC 1993), pp. 776–785 (1993)Google Scholar
18. 18.
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 2005), pp. 195–202 (2005)Google Scholar
19. 19.
Tarjan, R.E.: Sensitivity analysis of minimum spanning trees and shortest path problems. Inform. Proc. Lett. 14, 30–33 (1982)
20. 20.
Vickrey, W.: Counterspeculation, auctions and competitive sealed tenders. J. of Finance 16, 8–37 (1961)

## Authors and Affiliations

• Davide Bilò
• 1
• Luciano Gualà
• 1
• Guido Proietti
• 1
• 2
1. 1.Dipartimento di InformaticaUniversità di L’AquilaItaly
2. 2.Istituto di Analisi dei Sistemi ed Informatica, CNRRomaItaly