The price of anarchy of finite congestion games

ABSTRACT

We consider the price of anarchy of pure Nash equilibria in congestion games with linear latency functions. For asymmetric games, the price of anarchy of maximum social cost is Θ(√N), where N is the number of players. For all other cases of symmetric or asymmetric games and for both maximum and average social cost, the price of anarchy is 5/2. We extend the results to latency functions that are polynomials of bounded degree. We also extend some of the results to mixed Nash equilibria.

REFERENCES

• 1: Baruch Awerbuch , Yossi Azar , Amir Epstein, Large the price of routing unsplittable flow, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060599]
• 2: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 3: G. Christodoulou and E. Koutsoupias. On the price of anarchy and stability of correlated equilibria of linear congestion games Submitted. http://www.di.uoa.gr/~elias/publications/paper-ck05b.ps
• 4: J. R. Correa, A. S. Schulz and N. S. Moses. Computational Complexity, Fairness, and the Price of Anarchy of the Maximum Latency Problem. In Proceedings of the 10th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 59--73, 2004.
• 5: Artur Czumaj , Piotr Krysta , Berthold Vöcking, Selfish traffic allocation for server farms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509952]
• 6: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 7: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 8: D. Fotakis, S. C. Kontogiannis and P. G. Spirakis. Selfish Unsplittable Flows. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), pages 593--605, 2004.
• 9: M. Gairing, T. Lücking, M. Mavronicolas and B. Monien. The Price of Anarchy for Polynomial Social Cost. In Proceedings of the 29th International Symposium of Mathematical Foundations of Computer Science (MFCS), pages 574--585, 2004.
• 10: Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien, Computing Nash equilibria for scheduling on restricted parallel links, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007446]
• 11: M. Gairing, T. Lücking, M. Mavronicolas, B. Monien and M. Rode. Nash Equilibria in Discrete Routing Games with Convex Latency Functions. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), pages 645--657, 2004.
• 12: E. Koutsoupias, M. Mavronicolas, and P. Spirakis. Approximate Equilibria and Ball Fusion. In Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2002
• 13: E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 404--413, 1999.
• 14: T. Lücking, M. Mavronicolas, B. Monien and M. Rode. A New Model for Selfish Routing. In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 547--558, 2004.
• 15: Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece [doi>10.1145/380752.380846]
• 16: I. Milchtaich. Congestion Games with Player-Specific Payoff Functions. Games and Economic Behavior 13, pages 111--124, 1996.
• 17: D. Monderer and L. S. Shapley. Potential Games. Games and and Economic Behavior 14, pages 124--143, 1996.
• 18: M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, 1994.
• 19: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 20: R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 21: Tim Roughgarden, The price of anarchy is independent of the network topology, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509971]
• 22: Tim Roughgarden, The maximum latency of selfish routing, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 23: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 24: T. Roughgarden and E. Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior, 47(2):389--403, 2004.
• 25: Subhash Suri , Csaba D. Tóth , Yunhong Zhou, Selfish load balancing and atomic congestion games, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007941]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Performance, Theory

Keywords:
congestion games, price of anarchy