Abstract
In this work, we consider Wardrop games where traffic has to be routed through a shared network. Traffic is allowed to be split into arbitrary pieces and can be modeled as network flow. For each edge in the network there is a latency function that specifies the time needed to traverse the edge given its congestion. In a Wardrop equilibrium, all used paths between a given source-destination pair have equal and minimal latency.
In this paper, we allow for polynomial latency functions with an upper bound d and a lower bound s on the degree of all monomials that appear in the polynomials. For this environment, we prove upper and lower bounds on the price of anarchy.
This work has been partially supported by the DFG-SFB 376 and by the European Union within the Integrated Project IST-15964 ”Algorithmic Principles for Building Efficient Overlay Computers” (AEOLUS).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact Price of Anarchy for Polynomial Congestion Games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 218–229. Springer, Heidelberg (2006)
Awerbuch, B., Azar, Y., Epstein, A.: The Price of Routing Unsplittable Flow. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 57–66 (2005)
Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press (1956)
Beckmann, M.J.: On the Theory of Traffic Flow in Networks. Traffic Quarterly 21, 109–116 (1967)
Christodoulou, G., Koutsoupias, E.: The Price of Anarchy of Finite Congestion Games. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 67–73 (2005)
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: On the Inefficiency of Equilibria in Nonatomic Congestion Games. In: Jünger, M., Kaibel, V. (eds.) IPCO 2005. LNCS, vol. 3509, pp. 167–181. Springer, Heidelberg (2005)
Cominetti, R., Correa, J.R., Stier-Moses, N.E.: Network Games With Atomic Players. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 525–536. Springer, Heidelberg (2006)
Czumaj, A., Vöcking, B.: Tight Bounds for Worst-Case Equilibria. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 413–420 (2002); Journal of Algorithms as Special Issue of SODA 2002 (accepted)
Gairing, M., Lücking, T., Mavronicolas, M., Monien, B.: The Price of Anarchy for Polynomial Social Cost. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 574–585. Springer, Heidelberg (2004)
Gairing, M., Lücking, T., Mavronicolas, M., Monien, B.: The Price of Anarchy for Restricted Parallel Links. Parallel Processing Letters 16(1), 117–131 (2006)
Gairing, M., Lücking, T., Monien, B., Tiemann, K.: Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 51–65. Springer, Heidelberg (2005)
Gairing, M., Monien, B., Tiemann, K.: Selfish Routing with Incomplete Information. In: Proceedings of the 17th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2005), pp. 203–212 (2005)
Gairing, M., Monien, B., Tiemann, K.: Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 501–512. Springer, Heidelberg (2006)
Koutsoupias, E., Papadimitriou, C.H.: Worst-Case Equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
Mavronicolas, M., Spirakis, P.: The Price of Selfish Routing. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC 2001), pp. 510–519 (2001)
Nash, J.F.: Non-Cooperative Games. Annals of Mathematics 54(2), 286–295 (1951)
Pigou, A.C.: The Economics of Welfare. Macmillan and Company, Basingstoke (1920)
Rosenthal, R.W.: A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory 2, 65–67 (1973)
Roughgarden, T.: The Price of Anarchy is Independent of the Network Topology. Journal of Computer and System Sciences 67(2), 341–364 (2003)
Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press, Cambridge (2005)
Roughgarden, T., Tardos, É.: How Bad Is Selfish Routing? Journal of the ACM 49(2), 236–259 (2002)
Vazirani, V.: Approximation Algorithms. Springer, Heidelberg (2001)
Wardrop, J.G.: Some Theoretical Aspects of Road Traffic Research. In: Proceedings of the Institute of Civil Engineers, Pt. II, vol. 1, pp. 325–378 (1952)
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
Dumrauf, D., Gairing, M. (2006). Price of Anarchy for Polynomial Wardrop Games. In: Spirakis, P., Mavronicolas, M., Kontogiannis, S. (eds) Internet and Network Economics. WINE 2006. Lecture Notes in Computer Science, vol 4286. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11944874_29
Download citation
DOI: https://doi.org/10.1007/11944874_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68138-0
Online ISBN: 978-3-540-68141-0
eBook Packages: Computer ScienceComputer Science (R0)