Abstract
The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that of an optimal outcome, quantifies the inefficiency of selfish behavior. Remarkably good bounds on this measure are known for a wide range of application domains. However, such bounds are meaningful only if a game's participants successfully reach a Nash equilibrium. This drawback motivates inefficiency bounds that apply more generally to weaker notions of equilibria, such as mixed Nash equilibria and correlated equilibria, or to sequences of outcomes generated by natural experimentation strategies, such as simultaneous regret-minimization.
We prove a general and fundamental connection between the price of anarchy and its seemingly more general relatives. First, we identify a "canonical sufficient condition" for an upper bound on the price of anarchy of pure Nash equilibria, which we call a smoothness argument. Second, we prove an "extension theorem": every bound on the price of anarchy that is derived via a smoothness argument extends automatically, with no quantitative degradation in the bound, to mixed Nash equilibria, correlated equilibria, and the average objective function value of every no-regret sequence of joint repeated play. Third, we prove that in routing games, smoothness arguments are "complete" in a proof-theoretic sense: despite their automatic generality, they are guaranteed to produce an optimal worst-case upper bound on the price of anarchy.
Supplemental Material
- Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F. Exact price of anarchy for polynomial congestion games. SIAM J. Comput. 40, 5 (2011), 1211--1233. Google ScholarDigital Library
- Awerbuch, B., Azar, Y., Epstein, A. The price of routing unsplittable flow. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC) (2005), 57--66. Google ScholarDigital Library
- Blum, A., Hajiaghayi, M., Ligett, K., Roth, A. Regret minimization and the price of total anarchy. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC) (2008), 373--382. Google ScholarDigital Library
- Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M., Lucier, B., Leme, R.P., Tardos, É. On the efficiency of equilibria in generalized second price auctions. Submitted 2012. Earlier versions appeared in FOCS, '10 and EC, '11. Google ScholarDigital Library
- Chen, X., Deng, X., Teng, S.H. Settling the complexity of two-player Nash equilibria. J. ACM 56, 3 (2009). Google ScholarDigital Library
- Christodoulou, G., Koutsoupias, E. On the price of anarchy and stability of correlated equilibria of linear congestion games. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA), volume 3669 of Lecture Notes in Computer Science (2005), 59--70. Google ScholarDigital Library
- Christodoulou, G., Koutsoupias, E. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC) (2005), 67--73. Google ScholarDigital Library
- Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H. The complexity of computing a Nash equilibrium. SIAM J. Comput. 39, 1 (2009), 195--259. Google ScholarDigital Library
- Fabrikant, A., Papadimitriou, C.H., Talwar, K. The complexity of pure Nash equilibria. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC) (2004), 604--612. Google ScholarDigital Library
- Foster, D., Vohra, R. Calibrated learning and correlated equilibrium. Game Econ. Behav. 21(1--2) (1997), 40--55.Google ScholarCross Ref
- Harks, T. Stackelberg strategies and collusion in network games with splittable flow. Proceedings of the 6th International Workshop on Approximation and Online Algorithms (WAOA'08), E. Bampis and M. Skutella, eds. Volume 5426 of LNCS (2008), 133--146.Google Scholar
- Hart, S., Mas-Colell, A. A simple adaptive procedure leading to correlated equilibria. Econometrica 68, 5 (2000), 1127--1150.Google ScholarCross Ref
- Kleinberg, R.D., Piliouras, G., Tardos, É. Multiplicative updates outperform generic no-regret learning in congestion games. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC) (2009), 533--542. Google ScholarDigital Library
- Koutsoupias, E., Papadimitriou, C.H. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1563 of Lecture Notes in Computer Science (1999), 404--413. Google ScholarDigital Library
- Nadav, U., Roughgarden, T. The limits of smoothness: A primal-dual framework for price of anarchy bounds. In The 6th International Workshop on Internet and Network Economies (WINE) (2010), 319--326. Google ScholarDigital Library
- Nash, J.F. Equilibrium points in N-person games. Proc. Natl. Acad. Sci. 36, 1 (1950), 48--49.Google ScholarCross Ref
- Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V., eds. Algorithmic Game Theory. Cambridge University Press, 2007. Google ScholarCross Ref
- Olver, N. The price of anarchy and a priority-based model of routing. M.S. thesis, McGill University (2006).Google Scholar
- Perakis, G. The "price of anarchy" under nonlinear and asymmetric costs. Math. Oper. Res. 32, 3 (2007), 614--628. Google ScholarDigital Library
- Rosenthal, R.W. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theor. 2, 1 (1973), 65--67.Google ScholarDigital Library
- Roughgarden, T. The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67, 2 (2003), 341--364. Google ScholarDigital Library
- Roughgarden, T. Intrinsic robustness of the price of anarchy. In 41st ACM Symposium on Theory of Computing (STOC) (2009), 513--522. Google ScholarDigital Library
- Roughgarden, T. The price of anarchy in games of incomplete information. In 13th ACM Conference on Electronic Commerce (EC) (2012). Google ScholarDigital Library
- Roughgarden, T., Tardos, É. How bad is selfish routing? J. ACM 49, 2 (2002), 236--259. Google ScholarDigital Library
- Vetta, A. Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS) (2002), 416--425. Google ScholarDigital Library
Index Terms
Intrinsic robustness of the price of anarchy
Recommendations
Intrinsic Robustness of the Price of Anarchy
The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that of an optimal outcome, quantifies the inefficiency of selfish behavior. Remarkably good bounds on this measure are known for a ...
Intrinsic robustness of the price of anarchy
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingThe price of anarchy (POA) is a worst-case measure of the inefficiency of selfish behavior, defined as the ratio of the objective function value of a worst Nash equilibrium of a game and that of an optimal outcome. This measure implicitly assumes that ...
Intrinsic Robustness of the Price of Anarchy: Abstract of the Kalai Prize Talk
EC '16: Proceedings of the 2016 ACM Conference on Economics and ComputationThe price of anarchy is a measure of the inefficiency of selfish behavior that has been successfully analyzed in many applications, including network routing, resource allocation, auctions, and even models of basketball. It is defined as the worst-case ...
Comments