On the Existence of Pure Nash Equilibria in Weighted Congestion Games

References

• Ackermann H, Röglin H, Vöcking B. Pure Nash equilibria in player-specific and weighted congestion games. Theoret. Comput. Sci. (2009) 410(17):1552–1563Crossref, Google Scholar
• Ackermann H, Skopalik A, Deng X, Graham F. On the complexity of pure Nash equilibria in player-specific network congestion games. Proc. 3rd Internat. Workshop on Internet and Network Econom., LNCS (2007) 4858:419–430Crossref, 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 Comput. Sci., LNCS (2006) 3884:218–229Crossref, Google Scholar
• Andelman N, Feldman M, Mansour Y. Strong price of anarchy. Games Econom. Behav. (2009) 65(2):289–317Crossref, Google Scholar
• Anshelevich E, Dasgupta A, Kleinberg J, Tardos É, Wexler T, Roughgarden T. The price of stability for network design with fair cost allocation. SIAM J. Comput. (2008) 38(4):1602–1623Crossref, Google Scholar
• Awerbuch B, Azar Y, Epstein A, Gabow HN, Fagin R. The price of routing unsplittable flow. Proc. 37th Annual ACM Sympos. Theory Comput. (2005) (ACM Press)57–66Google Scholar
• Balakrishnan VK. Introductory Discrete Mathematics (1996) (Dover Publications, New York) Google Scholar
• Bhaskar U, Fleischer L, Hoy D, Huang C, Mathieu C. Equilibria of atomic flow games are not unique. Proc. 20th Annual ACM-SIAM Sympos. Discrete Algorithms (2009) (SIAM, Philadelphia) 748–757Crossref, Google Scholar
• Bhawalkar K, Gairing M, Roughgarden T, de Berg M, Meyer U. Weighted congestion games: Price of anarchy, universal worst-case examples, and tightness. Proc. 18th Annual Eur. Sympos. Algorithms, Part II, LNCS (2010) 6347:17–28Crossref, Google Scholar
• Bureau of Public Roads Traffic assignment manual. (1964) . U.S. Department of Commerce, Urban Planning Division, Washington, DCGoogle Scholar
• Chen H-L, Roughgarden T. Network design with weighted players. Theory Comput. Syst. (2009) 45(2):302–324Crossref, Google Scholar
• Christodoulou G, Koutsoupias E, Gabow HN, Fagin R. The price of anarchy of finite congestion games. Proc. 37th Annual ACM Sympos. Theory Comput. (2005) 67–73Crossref, Google Scholar
• Dunkel J, Schulz A. On the complexity of pure-strategy Nash equilibria in congestion and local-effect games. Math. Oper. Res. (2008) 33(4):851–868Link, Google Scholar
• Even-Dar E, Kesselman A, Mansour Y. Convergence time to Nash equilibrium in load balancing. ACM Trans. Algorithms (2007) 3(3):32Crossref, Google Scholar
• Fotakis D, Kontogiannis S, Koutsoupias E, Mavronicolas M, Spirakis P, Widmayer P, Triguero F, Morales R, Hennessy M, Eidenbenz S, Conejo R. The structure and complexity of Nash equilibria for a selfish routing game. Proc. 29th Internat. Colloquium on Automata, Languages, and Programming, LNCS (2002) 2380:123–134Crossref, Google Scholar
• Fotakis D, Kontogiannis S, Spirakis P. Selfish unsplittable flows. Theoret. Comput. Sci. (2005) 348(2--3):226–239Crossref, Google Scholar
• Fotakis D, Kontogiannis S, Spirakis P, Bugliesi M, Preneel B, Sassone V, Wegener I. Atomic congestion games among coalitions. Proc. 33rd Internat. Colloquium on Automata, Languages, and Programming, LNCS (2006) 4052:572–583Crossref, 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, LNCS (2006) 4051:501–512Crossref, Google Scholar
• Goemans M, Mirrokni V, Vetta A. Sink equilibria and convergence. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (2005) 142–154Crossref, Google Scholar
• Harks T, Klimm M, Abramsky S, Gavoille C, Kirchner C, Meyer auf der Heide F, Spirakis P. On the existence of pure Nash equilibria in weighted congestion games. Proc. 37th Internat. Colloquium on Automata, Languages, and Programming, LNCS (2010) 6198:79–89Crossref, Google Scholar
• Harks T, Klimm M, Möhring R, Leonardi S. Strong Nash equilibria in games with the lexicographical improvement property. Proc. 5th Internat. Workshop on Internet and Network Econom., LNCS (2009) 5929:463–470Crossref, Google Scholar
• Harks T, Klimm M, Möhring R. Characterizing the existence of potential functions in weighted congestion games. Theory Comput. Systems (2011) 49(1):46–70Crossref, 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) 489–494Google Scholar
• Libman L, Orda A. Atomic resource sharing in noncooperative networks. Telecommun. Syst. (2001) 17(4):385–409Crossref, Google Scholar
• Milchtaich I. Congestion games with player-specific payoff functions. Games Econom. Behav. (1996) 13(1):111–124Crossref, Google Scholar
• Milchtaich I. Topological conditions for uniqueness of equilibrium in networks. Math. Oper. Res. (2005) 30(1):225–244Link, Google Scholar
• Milchtaich I, Mavronicolas M, Kontogiannis S. The equilibrium existence problem in finite network congestion games. Proc. 2nd Internat. Workshop on Internet and Network Econom., LNCS (2006) 4286:87–98Crossref, Google Scholar
• Monderer D, Shapley L. Potential games. Games Econom. Behav. (1996) 14(1):124–143Crossref, Google Scholar
• Orda A, Rom R, Shimkin N. Competitive routing in multi-user communication networks. IEEE Trans. Networking (1993) 1:510–521Crossref, Google Scholar
• Panagopoulou P, Spirakis P. Algorithms for pure Nash equilibria in weighted congestion games. ACM J. Exp. Algorithmics (2006) 11(2.7):1–19Google Scholar
• Richman O, Shimkin N. Topological uniqueness of the Nash equilibrium for selfish routing with atomic users. Math. Oper. Res. (2007) 32(1):215–232Link, Google Scholar
• Rosenthal R. A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory (1973) 2(1):65–67Crossref, Google Scholar
• Rosenthal R. The network equilibrium problem in integers. Networks (1973) 3(1):53–59Crossref, Google Scholar
• Roughgarden T, Mitzenmacher M. Intrinsic robustness of the price of anarchy. Proc. 41st Annual ACM Sympos. Theory Comput. (2009) 513–522Crossref, Google Scholar
• Roughgarden T, Tardos É. How bad is selfish routing? J. ACM (2002) 49(2):236–259Crossref, Google Scholar
• Rozenfeld O, Tennenholtz M, Spirakis P, Mavronicolas M, Kontogiannis S. Strong and correlated strong equilibria in monotone congestion games. Proc. 2nd Internat. Workshop on Internet and Network Econom., LNCS (2006) 4286:74–86Crossref, Google Scholar
• Yang H, Zhang X. Existence of anonymous link tolls for system optimum on networks with mixed equilibrium behaviors. Transportation Res. Part B: Methodological (2008) 42(2):99–112Crossref, Google Scholar