×

How to find Nash equilibria with extreme total latency in network congestion games? (English) Zbl 1189.91039

Summary: We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyze how it is influenced by the graph topology and the number of users. In our context best and worst equilibria are those with minimum or maximum total latency, respectively. We establish that both problems can be solved by a greedy type algorithm equipped with a suitable tie breaking rule on extension-parallel graphs. On series-parallel graphs finding a worst Nash equilibrium is NP-hard for two or more users while finding a best one is solvable in polynomial time for two users and NP-hard for three or more. additionally we establish NP-hardness in the strong sense for the problem of finding a worst Nash equilibrium on a general acyclic graph.

MSC:

91A43 Games involving graphs
91A10 Noncooperative games
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Awerbuch B, Azar Y, Epstein A (2005) The price of routing unsplittable flow. In: Proceedings of 37th annual ACM symposium on the theory of computing (STOC), pp 57–66 · Zbl 1192.90099
[2] Christodoulou G, Koutsoupias E (2005) The price of anarchy of finite congestion games. In: Proceedings of the 37th annual ACM symposium on the theory of computing (STOC), pp 67–73 · Zbl 1192.91039
[3] Czumaj A, Vöcking B (2002) Tight bounds for worst-case equilibria. In: Proceedings of the 13th annual ACM–SIAM symposium on discrete algorithms (SODA), pp 413–420 · Zbl 1092.91508
[4] Epstein A, Feldman M, Mansour Y (2007) Efficient graph topologies in network routing games. In: Joint workshop on economics of networked systems and incentive-based computing
[5] Fabrikant A, Papadimitriou C, Talwar K (2004) The complexity of pure nash equilibria. In: Proceedings of the 36th annual ACM symposium on the theory of computing (STOC), pp 604–612 · Zbl 1192.91042
[6] Feldmann R, Gairing M, Lücking T, Monien B, Rode M (2003) Nashification and the coordination ratio for a selfish routing game. In: Baeten JCM, Lenstra JK, Parrow J, Woeginger GJ (eds) Proceedings of the 30th international colloquium on automata, languages and programming (ICALP), LNCS vol. 2719. Springer, NY, pp 514–526 · Zbl 1060.68531
[7] Fischer S, Vöcking B (2007) On the structure and complexity of worst-case equilibria. Theor Comput Sci 378(2): 165–174 · Zbl 1121.91058 · doi:10.1016/j.tcs.2007.02.019
[8] Fotakis D, Kontogiannis S, Koutsoupias E, Mavronicolas M, Spirakis P (2002) The structure and complexity of Nash equilibria for a selfish routing game. In: Widmayer P, Ruiz FT, Bueno RM, Hennessy M, Eidenbenz S, Conejo R (eds) Proceedings of the 29th international colloquium on automata, languages and programming (ICALP), LNCS vol. 2380. Springer, NY, pp 123–134
[9] Fotakis D, Kontogiannis S, Spirakis P (2005) Symmetry in network congestion games: pure equilibria and anarchy cost. In: Erlebach T, Persiano G (eds) Proceedings of the 3rd workshop on approximation and online algorithms (WAOA), LNCS vol. 3879. Springer, NY, pp 161–175 · Zbl 1177.90070
[10] Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. A series of books in the mathematical sciences. W.H. Freeman, San Francisco
[11] Gassner E, Hatzl J, Krumke SO, Sperber H, Woeginger GJ (2008) How hard is it to find extreme Nash equilibria in network congestion games. In: Papadimitriou C, Zhang S (eds) Proceedings of the 4th international workshop on internet and network economics (WINE), LNCS vol. 5385, pp 82–93 · Zbl 1175.91044
[12] Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. In: Proceedings of the 16th international symposium on theoretical aspects of computer science (STACS), LNCS vol. 1563, pp 404–413 · Zbl 1099.91501
[13] Mavronicolas M, Spirakis P (2001) The price of selfish routing. In: Proceedings of the 33rd annual ACM symposium on the theory of computing (STOC), pp 510–519 · Zbl 1323.91006
[14] Papadimitriou C (2001) Algorithms, games, and the internet. In: Proceedings of the 33rd annual ACM symposium on the theory of computing (STOC), pp 749–753 · Zbl 1323.68022
[15] Pigou AC (1920) The economics of welfare. Macmillan, NY
[16] Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Int J Game Theory 2(1): 65–67 · Zbl 0259.90059 · doi:10.1007/BF01737559
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.