Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses

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] Aland S, Dumrauf D, Gairing M, Monien B, Schoppmann F (2011) Exact price of anarchy for polynomial congestion games. SIAM J. Comput. 40(5):1211–1233.Google Scholar
• [3] Awerbuch B, Azar Y, Epstein A (2013) The price of routing unsplittable flow. SIAM J. Comput. 42(1):160–177.Google Scholar
• [4] Bhawalkar K, Gairing M, Roughgarden T (2014) Weighted congestion games: The price of anarchy, universal worst-case examples, and tightness. ACM Trans. Econom. Comput. 2(4):1–23.Google Scholar
• [5] Bilò V (2018) A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. Theory Comput. Systems 62(5):1288–1317.Google Scholar
• [6] Bilò V, Vinci C (2017) On the impact of singleton strategies in congestion games. Pruhs K, Sohler C, eds. 25th Annual Eur. Sympos. Algorithms (ESA) (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 17:1–17:14.Google Scholar
• [7] Caragiannis I, Fanelli A (2019) On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, eds. Proc. 46th Internat. Colloquium Automata Languages Programming (ICALP) (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 133:1–133:12.Google Scholar
• [8] Caragiannis I, Fanelli A, Gravin N, Skopalik A (2011) Efficient computation of approximate pure Nash equilibria in congestion games. Ostrovsky R, ed. Proc. 52nd Annual Symp. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Los Alamitos, CA), 532–541.Google Scholar
• [9] 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
• [10] Chen HL, Roughgarden T (2008) Network design with weighted players. Theory Comput. Systems 45(2):302–324.Google Scholar
• [11] Chien S, Sinclair A (2011) Convergence to approximate Nash equilibria in congestion games. Games Econom. Behav. 71(2):315–327.Google Scholar
• [12] Christodoulou G, Gairing M (2015) Price of stability in polynomial congestion games. ACM Trans. Econom. Comput. 4(2):1–17.Google Scholar
• [13] Christodoulou G, Koutsoupias E (2005) The price of anarchy of finite congestion games. Fagin R, ed. Proc. 37th Annual ACM Symp. Theory Comput. (STOC) (ACM, New York), 67–73.Google Scholar
• [14] Christodoulou G, Koutsoupias E, Spirakis PG (2011) On the performance of approximate equilibria in congestion games. Algorithmica 61(1):116–140. Google Scholar
• [15] Christodoulou G, Gairing M, Giannakopoulos Y, Spirakis PG (2019) The price of stability of weighted congestion games. SIAM J. Comput. 48(5):1544–1582.Google Scholar
• [16] 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-Zentrum fuer Informatik, Dagstuhl, Germany), 32:1–32:18. Google Scholar
• [17] Corless RM, Gonnet GH, Hare DEG, Jeffrey DJ, Knuth DE (1996) On the Lambert W function. Adv. Comput. Math. 5(1):329–359.Google Scholar
• [18] 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.Google Scholar
• [19] Fabrikant A, Papadimitriou C, Talwar K (2004) The complexity of pure Nash equilibria. Babai L, ed. Proc. 36th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 604–612.Google Scholar
• [20] Feldotto M, Gairing M, Skopalik A (2014) Bounding the potential function in congestion games and approximate pure nash equilibria. Liu TY, Qi Q, Ye Y, eds. Proc. 10th Internat. Conf. Web Internet Econom. (WINE) (Springer International Publishing, Cham, Switzerland), 30–43.Google Scholar
• [21] Feldotto M, Gairing M, Kotsialou G, Skopalik A (2017) Computing approximate pure Nash equilibria in Shapley value weighted congestion games. Devanur NR, Lu P, eds. Proc. 13th Internat. Conf. Web Internet Econom. (WINE) (Springer International Publishing, Cham, Switzerland), 191–204. Google Scholar
• [22] Fotakis D, Kontogiannis S, Spirakis P (2005) Selfish unsplittable flows. Theoret. Comput. Sci. 348(2):226–239.Google Scholar
• [23] Gairing M, Schoppmann F (2007) Total latency in singleton congestion games. Deng X, Chung GF, eds. Proc. 3rd Internat. Workshop Internet Network Econom. (WINE) (Springer-Verlag, Berlin, Heidelberg), 381–387.Google Scholar
• [24] Giannakopoulos Y, Noarov G, Schulz AS (2020) Computing approximate equilibria in weighted congestion games via best-responses. Tobias H, Max K, eds. Proc. 13th Symp. Algorithmic Game Theory (SAGT) (Springer International Publishing, Cham, Switzerland), 339.Google Scholar
• [25] Goemans MX, Mirrokni V, Vetta A (2005) Sink equilibria and convergence. Tardos E, ed. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Los Alamitos, CA), 142–151.Google Scholar
• [26] Hansknecht C, Klimm M, Skopalik A (2014) Approximate pure Nash equilibria in weighted congestion games. Jansen K, Rolim JDP, Devanur NR, Moore C, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 242–257.Google Scholar
• [27] Harks T, Klimm M (2012) On the existence of pure Nash equilibria in weighted congestion games. Math. Oper. Res. 37(3):419–436.Google Scholar
• [28] Karlin A, Peres Y (2017) Game Theory, Alive (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [29] Kollias K, Roughgarden T (2015) Restoring pure equilibria to weighted congestion games. ACM Trans. Econom. Comput. 3(4):21:1–21:24.Google Scholar
• [30] Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. Proc. 16th Annual Sympos. Theoret. Aspects Comput. Sci. (STACS), 404–413.Google Scholar
• [31] Libman L, Orda A (2001) Atomic resource sharing in noncooperative networks. Telecomm. Systems 17(4):385–409.Google Scholar
• [32] Monderer D, Shapley LS (1996) Potential games. Games Econom. Behav. 14(1):124–143.Google Scholar
• [33] Nash J (1951) Non-cooperative games. Annals Math. 54(2):286–295.Google Scholar
• [34] Nisan N, Roughgarden T, Tardos É, Vazirani V, eds. (2007) Algorithmic Game Theory (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [35] Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2(1):65–67.Google Scholar
• [36] Roughgarden T (2005) Selfish Routing and the Price of Anarchy (MIT Press, Cambridge, MA).Google Scholar
• [37] Roughgarden T (2015) Intrinsic robustness of the price of anarchy. J. ACM 62(5):32:1–32:42.Google Scholar
• [38] Roughgarden T (2016) Twenty Lectures on Algorithmic Game Theory (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [39] Skopalik A, Vöcking B (2008) Inapproximability of pure Nash equilibria. Dwork C, ed. Proc. 40th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 355–364.Google Scholar