skip to main content
research-article
Free Access

Intrinsic robustness of the price of anarchy

Published:01 July 2012Publication History
Skip Abstract Section

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.

Skip Supplemental Material Section

Supplemental Material

Roughgarden_July2012.mp4

Tim Roughgarden of Stanford University summarizes and provides more details on "Intrinsic Robustness of the Price of Anarchy," his Research Highlights article in the July 2012 Communications of the ACM.

References

  1. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  2. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  3. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  4. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  5. Chen, X., Deng, X., Teng, S.H. Settling the complexity of two-player Nash equilibria. J. ACM 56, 3 (2009). Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  7. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  8. Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H. The complexity of computing a Nash equilibrium. SIAM J. Comput. 39, 1 (2009), 195--259. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  10. Foster, D., Vohra, R. Calibrated learning and correlated equilibrium. Game Econ. Behav. 21(1--2) (1997), 40--55.Google ScholarGoogle ScholarCross RefCross Ref
  11. 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 ScholarGoogle Scholar
  12. Hart, S., Mas-Colell, A. A simple adaptive procedure leading to correlated equilibria. Econometrica 68, 5 (2000), 1127--1150.Google ScholarGoogle ScholarCross RefCross Ref
  13. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  14. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. Nash, J.F. Equilibrium points in N-person games. Proc. Natl. Acad. Sci. 36, 1 (1950), 48--49.Google ScholarGoogle ScholarCross RefCross Ref
  17. Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V., eds. Algorithmic Game Theory. Cambridge University Press, 2007. Google ScholarGoogle ScholarCross RefCross Ref
  18. Olver, N. The price of anarchy and a priority-based model of routing. M.S. thesis, McGill University (2006).Google ScholarGoogle Scholar
  19. Perakis, G. The "price of anarchy" under nonlinear and asymmetric costs. Math. Oper. Res. 32, 3 (2007), 614--628. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Rosenthal, R.W. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theor. 2, 1 (1973), 65--67.Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Roughgarden, T. The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67, 2 (2003), 341--364. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. Roughgarden, T. Intrinsic robustness of the price of anarchy. In 41st ACM Symposium on Theory of Computing (STOC) (2009), 513--522. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. Roughgarden, T. The price of anarchy in games of incomplete information. In 13th ACM Conference on Electronic Commerce (EC) (2012). Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. Roughgarden, T., Tardos, É. How bad is selfish routing? J. ACM 49, 2 (2002), 236--259. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. 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 ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Intrinsic robustness of the price of anarchy

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in

    Full Access

    • Published in

      cover image Communications of the ACM
      Communications of the ACM  Volume 55, Issue 7
      July 2012
      120 pages
      ISSN:0001-0782
      EISSN:1557-7317
      DOI:10.1145/2209249
      Issue’s Table of Contents

      Copyright © 2012 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 1 July 2012

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article
      • Popular
      • Refereed

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    HTML Format

    View this article in HTML Format .

    View HTML Format