Abstract
We provide a collection of new upper and lower bounds on the price of anarchy for singleton congestion games. In our study, we distinguish between restricted and unrestricted strategy sets, between weighted and unweighted player weights, and between linear and polynomial latency functions.
Work partially supported by the European Union within the Integrated Project IST-15964 “Algorithmic Principles for Building Efficient Overlay Computers” (AEOLUS). Research for this work was done while the first author was at the University of Paderborn.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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: Proc. of 37th STOC, pp. 57–66 (2005)
Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight Bounds for Selfish and Greedy Load Balancing. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 311–322. Springer, Heidelberg (2006)
Christodoulou, G., Koutsoupias, E.: On The Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 59–70. Springer, Heidelberg (2005)
Christodoulou, G., Koutsoupias, E.: The Price of Anarchy of Finite Congestion Games. In: Proc. of 37th STOC, pp. 67–73 (2005)
Czumaj, A., Vöcking, B.: Tight Bounds for Worst-Case Equilibria. ACM Transactions on Algorithms 3(1) (2007) (Article No. 4)
Elsässer, R., Gairing, M., Lücking, T., Mavronicolas, M., Monien, B.: A Simple Graph-Theoretic Model for Selfish Restricted Scheduling. In: Deng, X., Ye, Y. (eds.) WINE 2005. LNCS, vol. 3828, pp. 195–209. Springer, Heidelberg (2005)
Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 123–134. Springer, Heidelberg (2002)
Gairing, M., Lücking, T., Mavronicolas, M., Monien, B.: Computing Nash Equilibria for Scheduling on Restricted Parallel Links. In: Proc. of 36th STOC, pp. 613–622 (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., Mavronicolas, M., Monien, B., Rode, M.: Nash Equilibria in Discrete Routing Games with Convex Latency Functions. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 645–657. Springer, Heidelberg (2004)
Gairing, M., Monien, B., Tiemann, K.: Selfish Routing with Incomplete Information. In: Proc. of 17th SPAA, 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., Mavronicolas, M., Spirakis, P.: Approximate Equilibria and Ball Fusion. Theory of Computing Systems 36(6), 683–693 (2003)
Koutsoupias, E., Papadimitriou, C.H.: Worst-Case Equilibria. In: Meinel, C., Tison, S. (eds.) STACS 99. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: A New Model for Selfish Routing. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 547–558. Springer, Heidelberg (2004)
Milchtaich, I.: Congestion Games with Player-Specific Payoff Functions. Games and Economic Behavior 13(1), 111–124 (1996)
Nash, J.F.: Non-Cooperative Games. Annals of Mathematics 54(2), 286–295 (1951)
Rosenthal, R.W.: A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory 2, 65–67 (1973)
Roughgarden, T., Tardos, E.: How Bad Is Selfish Routing? Journal of the ACM 49(2), 236–259 (2002)
Suri, S., Tóth, C.D., Zhou, Y.: Selfish Load Balancing and Atomic Congestion Games. In: Proc. of 16th SPAA, pp. 188–195 (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gairing, M., Schoppmann, F. (2007). Total Latency in Singleton Congestion Games. In: Deng, X., Graham, F.C. (eds) Internet and Network Economics. WINE 2007. Lecture Notes in Computer Science, vol 4858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77105-0_42
Download citation
DOI: https://doi.org/10.1007/978-3-540-77105-0_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77104-3
Online ISBN: 978-3-540-77105-0
eBook Packages: Computer ScienceComputer Science (R0)