On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games

References

• Ackermann H., Röglin H., Vöcking B. On the impact of combinatorial structure on congestion games. Proc. 47th Ann. IEEE Sympos. Foundations Comput. Sci. (2006a) Berkeley, CA:613–622Crossref, Google Scholar
• Ackermann H., Röglin H., Vöcking B., Spirakis P. G., Mavronicolas M., Kontogiannis S. C. Pure Nash equilibria in player-specific and weighted congestion games. Proc. 2nd Internat. Workshop on Internet and Network Econom. Lecture Notes in Computer Science (2006b) 4286(Springer, Berlin) 50–61Crossref, Google Scholar
• Aland S., Dumrauf D., Gairing M., Monien B., Schoppmann F., Durand B., Thomas W. Exact price of anarchy for polynomial congestion games. Proc. 23rd Internat. Sympos. Theoretical Aspects of Comput. Sci. Lecture Notes in Computer Science (2006) 3884(Springer, Berlin) 218–229Crossref, Google Scholar
• Àlvarez C., Gabarró J., Serna M. J., Jedrzejowicz J., Szepietowski A. Pure Nash equilibria in games with a large number of actions. Proc. 30th Internat. Sympos. Math. Foundations of Comput. Sci. Lecture Notes in Computer Science (2005) 3618(Springer, Berlin) 95–106Crossref, Google Scholar
• Awerbuch B., Azar Y., Epstein A. The price of routing unsplittable flow. Proc. 37th Annual ACM Sympos. Theory Comput. (2005) Baltimore:57–66Google Scholar
• Brandt F., Fischer F., Holzer M., Thomas W., Weil P. Symmetries and the complexity of pure Nash equilibrium. Proc. 24th Internat. Sympos. Theoretical Aspects Comput. Sci. Lecture Notes in Computer Science (2007) 4393(Springer, Berlin) 212–223Crossref, Google Scholar
• Chen X., Deng X. 3-Nash is PPAD-complete. (2005) . Technical Report 05-134, Electronic Colloquium in Computational ComplexityGoogle Scholar
• Chen X., Deng X. Settling the complexity of two-player Nash equilibrium. Proc. 47th Annual IEEE Sympos. Foundations Comput. Sci. (2006) Berkeley, CA:261–272Crossref, Google Scholar
• Daskalakis C., Papadimitriou C. H. Three-player games are hard. (2005) . Technical Report 05-139, Electronic Colloquium in Computational ComplexityGoogle Scholar
• Daskalakis C., Goldberg P. W., Papadimitriou C. H. The complexity of computing a Nash equilibrium. Proc. 38th Annual ACM Sympos. Theory Comput. (2006) Seattle:71–78Crossref, Google Scholar
• Dunkel J., Schulz A. S., Spirakis P. G., Mavronicolas M., Kontogiannis S. C. On the complexity of pure-strategy Nash equilibria in congestion and local-effect games. Proc. 2nd Internat. Workshop on Internet and Network Econom. Lecture Notes in Computer Science (2006) 4286(Springer, Berlin) 62–73Crossref, Google Scholar
• Fabrikant A., Papadimitriou C. H., Talwar K. The complexity of pure Nash equilibria. Proc. 36th Annual ACM Sympos. Theory Comput. (2004) Chicago, IL:604–612Crossref, Google Scholar
• Fischer F., Holzer M., Katzenbeisser S. The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria. Inform. Processing Lett. (2006) 99:239–245Crossref, Google Scholar
• Fischer S. T. A note on the complexity of local search problems. Inform. Processing Lett. (1995) 53(2):69–75Crossref, Google Scholar
• Fortune S., Hopcroft J. E., Wyllie J. The directed subgraph homeomorphism problem. Theoret. Comput. Sci. (1980) 10(2):111–121Crossref, Google Scholar
• Fotakis D., Kontogiannis S., Spirakis P. Selfish unsplittable flows. Theoret. Comput. Sci. (2005) 348(2):226–239Crossref, Google Scholar
• Gairing M., Monien B., Tiemann K., Bugliesi M., Preneel B., Sassone V., Wegener I. Routing (un-) splittable flow in games with player-specific linear latency functions. Proc. 33rd Internat. Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science (2006) 4051(Springer, Berlin) 501–512Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractibility. A Guide to the Theory of NP-Completeness (1979) (Freeman and Company, New York) Google Scholar
• Goemans M. X., Mirrokni V., Vetta A. Sink equilibria and convergence. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (2005) Pittsburgh:142–154Crossref, Google Scholar
• Goldberg P. W., Papadimitriou C. H. Reducibility among equilibrium problems. Proc. 38th Annual ACM Sympos. Theory Comput. (2006) Seattle:61–70Crossref, Google Scholar
• Gottlob G., Greco G., Scarcello F. Pure Nash equilibria: Hard and easy games. J. Artificial Intelligence Res. (2005) 24:357–406Crossref, Google Scholar
• Ieong S., McGrew R., Nudelman E., Shoham Y., Sun Q. Fast and compact: A simple class of congestion games. Proc. 20th National Conf. Artificial Intelligence and the 17th Innovative Appl. Artificial Intelligence Conf. (2005) Pittsburgh:489–494Google Scholar
• Johnson D. S., Papadimitriou C. H., Yannakakis M. How easy is local search? J. Comput. System Sci. (1988) 37:79–100Crossref, Google Scholar
• Leyton-Brown K., Tennenholtz M. Local-effect games. Proc. 18th Internat. Joint Conf. Artificial Intelligence (2003) Acapulco, Mexico:772–780Google Scholar
• Libman L., Orda A. Atomic resource sharing in noncooperative networks. Telecommunication Systems (2001) 17:385–409Crossref, Google Scholar
• Meyers C. A., Schulz A. S. The complexity of congestion games. (2008) . Working paper, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Milchtaich I. Congestion games with player-specific payoff functions. Games Econom. Behav. (1996) 13:111–124Crossref, Google Scholar
• Milchtaich I., Spirakis P. G., Mavronicolas M., Kontogiannis S. C. The equilibrium existence problem in finite network congestion games. Proc. 2nd Internat. Workshop on Internet and Network Econom. Lecture Notes in Computer Science (2006) 4286(Springer, Berlin) 87–98Crossref, Google Scholar
• Monderer D., Shapley L. S. Potential games. Games Econom. Behav. (1996) 14:124–143Crossref, Google Scholar
• Nash J. F. Non-cooperative games. Ann. Math. (1951) 54:286–295Crossref, Google Scholar
• Rosenthal R. W. A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory (1973a) 2:65–67Crossref, Google Scholar
• Rosenthal R. W. The network equilibrium problem in integers. Networks (1973b) 3:53–59Crossref, Google Scholar
• Schäffer A. A., Yannakakis M. Simple local search problems that are hard to solve. SIAM J. Comput. (1991) 20:56–87Crossref, Google Scholar
• Schoenebeck G., Vadhan S. P. The computational complexity of Nash equilibria in concisely represented games. Proc. 7th ACM Conf. Electronic Commerce (2006) Ann Arbor, MI:270–279Crossref, Google Scholar
• Shor M. Matching pennies. (2005) . Dictionary of Game Theory Terms, Game Theory .net. http://www.gametheory.net/dictionary/Games/MatchingPennies.htmlGoogle Scholar
• Yannakakis M., Aarts E., Lenstra J. K. Computational complexity. Local Search in Combinatorial Optimization (1997) (John Wiley and Sons, New York) 19–55Chapter 2Google Scholar