Exact Price of Anarchy for Polynomial Congestion Games
- 1 January 2011
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 40 (5), 1211-1233
- https://doi.org/10.1137/090748986
Abstract
We show exact values for the worst-case price of anarchy in weighted and unweighted (atomic unsplittable) congestion games, provided that all cost functions are bounded-degree polynomials with nonnegative coefficients. The given values also hold for weighted and unweighted network congestion games.Keywords
This publication has 23 references indexed in Scilit:
- Nash equilibria in discrete routing games with convex latency functionsJournal of Computer and System Sciences, 2008
- A new model for selfish routingTheoretical Computer Science, 2008
- Tight bounds for worst-case equilibriaACM Transactions on Algorithms, 2007
- The price of anarchy for polynomial social costTheoretical Computer Science, 2006
- Tradeoffs in worst-case equilibriaTheoretical Computer Science, 2006
- Selfish unsplittable flowsTheoretical Computer Science, 2005
- How bad is selfish routing?Journal of the ACM, 2002
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973
- ROAD PAPER. SOME THEORETICAL ASPECTS OF ROAD TRAFFIC RESEARCH.Proceedings of the Institution of Civil Engineers, 1952
- Non-Cooperative GamesAnnals of Mathematics, 1951