Worst-case equilibria
作者： Elias Koutsoupias , Christos Papadimitriou
关键词: Simple (abstract algebra) 、 Parallel algorithm 、 Nash equilibrium 、 Mathematical economics 、 Upper and lower bounds 、 Price of anarchy 、 Congestion game 、 Mathematics 、 Measure (mathematics) 、 Game theory
摘要: In a system in which noncooperative agents share common resource, we propose the ratio between worst possible Nash equilibrium and social optimum as measure of effectiveness system. Deriving upper lower bounds for this model several very simple network leads to some interesting mathematics, results, open problems.
springer.com
core.ac.uk
springerlink.com参考文章(11)
Meera Sitharam, Kihong Park, Shaogang Chen, Quality of Service Provision in Noncooperative Network Environments ,(1997)
Geoffrey R. Grimmett, David Stirzaker, Probability and random processes ,(1982)
Teofilo Gonzalez, Oscar H. Ibarra, Sartaj Sahni, Bounds for LPT Schedules on Uniform Processors SIAM Journal on Computing. ,vol. 6, pp. 155- 166 ,(1977) , 10.1137/0206013
Scott Shenker, David Clark, Deborah Estrin, Shai Herzog, Pricing in computer networks: Reshaping the research agenda Telecommunications Policy. ,vol. 20, pp. 183- 201 ,(1996) , 10.1016/0308-5961(96)00002-X
Kihong Park, Meera Sitharam, Shaogang Chen, Quality of service provision in noncooperative networks: heterogenous preferences, multi-dimensional QoS vectors, and burstiness Proceedings of the first international conference on Information and computation economies. pp. 111- 127 ,(1998) , 10.1145/288994.289022
S.J. Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines IEEE ACM Transactions on Networking. ,vol. 3, pp. 819- 831 ,(1995) , 10.1109/90.477727
Christos H. Papadimitriou, Mihalis Yannakakis, On complexity as bounded rationality (extended abstract) Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94. pp. 726- 733 ,(1994) , 10.1145/195058.195445
Y.A. Korilis, A.A. Lazar, A. Orda, Architecting noncooperative networks IEEE Journal on Selected Areas in Communications. ,vol. 13, pp. 1241- 1251 ,(1995) , 10.1109/49.414643
J. Wroclawski, S. Shenker, B. Braden, J. Crowcroft, V. Jacobson, C. Partridge, D. Estrin, B. Davie, K. Ramakrishnan, D. Clark, L. Peterson, S. Floyd, L. Zhang, G. Minshall, S. Deering, Recommendations on Queue Management and Congestion Avoidance in the Internet Recommendations on Queue Management and Congestion Avoidance in the Internet. ,vol. 2309, pp. 1- 17 ,(1998)
Yannis A. Korilis, Aurel A. Lazar, On the existence of equilibria in noncooperative optimal flow control Journal of the ACM. ,vol. 42, pp. 584- 613 ,(1995) , 10.1145/210346.210415