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)


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.


Algorithmic Mechanism Design Bicriteria Network Design Problems Broadcasting Tree Truthful Mechanisms 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  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)CrossRefGoogle Scholar
  5. 5.
    Feige, U.: A threshold of ln n for approximating set cover. J. of the ACM 45(4), 634–652 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Groves, T.: Incentives in teams. Econometrica 41(4), 617–631 (1973)zbMATHCrossRefMathSciNetGoogle Scholar
  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)CrossRefGoogle Scholar
  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)CrossRefGoogle Scholar
  9. 9.
    Hassin, R.: Approximation schemes for restricted shortest path problems. Math. Oper. Res. 17(1), 36–42 (1992)zbMATHCrossRefMathSciNetGoogle Scholar
  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)zbMATHCrossRefMathSciNetGoogle Scholar
  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)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Nisan, N., Ronen, A.: Algorithmic mechanism design. Games and Economic Behaviour 35, 166–196 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (1994)zbMATHGoogle Scholar
  16. 16.
    Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. of the ACM 49(1), 16–34 (2002)CrossRefMathSciNetGoogle Scholar
  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)CrossRefMathSciNetGoogle Scholar
  20. 20.
    Vickrey, W.: Counterspeculation, auctions and competitive sealed tenders. J. of Finance 16, 8–37 (1961)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

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

Personalised recommendations