zbMATH — the first resource for mathematics

Worst-case equilibria. (English) Zbl 1303.91012
Summary: In a system where noncooperative agents share a common resource, we propose the price of anarchy, which is the ratio between the worst possible Nash equilibrium and the social optimum, as a measure of the effectiveness of the system. Deriving upper and lower bounds for this ratio in a model where several agents share a very simple network leads to some interesting mathematics, results, and open problems.

91A05 2-person games
91A06 \(n\)-person games, \(n>2\)
91A10 Noncooperative games
68M10 Network design and communication in computer systems
91-02 Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance
68-02 Research exposition (monographs, survey articles) pertaining to computer science
Nash eqilibria
Full Text: DOI
[1] B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S. Floyd, V. Jacobson, G. Minshall, C. Partridge, L. Peterson, K. Ramakrishnan, S. Shenker, J. Wroclawski, L. Zhang, Recommendations on queue management and congestion avoidance in the Internet, April 1998. http://info.internet.isi.edu:80/in-notes/rfc/files/rfc2309.txt
[2] Owen, G., Game theory, (1995), Academic Press · Zbl 1284.91004
[3] C.H. Papadimitriou, M. Yannakakis, On complexity as bounded rationality, in: Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, Montreal, Quebec, Canada, 23-25 May 1994, pp. 726-733 · Zbl 1345.68216
[4] Korilis, Y.; Lazar, A., On the existence of equilibria in noncooperative optimal flow control, Journal of the ACM, 42, 3, 584-613, (1995) · Zbl 0885.68015
[5] R. La, V. Anantharam, Optimal routing control: Game theoretic approach, in: Proc. 1997 CDC Conf. · Zbl 1364.91028
[6] Shenker, S.J., Making greed work in networks: A game-theoretic analysis of switch service disciplines, IEEE/ACM transactions on networking, 3, 6, 819-831, (1995)
[7] Shenker, S.; Clark, D.; Estrin, D.; Herzog, S., Pricing in computer network: reshaping the research agenda, Communications policy, 20, 1, (1996)
[8] Korilis, Y.; Lazar, A.; Orda, A., Architecting noncooperative networks, IEEE journal on selected areas of communications, 13, 7, (1995)
[9] Nisan, N.; Roughgarden, T.; Tardos, E.; Vazirani, V.V., Algorithmic game theory, (2007), Cambridge University Press
[10] A. Czumaj, B. Vöcking, Tight bounds for worst-case equilibria, in: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, January 2002, pp. 413-420 · Zbl 1092.91508
[11] E. Koutsoupias, M. Mavronicolas, P. Spirakis, Approximate equilibria and ball fusion, in: Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity, SIROCCO, 2002 · Zbl 1101.68336
[12] Motwani, R.; Raghavan, P., Randomized algorithms, (1995), Cambridge University Press · Zbl 0849.68039
[13] T. Roughgarden, E. Tardos, How bad is selfish routing? in: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, November 12-14, 2000, pp. 93-102
[14] N. Nisan, A. Ronen, Algorithmic mechanism design, in: Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, May 01-04, 1999, Atlanta, Georgia, United States, pp. 129-140 · Zbl 1346.68246
[15] N. Nisan, Algorithms for selfish agents: Mechanism design for distributed computation, in: Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, 1999, pp. 1-15
[16] Cho, Y.; Sahni, S., Bounds for List schedules on uniform processors, SIAM journal on computing, 9, 1, 91-103, (1980) · Zbl 0446.68025
[17] E. Koutsoupias, C.H. Papadimitriou, Worst-case equilibria, in: Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, 1999, pp. 404-413 · Zbl 1099.91501
[18] C.H. Papadimitriou, Algorithms, games, and the Internet, in: Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing, 2001, pp. 749-753 · Zbl 1323.68022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.