THE PRICE OF ANARCHY FOR RESTRICTED PARALLEL LINKS
Abstract
In the model of restricted parallel links, n users must be routed on m parallel links under the restriction that the link for each user be chosen from a certain set of allowed links for the user. In a (pure) Nash equilibrium, no user may improve its own Individual Cost (latency) by unilaterally switching to another link from its set of allowed links. The Price of Anarchy is a widely adopted measure of the worst-case loss (relative to optimum) in system performance (maximum latency) incurred in a Nash equilibrium.
In this work, we present a comprehensive collection of bounds on Price of Anarchy for the model of restricted parallel links and for the special case of pure Nash equilibria. Specifically, we prove:
• For the case of identical users and identical links, the Price of Anarchy is
.
• For the case of identical users, the Price of Anarchy is
.
• For the case of identical links, the Price of Anarchy is
, which is asymptotically tight.
• For the most general case of arbitrary users and related links, the Price of Anarchy is at least m – 1 and less than m.
The shown bounds reveal the dependence of the Price of Anarchy on n and m for all possible assumptions on users and links.
The results in this work were included in preliminary form in the paper (by the same group of authors) "Computing Nash Equilibria for Scheduling on Restricted Parallel Links," Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 613–622, June 2004. This work has been partially supported by the IST Program of the European Union under contract numbers IST-1999-14186 (ALCOM-FT), IST-2001-33116 (FLAGS), 001907 (DELIS) and 015964 (AEOLUS).
References
B. Awerbuch , Y. Azar and A. Epstein , The Price of Routing Unsplittable Flow, Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005) pp. 57–66. Google ScholarB. Awerbuch , Tradeoffs in Worst-Case Equilibria, Proceedings of the 1st International Workshop on Approximation and Online Algorithms,Lecture Notes in Computer Science 2909, eds.K. Jansen and R. Solis-Oba (Springer-Verlag, 2003) pp. 41–52. Google ScholarG. Christodoulou and E. Koutsoupias , The Price of Anarchy of Finite Congestion Games, Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005) pp. 67–73. Google ScholarA. Czumaj and B. Vöking , Tight Bounds for Worst-Case Equilibria, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (2002) pp. 413–420. Google Scholar- R. Elsäser, M. Gairing, T. Lücking, M. Mavronicolas and B. Monien, "A Simple Graph-Theoretic Model for Selfish Restricted Scheduling," Proceedings of the First Workshop on Internet and Network Economics, Lecture Notes in Computer Science, Springer-Verlag, Hong-Kong, December 2005, to appear . Google Scholar
D. Fotakis , S. Kontogiannis and P. Spirakis , Selfish Unsplittable Flow, Proceedings of the 31st International Colloquium on Automata, Languages and Programming,Lecture Notes in Computer Science 3142, eds.J. Diaz (Springer-Verlag, 2004) pp. 593–605. Google ScholarM. Gairing , The Price of Anarchy for Polynomial Social Cost, Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science,Lecture Notes in Computer Science , eds.J. Fiala , V. Koubek and J. Kratochvil (Springer-Verlag, 2004) pp. 574–585. Google ScholarM. Gairing , Nash Equilibria in Discrete Routing Games with Convex Latency Functions, Proceedings of the 30th International Colloquium on Automata, Languages, and Programming,Lecture Notes in Computer Science 3142, eds.J. Diaz (Springer-Verlag, 2004) pp. 645–657. Google ScholarT. Lücking , A New Model for Selfish Routing, The 21st International Symposium on Theoretical Aspects of Computer Science,Lecture Notes in Computer Science 2996, eds.V. Diekert and M. Habib (Springer-Verlag, 2004) pp. 547–558. Google Scholar- Theory of Computing Systems 36(6), 683 (2003), DOI: 10.1007/s00224-003-1131-5. Crossref, ISI, Google Scholar
E. Koutsoupias and C. H. Papadimitriou , Worst-Case Equilibria, Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science,Lecture Notes in Computer Science 1563 (Springer-Verlag, 1999) pp. 404–413. Google Scholar- M. Mavronicolas and P. Spirakis, "The Price of Selfish Routing," Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 510–519, July 2001. Also, accepted to Algorithmica . Google Scholar
J. F. Nash , Equilibrium Points in N-Person Games, Proceedings of the National Academy of Sciences36 (1950) pp. 48–49. Google Scholar- Annals of Mathematics 54(2), 286 (1951), DOI: 10.2307/1969529. Crossref, ISI, Google Scholar
C. H. Papadimitriou , Algorithms, Games and the Internet, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (2001) pp. 749–753. Google Scholar- International Journal of Game Theory 2, 65 (1973), DOI: 10.1007/BF01737559. Crossref, ISI, Google Scholar
S. Suri , C. D. Toth and Y. Zhou , Selfish Load Balancing and Atomic Congestion Games, Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (2004) pp. 188–195. Google Scholar


