Uniform Mixed Equilibria in Network Congestion Games with Link Failures

References

• [1] Aghassi M, Bertsimas D (2006) Robust game theory. Math. Programming 107(1–2):231–273.Crossref, Google Scholar
• [2] Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Pearson, New York).Google Scholar
• [3] 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.Crossref, Google Scholar
• [4] Anshelevich E, Dasgupta A, Kleinberg JM, Tardos É, Wexler T, Roughgarden T (2008) The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4):1602–1623.Crossref, Google Scholar
• [5] Ashlagi I, Monderer D, Tennenholtz M (2009) Two-terminal routing games with unknown active players. Artificial Intelligence 173(15):1441–1455.Crossref, Google Scholar
• [6] Awerbuch B, Azar Y, Epstein A (2013) The price of routing unsplittable flow. SIAM J. Comput. 42(1):160–177.Crossref, Google Scholar
• [7] Babaioff M, Kleinberg R, Papadimitriou CH (2009) Congestion games with malicious players. Games Econom. Behav. 67(1):22–35.Crossref, Google Scholar
• [8] Beckmann M, McGuire CB, Winsten CB (1956) Studies in the Economics of Transportation (Yale University Press, New Haven, CT).Google Scholar
• [9] Benita F, Bilò V, Monnot B, Piliouras G, Vinci C (2020) Data-driven models of selfish routing: Why price of anarchy does depend on network topology. Chen X, Gravin N, Hoefer M, Mehta R, eds. Proc. 16th Internat. Conf. Web Internet Econom. WINE (Springer, Berlin), 252–265.Google Scholar
• [10] Bhawalkar K, Gairing M, Roughgarden T (2014) Weighted congestion games: Price of anarchy, universal worst-case examples, and tightness. ACM Trans. Econom. Comput. 2(4):14.Google Scholar
• [11] 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.Crossref, Google Scholar
• [12] Bilò V, Caragiannis I, Fanelli A, Monaco G (2013) Improved lower bounds on the price of stability of undirected network design games. Theory Comput. Systems 52(4):668–686.Crossref, Google Scholar
• [13] Bilò V, Flammini M, Moscardelli L (2020) The price of stability for undirected broadcast network design with fair cost allocation is constant. Games Econom. Behav. 123:359–376.Crossref, Google Scholar
• [14] Bilò V, Monaco G, Moscardelli L, Vinci C (2022) Nash social welfare in selfish and online load balancing. ACM Trans. Econom. Comput. 10(2):8.Google Scholar
• [15] Bilò V, Moscardelli L, Vinci C (2018) Uniform mixed equilibria in network congestion games with link failures. Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, eds. Proc. 45th Internat. Colloquium Automata Languages Programming (ICALP) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 146.Google Scholar
• [16] 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 für Informatik), 17.Google Scholar
• [17] Bilò V, Vinci C (2019) Dynamic taxes for polynomial congestion games. ACM Trans. Econom. Comput. 7(3):15.Google Scholar
• [18] Bilò V, Vinci C (2019) On Stackelberg strategies in affine congestion games. Theory Comput. Systems 63(6):1228–1249.Crossref, Google Scholar
• [19] Bilò V, Vinci C (2020) Congestion games with priority-based scheduling. Harks T, Klimm M, eds. Proc. 13th Internat. Sympos. Algorithmic Game Theory SAGT 2020, Lecture Notes in Computer Science, vol. 12283 (Springer, Berlin), 67–82.Google Scholar
• [20] Borodin A, El-Yaniv R (1998) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• [21] Caragiannis I, Flammini M, Kaklamanis C, Kanellopoulos P, Moscardelli L (2011) Tight bounds for selfish and greedy load balancing. Algorithmica 61(3):606–637.Crossref, Google Scholar
• [22] Caragiannis I, Kaklamanis C, Kanellopoulos P (2010) Taxes for linear atomic congestion games. ACM Trans. Algorithms 7(1):13.Crossref, Google Scholar
• [23] Chakrabarty D, Mehta A, Nagarajan V (2005) Fairness and optimality in congestion games. Riedl J, Kearns MJ, Reiter MK, eds. Proc. 6th ACM Conf. Electronic Commerce (ACM, New York), 52–57.Google Scholar
• [24] Christodoulou G, Koutsoupias E (2005) On the price of anarchy and stability of correlated equilibria of linear congestion games. Brodal GS, Leonardi S, eds. Proc. 13th Annual Eur. Sympos. Algorithms (ESA) (Springer, Berlin), vol. 3669, 59–70.Google Scholar
• [25] Christodoulou G, Koutsoupias E (2005) The price of anarchy of finite congestion games. Gabow HN, Fagin R, eds. Proc. 37th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 67–73.Google Scholar
• [26] Cominetti R, Scarsini M, Schröder M, Stier-Moses NE (2019) Price of anarchy in stochastic atomic congestion games with affine costs. Karlin A, Immorlica N, Johari R, eds. Proc. 20th ACM Conf. Econom. Comput. (EC) (ACM, New York), 579–580.Google Scholar
• [27] Fabrikant A, Papadimitriou CH, 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
• [28] Fiat A, Kaplan K, Levy M, Olonetsky S, Shabo R (2006) On the price of stability for designing undirected networks with fair cost allocations. Bugliesi M, Preneel B, Sassone V, Wegener I, eds. Proc. 33rd Internat. Colloquium Automata Languages Programming (Springer, Berlin), 608–618.Google Scholar
• [29] Fotakis D (2010) Stackelberg strategies for atomic congestion games. Theory Comput. Systems 47(1):218–249.Crossref, Google Scholar
• [30] Fotakis D, Kontogiannis SC, Spirakis PG (2005) Selfish unsplittable flows. Theoret. Comput. Sci. 348(2–3):226–239.Crossref, Google Scholar
• [31] Fotakis D, Kontogiannis SC, Spirakis PG (2005) Symmetry in network congestion games: Pure equilibria and anarchy cost. Erlebach T, Persiano G, eds. Proc. 3rd Workshop Approximation Online Algorithms (WAOA) (Springer, Berlin), 161–175.Google Scholar
• [32] Harks T, Klimm M, Möhring R (2011) Characterizing the existence of potential functions in weighted congestion games. Theory Comput. Systems 49(1):46–70.Crossref, Google Scholar
• [33] Karakostas G, Viglas A (2007) Equilibria for networks with malicious users. Math. Programming 110(3):591–613.Crossref, Google Scholar
• [34] Kleer P, Schäfer G (2019) Tight inefficiency bounds for perception-parameterized affine congestion games. Theoret. Comput. Sci. 754:65–87.Crossref, Google Scholar
• [35] Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. Meinel C, Tison S, eds. Proc. 16th Internat. Sympos. Theoret. Aspects Comput. Sci. STACS (Springer, Berlin), 404–413.Google Scholar
• [36] Li J (2009) An O(log(n)/log(log(n))) upper bound on the price of stability for undirected Shapley network design games. Inform. Processing Lett. 109(15):876–878.Crossref, Google Scholar
• [37] Menger K (1927) Zur allgemeinen kurventheorie. Fundamenta Mathematicae 10(1):96–115.Crossref, Google Scholar
• [38] Moscibroda T, Schmid S, Wattenhofer R (2006) When selfish meets evil: Byzantine players in a virus inoculation game. Ruppert E, Malkhi D, eds. Proc. Twenty-Fifth Annual ACM Sympos. Principles Distributed Comput. PODC 06 (ACM, New York), 35–44.Google Scholar
• [39] Nash JF (1950) Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36(1):48–49.Crossref, Google Scholar
• [40] Nash JF (1951) Non-cooperative games. Ann. Math. 54(2):286–295.Crossref, Google Scholar
• [41] Paccagnan D, Chandan R, Ferguson BL, Marden JR (2021) Optimal taxes in atomic congestion games. ACM Trans. Econom. Comput. 9(3):19.Google Scholar
• [42] Paccagnan D, Gairing M (2021) In congestion games, taxes achieve optimal approximation. Birò P, Chawla S, Echenique F, eds. Proc. 22nd ACM Conf. Econom. Comput. EC 2021 (ACM, New York), 743–744.Google Scholar
• [43] Panagopoulou PN, Spirakis PG (2006) Algorithms for pure Nash equilibria in weighted congestion games. ACM J. Experiment. Algorithmms, https://doi.org/10.1145/1187436.1216584.Google Scholar
• [44] Penn M, Polukarov M, Tennenholtz M (2009) Asynchronous congestion games. Lipshteyn M, Levit VE, McConnell RM, eds. Graph Theory, Computational Intelligence and Thought: Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol. 5420 (Springer, Berlin), 41–53.Crossref, Google Scholar
• [45] Penn M, Polukarov M, Tennenholtz M (2009) Congestion games with load-dependent failures: Identical resources. Games Econom. Behav. 67(1):156–173.Crossref, Google Scholar
• [46] Penn M, Polukarov M, Tennenholtz M (2009) Random order congestion games. Math. Oper. Res. 34(3):706–725.Link, Google Scholar
• [47] Penn M, Polukarov M, Tennenholtz M (2009) Taxed congestion games with failures. Ann. Math. Artificial Intelligence 56(2):133–151.Crossref, Google Scholar
• [48] Penn M, Polukarov M, Tennenholtz M (2011) Congestion games with failures. Discrete Appl. Math. 159(15):1508–1525.Crossref, Google Scholar
• [49] Piliouras G, Nikolova E, Shamma JS (2016) Risk sensitivity of price of anarchy under uncertainty. ACM Trans. Econom. Comput. 5(1):5.Google Scholar
• [50] Porter R, Ronen A, Shoham Y, Tennenholtz M (2008) Fault tolerant mechanism design. Artificial Intelligence 172(15):1783–1799.Crossref, Google Scholar
• [51] Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2:65–67.Crossref, Google Scholar
• [52] Roth A (2008) The price of malice in linear congestion games. Papadimitriou CH, Zhang S, eds. Proc. 4th Internat. Workshop Internet Network Econom. WINE 2008 (Springer, Berlin), 118–125.Google Scholar
• [53] Roughgarden T, Tardos E (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
• [54] Zhang Y, Manisterski E, Kraus S, Subrahmanian V, Peleg D (2009) Computing the fault tolerance of multi-agent deployment. Artificial Intelligence 173(3):437–465.Crossref, Google Scholar