Intrinsic robustness of the price of anarchy

ABSTRACT

The 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 players successfully reach some Nash equilibrium. This drawback motivates the search for inefficiency bounds that apply more generally to weaker notions of equilibria, such as mixed Nash and correlated equilibria; or to sequences of outcomes generated by natural experimentation strategies, such as successive best responses or simultaneous regret-minimization. We prove a general and fundamental connection between the price of anarchy and its seemingly stronger relatives in classes of games with a sum objective. First, we identify a "canonical sufficient condition" for an upper bound of the POA for pure Nash equilibria, which we call a smoothness argument. Second, we show that every bound 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 regret-minimizing players (or "price of total anarchy"). Smoothness arguments also have automatic implications for the inefficiency of approximate and Bayesian-Nash equilibria and, under mild additional assumptions, for bicriteria bounds and for polynomial-length best-response sequences. We also identify classes of games --- most notably, congestion games with cost functions restricted to an arbitrary fixed set --- that are tight, in the sense that smoothness arguments are guaranteed to produce an optimal worst-case upper bound on the POA, even for the smallest set of interest (pure Nash equilibria). Byproducts of our proof of this result include the first tight bounds on the POA in congestion games with non-polynomial cost functions, and the first structural characterization of atomic congestion games that are universal worst-case examples for the POA.

REFERENCES

• 1: S. Aland, D. Dumrauf, M. Gairing, B. Monien, and F. Schoppmann. Exact price of anarchy for polynomial congestion games. In STACS '06, pages 218--229.
• 2: I. Ashlagi, D. Monderer, and M. Tennenholtz. On the value of correlation. Journal of Artificial Intelligence, 2009. To appear.
• 3: R. J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67--96, 1974.
• 4: R. J. Aumann. Correlated equilibrium as an expression of Bayesian rationality. Econometrica, 55(1):1--18, 1987.
• 5: Baruch Awerbuch , Yossi Azar , Amir Epstein , Vahab Seyed Mirrokni , Alexander Skopalik, Fast convergence to nearly optimal solutions in potential games, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386832]
• 6: Baruch Awerbuch , Yossi Azar , Amir Epstein, Large the price of routing unsplittable flow, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060599]
• 7: Avrim Blum , Eyal Even-Dar , Katrina Ligett, Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146392]
• 8: Avrim Blum , MohammadTaghi Hajiaghayi , Katrina Ligett , Aaron Roth, Regret minimization and the price of total anarchy, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374430]
• 9: M. Bradonjić, G. Ercal-Ozkaya, and A. Meyerson. On the price of mediation. Manuscript, 2008.
• 10: Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
• 11: Steve Chien , Alistair Sinclair, Convergence to approximate Nash equilibria in congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 07-09, 2007, New Orleans, Louisiana
• 12: G. Christodoulou and E. Koutsoupias. On the price of anarchy and stability of correlated equilibria of linear congestion games. In ESA '05, pages 59--70.
• 13: George Christodoulou , Elias Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060600]
• 14: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 15: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 16: D. Foster and R. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(1-2):40--55, 1997.
• 17: M. Gairing. Selfish Routing in Networks. PhD thesis, Universitat Paderborn, 2006.
• 18: I. Gilboa and E. Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1(1):80--93, 1989.
• 19: Michel Goemans , Vahab Mirrokni , Adrian Vetta, Sink Equilibria and Convergence, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.142-154, October 23-25, 2005 [doi>10.1109/SFCS.2005.68]
• 20: S. Hart and A. Mas-Colell. A simple adaptive pocedure leading to correlated equilibria. Econometrica, 68(5):1127--1150, 2000.
• 21: E. Koutsoupias, M. Mavronicolas, and P. G. Spirakis. Approximate equilibria and ball fusion. Theory of Computing Systems, 36(6):683--693, 2003.
• 22: E. Koutsoupias and C. H. Papadimitriou. Worst--case equilibria. In STACS '99, pages 404--413.
• 23: D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14(1):124--143, 1996.
• 24: J. F. Nash. Equilibrium points in N-person games. Proceedings of the National Academy of Science, 36(1):48--49, 1950.
• 25: Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
• 26: N. Olver. The price of anarchy and a priority--based model of routing. M.S. thesis, McGill University, 2006.
• 27: Christos H. Papadimitriou , Tim Roughgarden, Computing correlated equilibria in multi-player games, Journal of the ACM (JACM), v.55 n.3, p.1-29, July 2008 [doi>10.1145/1379759.1379762]
• 28: R. W. Rosenthal. A class of games possessing pure--strategy Nash equilibria. International Journal of Game Theory, 2(1):65--67, 1973.
• 29: Timothy Avelin Roughgarden , Eva Tardos, Selfish routing, Cornell University, Ithaca, NY, 2002
• 30: Tim Roughgarden, The price of anarchy is independent of the network topology, Journal of Computer and System Sciences, v.67 n.2, p.341-364, September 2003 [doi>10.1016/S0022-0000(03)00044-8]
• 31: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 32: T. Roughgarden and É. Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior, 49(2):389--403, 2004.
• 33: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002
• 34: H. P. Young. Strategic Learning and Its Limits. Oxford University Press, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Economics, Theory

Keywords:
congestion games, nash equilibria, price of anarchy, regret-minimizat