Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

References

• [1] Ackermann H, Röglin H, Vöcking B (2008) On the impact of combinatorial structure on congestion games. J. ACM 55(6):1–22.Google Scholar
• [2] Anshelevich E, Dasgupta A, Kleinberg J, Tardos É, Wexler T, Roughgarden T (2008) The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4):1602–1623.Google Scholar
• [3] Caragiannis I, Fanelli A (2021) On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. J. Comput. System Sci. 117:40–48.Crossref, Google Scholar
• [4] Caragiannis I, Fanelli A, Gravin N, Skopalik A (2011) Efficient computation of approximate pure Nash equilibria in congestion games. Proc. 52nd IEEE Annu. Sympos. Foundations Comput. Sci. FOCS (IEEE, Piscataway, NJ), 532–541.Google Scholar
• [5] Caragiannis I, Fanelli A, Gravin N, Skopalik A (2015) Approximate pure Nash equilibria in weighted congestion games: Existence, efficient computation, and structure. ACM Trans. Econom. Comput. 3(1):2:1–2:32.Google Scholar
• [6] Chen HL, Roughgarden T (2008) Network design with weighted players. Theory Comput. Systems 45(2):302.Crossref, Google Scholar
• [7] Christodoulou G, Gairing M (2015) Price of stability in polynomial congestion games. ACM Trans. Econom. Comput. 4(2):1–17.Google Scholar
• [8] Christodoulou G, Koutsoupias E, Spirakis PG (2011) On the performance of approximate equilibria in congestion games. Algorithmica 61(1):116–140.Crossref, Google Scholar
• [9] Christodoulou G, Gairing M, Giannakopoulos Y, Spirakis PG (2019) The price of stability of weighted congestion games. SIAM J. Comput. 48(5):1544–1582.Crossref, Google Scholar
• [10] Christodoulou G, Gairing M, Giannakopoulos Y, Poças D, Waldmann C (2020) Existence and complexity of approximate equilibria in weighted congestion games. Czumaj A, Dawar A, Merelli E, eds. Proc. 47th Internat. Colloquium Automata Languages Programming ICALP (Schloss Dagstuhl—Leibniz Center for Informatics, Wadern, Germany), 32:1–32:18.Google Scholar
• [11] Conitzer V, Sandholm T (2008) New complexity results about Nash equilibria. Games Econom. Behav. 63(2):621–641.Crossref, Google Scholar
• [12] Correa JR, Schulz AS, Stier-Moses NE (2004) Selfish routing in capacitated networks. Math. Oper. Res. 29(4):961–976.Link, Google Scholar
• [13] Dunkel J, Schulz AS (2008) On the complexity of pure-strategy Nash equilibria in congestion and local-effect games. Math. Oper. Res. 33(4):851–868.Link, Google Scholar
• [14] Fabrikant A, Papadimitriou C, Talwar K (2004) The complexity of pure Nash equilibria. Proc. 36th Annu. ACM Sympos. Theory Comput. STOC (Association for Computing Machinery, New York), 604–612.Google Scholar
• [15] Feldotto M, Gairing M, Kotsialou G, Skopalik A (2017) Computing approximate pure Nash equilibria in Shapley value weighted congestion games. Devanur R, Lu P, eds. Web and Internet Economics: WINE 2017, Lecture Notes in Computer Science, vol. 10660 (Springer International Publishing, Cham, Switzerland), 191–204.Crossref, Google Scholar
• [16] Fotakis D, Kontogiannis S, Spirakis P (2005) Selfish unsplittable flows. Theoret. Comput. Sci. 348(2):226–239.Crossref, Google Scholar
• [17] Fotakis D, Kontogiannis S, Koutsoupias E, Mavronicolas M, Spirakis P (2009) The structure and complexity of Nash equilibria for a selfish routing game. Theoret. Comput. Sci. 410(36):3305–3326.Crossref, Google Scholar
• [18] Giannakopoulos Y, Poças D (2020) A unifying approximate potential for weighted congestion games. Preprint, submitted May 20, https://arxiv.org/abs/2005.10101.Google Scholar
• [19] Giannakopoulos Y, Noarov G, Schulz AS (2020) Computing approximate equilibria in weighted congestion games via best-responses. Preprint, submitted November 25, https://arxiv.org/abs/1810.12806.Google Scholar
• [20] Gilboa I, Zemel E (1989) Nash and correlated equilibria: Some complexity considerations. Games Econom. Behav. 1(1):80–93.Crossref, Google Scholar
• [21] Goemans M, Mirrokni V, Vetta A (2005) Sink equilibria and convergence. Proc. 46th Annu. IEEE Sympos. Foundations Comput. Sci. FOCS (IEEE, Piscataway, NJ), 142–151.Google Scholar
• [22] Hansknecht C, Klimm M, Skopalik A (2014) Approximate pure Nash equilibria in weighted congestion games. Jansen K, Rolim JDP, Devanur NR, Moore C, eds. Proc. APPROX/RANDOM (Schloss Dagstuhl—Leibniz Center for Informatics, Wadern, Germany), 242–257.Google Scholar
• [23] Harks T, Klimm M (2012) On the existence of pure Nash equilibria in weighted congestion games. Math. Oper. Res. 37(3):419–436.Link, Google Scholar
• [24] Harks T, Klimm M, Möhring RH (2012) Strong equilibria in games with the lexicographical improvement property. Internat. J. Game Theory 42(2):461–482.Crossref, Google Scholar
• [25] Johnson DS, Papadimitriou CH, Yannakakis M (1988) How easy is local search? J. Comput. System Sci. 37(1):79–100.Crossref, Google Scholar
• [26] Ko KI (1983) On the definitions of some complexity classes of real numbers. Math. Systems Theory 16(1):95–109.Crossref, Google Scholar
• [27] Koutsoupias E, Papadimitriou C (2009) Worst-case equilibria. Comput. Sci. Rev. 3(2):65–69.Crossref, Google Scholar
• [28] Libman L, Orda A (2001) Atomic resource sharing in noncooperative networks. Telecommunication Systems 17(4):385–409.Crossref, Google Scholar
• [29] Nisan N, Roughgarden T, Tardos É, Vazirani V, eds. (2007) Algorithmic Game Theory (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [30] Olver FWJ, Lozier DW, Boisvert RF, Clark CW (2010) NIST Handbook of Mathematical Functions (Cambridge University Press, Cambridge, UK).Google Scholar
• [31] Panagopoulou PN, Spirakis PG (2007) Algorithms for pure Nash equilibria in weighted congestion games. J. Experiment. Algorithmics 11:2.7.Crossref, Google Scholar
• [32] Papadimitriou CH (1994) Computational Complexity (Addison-Wesley, Boston).Google Scholar
• [33] Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theor. 2(1):65–67.Crossref, Google Scholar
• [34] Roughgarden T (2016) Twenty Lectures on Algorithmic Game Theory (Cambridge University Press Cambridge, UK).Crossref, Google Scholar
• [35] Schäffer AA, Yannakakis M (1991) Simple local search problems that are hard to solve. SIAM J. Comput. 20(1):56–87.Crossref, Google Scholar
• [36] Skopalik A, Vöcking B (2008) Inapproximability of pure Nash equilibria. Proc. 40th Annu. ACM Sympos. Theor. Comput. STOC (Association for Computing Machinery, New York), 355–364.Google Scholar