×

Uniform mixed equilibria in network congestion games with link failures. (English) Zbl 1499.68029

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 146, 14 p. (2018).
Summary: Motivated by possible applications in fault-tolerant routing, we introduce the notion of uniform mixed equilibria in network congestion games with adversarial link failures, where players need to route traffic from a source to a destination node. Given an integer \(\rho \ge 1\), a \(\rho\)-uniform mixed strategy is a mixed strategy in which a player plays exactly rho edge disjoint paths with uniform probabilities, so that a \(\rho\)-uniform mixed equilibrium is a tuple of \(\rho\)-uniform mixed strategies, one for each player, in which no player can lower her cost by deviating to another \(\rho\)-uniform mixed strategy. For games with weighted players and affine latency functions, we show existence of rho-uniform mixed equilibria and provide a tight characterization of their price of anarchy. For games with unweighted players, instead, we extend the existential guarantee to any class of latency functions and, restricted to games with affine latencies, we derive a tight characterization of both the prices of anarchy and stability.
For the entire collection see [Zbl 1392.68012].

MSC:

68M10 Network design and communication in computer systems
68M15 Reliability, testing and fault tolerance of networks and computer systems
91A43 Games involving graphs
91A80 Applications of game theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. {\it Network flows - theory, algorithms and} {\it applications}. Prentice Hall, 1993. · Zbl 1201.90001
[2] E. Anshelevich, A. Dasgupta, J. M. Kleinberg, É. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation.{\it SIAM J. Comput.}, 38(4):1602-1623, 2008. · Zbl 1173.91321
[3] B. Awerbuch, Y. Azar, and A. Epstein. The price of routing unsplittable flow. In {\it Proceedings} {\it of the Thirty-seventh Annual ACM Symposium on Theory of Computing}, STOC, pages 57- 66, 2005. · Zbl 1192.90099
[4] M. Babaioff, R. Kleinberg, and C. H. Papadimitriou. Congestion games with malicious players. {\it Games and Economic Behavior}, 67(1):22-35, 2009. · Zbl 1173.91301
[5] K. Bhawalkar, M. Gairing, and T. Roughgarden. Weighted congestion games: price of anarchy, universal worst-case examples, and tightness. {\it ACM Transactions on Economics} {\it and Computation}, 2(4):1-23, 2014.
[6] V. Bilò. A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. In {\it Proceedings of the 10th Workshop on Approximation and Online} {\it Algorithms (WAOA)}, volume 7846 of {\it LNCS}, pages 229-241, 2012.
[7] V. Bilò, I. Caragiannis, A. Fanelli, and G. Monaco. Improved lower bounds on the price of stability of undirected network design games. {\it Theory Comput. Syst.}, 52(4):668-686, 2013. · Zbl 1273.90168
[8] V. Bilò, M. Flammini, and L. Moscardelli. The price of stability for undirected broadcast network design with fair cost allocation is constant. In {\it Proceedings of the 54th Annual} {\it IEEE Symposium on Foundations of Computer Science}, FOCS, pages 638-647, 2013.
[9] V. Bilò and C. Vinci. On Stackelberg strategies in affine congestion games. In {\it Proceedings} {\it of the 11th Conference on Web and Internet Economics (WINE)}, LNCS“ volume = ”9470, pages 132-145, 2015. · Zbl 1404.91045
[10] V. Bilò and C. Vinci. Dynamic taxes for polynomial congestion games. In {\it Proceedings of} {\it the 2016 ACM Conference on Economics and Computation}, EC ’16, pages 839-856, 2016.
[11] I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, and L. Moscardelli. Tight bounds for selfish and greedy load balancing. {\it Algorithmica}, 61(3):606-637, 2011. · Zbl 1237.91049
[12] I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos. Taxes for linear atomic congestion games. {\it ACM Trans. Algorithms}, 7(1):13:1-13:31, 2010. · Zbl 1295.91006
[13] G. Christodoulou and E. Koutsoupias. On the price of anarchy and stability of correlated equilibria of linear congestion games. In {\it Proceedings of the 13th Annual European} {\it Symposium on Algorithms (ESA)}, volume 3669 of {\it LNCS}, pages 59-70, 2005. · Zbl 1162.91305
[14] G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In {\it Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC)}, pages 67-73, 2005. · Zbl 1192.91039
[15] J. de Jong, M. Klimm, and M. Uetz. Efficiency of equilibria in uniform matroid congestion games. In {\it Proceedings of the 9th International Symposium on Algorithmic Game Theory} {\it (SAGT)}, volume 9928 of {\it LNCS}, pages 105-116, 2016. · Zbl 1403.91072
[16] C. Deeparnab, M. Aranyak, and N. Viswanath. Fairness and optimality in congestion games. In {\it Proceedings of the 6th ACM Conference on Electronic Commerce}, EC ’05, pages 52-57, 2005.
[17] A. Fabrikant, C. H. Papadimitriou, and K. Talwar. The complexity of pure Nash equilibria. In {\it Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC)}, pages 604-612, 2004. · Zbl 1192.91042
[18] A. Fiat, K. Kaplan, M. Levy, S. Olonetsky, and R. Shabo.On the price of stability for designing undirected networks with fair cost allocations. In {\it Automata, Languages and} {\it Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006,} {\it Proceedings, Part I}, pages 608-618, 2006. · Zbl 1223.91014
[19] D. Fotakis.Stackelberg strategies for atomic congestion games.{\it Theor. Comp. Sys.}, 47(1):218-249, 2010. · Zbl 1203.91035
[20] D. Fotakis, S. C. Kontogiannis, and P. G. Spirakis. Selfish unsplittable flows. {\it Theoretical} {\it Computer Science}, 348:226-239, 2005. · Zbl 1152.90355
[21] D. Fotakis, S. C. Kontogiannis, and P. G. Spirakis. Symmetry in network congestion games: pure equilibria and anarchy cost. In {\it Proceedings of the 3rd Workshop on Approximation} {\it and Online Algorithms (WAOA)}, volume 3879 of {\it LNCS}, pages 161-175, 2005. · Zbl 1177.90070
[22] T. Harks, M. Klimm, and R.H. Möhring. Characterizing the existence of potential functions in weighted congestion games. {\it Theory of Computing Systems}, 49(1):46-70, 2011. · Zbl 1278.91013
[23] G. Karakostas and A. Viglas. Equilibria for networks with malicious users. {\it Math. Program.}, 110(3):591-613, 2007. · Zbl 1203.90032
[24] J. Li. An O(log(n)/log(log(n))) upper bound on the price of stability for undirected Shapley network design games. {\it Information Processing Letters}, 109(15):876-878, 2009. · Zbl 1205.68044
[25] T. Moscibroda, S. Schmid, and R. Wattenhofer. When selfish meets evil: Byzantine players in a virus inoculation game. In {\it Proceedings of the Twenty-fifth Annual ACM Symposium} {\it on Principles of Distributed Computing}, PODC ’06, pages 35-44, 2006. · Zbl 1314.68070
[26] J. F. Nash. Equilibrium points in {\it n}-person games. {\it Proceedings of the National Academy} {\it of Science}, 36(1):48-49, 1950. · Zbl 0036.01104
[27] P. N. Panagopoulou and P. G. Spirakis. Algorithms for pure Nash equilibria in weighted congestion games. {\it Journal of Experimental Algorithmics}, 11(2.7), 2006. · Zbl 1169.68319
[28] M. Penn, M. Polukarov, and M. Tennenholtz.Congestion games with load-dependent failures: Identical resources. {\it Games and Economic Behavior}, 67(1):156-173, 2009. · Zbl 1173.91302
[29] M. Penn, M. Polukarov, and M. Tennenholtz. Congestion games with failures. {\it Discrete} {\it Applied Mathematics}, 159(15):1508-1525, 2011. · Zbl 1245.91007
[30] R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. {\it International} {\it Journal of Game Theory}, 2:65-67, 1973. · Zbl 0259.90059
[31] A. Roth. The price of malice in linear congestion games. In {\it Internet and Network Econom-} {\it ics, 4th International Workshop, WINE 2008. Proceedings}, pages 118-125, 2008.
[32] T. Roughgarden and É. Tardos. How bad is selfish routing? {\it J. ACM}, 49(2):236-259, 2002. · Zbl 1323.90011
[33] :14
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.