Abstract
In this paper we address the open problem of bounding the price of stability for network design with fair cost allocation for undirected graphs posed in [1]. We consider the case where there is an agent in every vertex. We show that the price of stability is O(loglogn). We prove this by defining a particular improving dynamics in a related graph. This proof technique may have other applications and is of independent interest.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: Proc. of 45th FOCS, pp. 295–304 (2004)
Anshelevich, E., Dasgupta, A., Tardos, E., Wexler, T.: Near-optimal network design with selfish agents. In: Proc. of 35th STOC, pp. 511–520 (2003)
Awerbuch, B., Azar, Y., Epstein, A.: Large the price of routing unsplittable flow. In: Proc. of 37th STOC, pp. 57–66 (2005)
Christodoulou, G., Koutsoupias, E.: On the price of anarchy and stability of correlated equilibria of linear congestion games. In: Proc. of 13th ESA, pp. 59–70 (2005)
Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proc. of 37th STOC, pp. 67–73 (2005)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
Monderer, D., Shapley, L.: Potential games. Games and Economic Behavior 14, 124–143 (1996)
Rosenthal, R.: A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory 2, 65–67 (1972)
Roughgarden, T., Tardos, E.: How bad is selfish routing? Journal of the ACM 49(2), 236–259 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fiat, A., Kaplan, H., Levy, M., Olonetsky, S., Shabo, R. (2006). On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds) Automata, Languages and Programming. ICALP 2006. Lecture Notes in Computer Science, vol 4051. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11786986_53
Download citation
DOI: https://doi.org/10.1007/11786986_53
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35904-3
Online ISBN: 978-3-540-35905-0
eBook Packages: Computer ScienceComputer Science (R0)