Document Open Access Logo

Uniform Mixed Equilibria in Network Congestion Games with Link Failures

Authors Vittorio Bilò, Luca Moscardelli, Cosimo Vinci

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.146.pdf
  • Filesize: 498 kB
  • 14 pages

Document Identifiers

Author Details

Vittorio Bilò
  • Department of Mathematics and Physics, University of Salento, Lecce, Italy
Luca Moscardelli
  • Department of Economic Studies, University of Chieti-Pescara, Pescara, Italy
Cosimo Vinci
  • Department of Information Engineering Computer Science and Mathematics, University of L'Aquila, L'Aquila, Italy - Gran Sasso Science Institute, L'Aquila, Italy

Cite As Get BibTex

Vittorio Bilò, Luca Moscardelli, and Cosimo Vinci. Uniform Mixed Equilibria in Network Congestion Games with Link Failures. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 146:1-146:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.146

Abstract

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 >= 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Theory of computation → Quality of equilibria
  • Theory of computation → Network games
Keywords
  • Network Congestion Games
  • Fault-Tolerant Routing
  • Nash Equilibria
  • Price of Anarchy
  • Price of Stability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

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

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact