canonical proof method is guaranteed to produce an optimal upper bound on the worst-case POA. In this sense, POA bounds for congestion games are “intrinsically robust.”

acknowledgments

This research was supported in part by NSF CAREER Award CCF-0448664, an ONR Young Investigator Award, an AFOSR MURI grant, and an Alfred P. Sloan Fellowship.

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.

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.

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 (S TOC) (2008), 373–382.

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.

5. Chen, x., deng, x., teng, s.h. settling the complexity of two-player nash equilibria. J. ACM 56, 3 (2009).

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.

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 (S TOC) (2005), 67–73.

8. daskalakis, C., goldberg, P. W., Papadimitriou, C.h. the complexity of computing a nash equilibrium. SIAM J. Comput. 39, 1 (2009), 195–259.

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.

10. Foster, d., vohra, r. Calibrated learning and correlated equilibrium. Game Econ. Behav. 21( 1–2) (1997), 40–55.

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.

Cambridge university Press, 2007.

18. olver, n. the price of anarchy and a priority-based model of routing. M.s. thesis, Mcgill university (2006).

19. Perakis, g. the “price of anarchy” under nonlinear and asymmetric costs. Math. Oper. Res. 32, 3 (2007), 614–628.

20. rosenthal, r. W. a class of games possessing pure-strategy nash equilibria. Int. J. Game Theor. 2, 1 (1973), 65–67.

21. roughgarden, t. the price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67, 2 (2003), 341–364.

22. roughgarden, t. intrinsic robustness of the price of anarchy. in 41st ACM Symposium on Theory of Computing (STOC) (2009), 513–522.

23. roughgarden, t. the price of anarchy in games of incomplete information. in 13th ACM Conference on Electronic Commerce (EC)

(2012).

24. roughgarden, t., tardos, É. how bad is selfish routing? J. ACM 49, 2 (2002), 236–259.

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.

 

Tim Roughgarden ( [e-mail]. edu), stanford university, stanford, Ca.

© 2012 aCM 0001-0782/12/07 $15.00

World-Renowned Journals from ACM

ACM publishes over 50 magazines and journals that cover an array of established as well as emerging areas of the computing field.
IT professionals worldwide depend on ACM's publications to keep them abreast of the latest technological developments and industry
news in a timely, comprehensive manner of the highest quality and integrity. For a complete listing of ACM's leading magazines & journals,
including our renowned Transaction Series, please visit the ACM publications homepage: www.acm.org/pubs.

ACM Transactions
on Interactive
Intelligent Systems

ACM Transactions on Interactive Intelligent Systems (TIIS). This quarterly journal publishes papers on research encompassing the design, realization, or evaluation of interactive systems incorporating some form of machine intelligence.

ACM Transactions
on Computation
Theory

ACM Transactions on Computation Theory (ToCT). This quarterly peer-reviewed journal has an emphasis on computational complexity, foundations of cryptography and other computation-based topics in theoretical computer science.

PLEASE CONTAC T ACM MEMBER SERVICES TO PLACE AN ORDER Phone: [phone] (U.S. and Canada)

+ 1.212.626.0500 (Global)

Fax: + 1.212.944.1318

(Hours: 8:30am–4:30pm, Eastern Time) [e-mail] ACM Member Services General Post Office PO Box 30777

New York, N Y 10087-0777 USA Email: Mail:

www.acm.org/pubs