Document Open Access Logo

On the Impact of Singleton Strategies in Congestion Games

Authors Vittorio Bilò, Cosimo Vinci

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.17.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Vittorio Bilò
Cosimo Vinci

Cite AsGet BibTex

Vittorio Bilò and Cosimo Vinci. On the Impact of Singleton Strategies in Congestion Games. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ESA.2017.17

Abstract

To what extent does the structure of the players' strategy space influence the efficiency of decentralized solutions in congestion games? In this work, we investigate whether better performance is possible when restricting to load balancing games in which players can only choose among single resources. We consider three different solutions concepts, namely, approximate pure Nash equilibria, approximate one-round walks generated by selfish players aiming at minimizing their personal cost and approximate one-round walks generated by cooperative players aiming at minimizing the marginal increase in the sum of the players' personal costs. The last two concepts can also be interpreted as solutions of simple greedy online algorithms for the related resource selection problem. Under fairly general latency functions on the resources, we show that, for all three types of solutions, better bounds cannot be achieved if players are either weighted or asymmetric. On the positive side, we prove that, under mild assumptions on the latency functions, improvements on the performance of approximate pure Nash equilibria are possible for load balancing games with weighted and symmetric players in the case of identical resources. We also design lower bounds on the performance of one-round walks in load balancing games with unweighted players and identical resources (in this case, solutions generated by selfish and cooperative players coincide).
Keywords
  • Congestion games
  • Nash equilibrium
  • price of anarchy
  • online load balancing
  • greedy algorithms

Metrics

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

References

  1. H. Ackermann, H. Röglin, and B. Vöcking. On the impact of combinatorial structure on congestion games. Journal of ACM, 55(6), 2008. Google Scholar
  2. H. Ackermann, H. Röglin, and B. Vöcking. Pure Nash equilibria in player-specific and weighted congestion games. Theoretical Computer Science, 410(17):1552-1563, 2009. Google Scholar
  3. S. Aland, D. Dumrauf, M. Gairing, B. Monien, and F. Schoppmann. Exact price of anarchy for polynomial congestion games. SIAM Journal on Computing, 40(5):1211-1233, 2011. Google Scholar
  4. B. Awerbuch, Y. Azar, and L. Epstein. The price of routing unsplittable flow. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 57-66, 2005. Google Scholar
  5. B. Awerbuch, Y. Azar, E. F. Grove, M.-Y. Kao, P. Krishnan, and J. S. Vitter. Load balancing in the L_p norm. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pages 383-391, 1995. Google Scholar
  6. 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
  7. 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
  8. V. Bilò, A. Fanelli, M. Flammini, and L. Moscardelli. Performances of one-round walks in linear congestion games. Theory of Computing Systems, 49(1):24-45, 2011. Google Scholar
  9. I. Caragiannis. Better bounds for online load balancing on unrelated machines. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 972-981, 2008. Google Scholar
  10. 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
  11. 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
  12. G. Christodoulou, E. Koutsoupias, and P. G. Spirakis. On the performance of approximate equilibria in congestion games. Algorithmica, 61(1):116-140, 2011. Google Scholar
  13. G. Christodoulou, V. S. Mirrokni, and A. Sidiropoulos. Convergence and approximation in potential games. Theoretical Computer Science, 438:13-27, 2012. Google Scholar
  14. J. Correa, J. de Jong, B. de Keijzer, and M. Uetz. The curse of sequentiality in routing games. In Proceedings of the 11th International Conference on Web and Internet Economics (WINE), volume 9470 of LNCS, pages 258-271, 2015. 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. 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
  17. D. Fotakis. Stackelberg strategies for atomic congestion games. Theory of Computing Systems, 47(1):218-249, 2010. Google Scholar
  18. D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish unsplittable flows. Theoretical Computer Science, 348:226-239, 2005. Google Scholar
  19. M. Gairing, T. Lücking, M. Mavronicolas, and B. Monien. The price of anarchy for polynomial social cost. Theoretical Computer Science, 369(1-3):116-135, 2006. Google Scholar
  20. M. Gairing and F. Schoppmann. Total latency in singleton congestion games. In Proceedings of the Third International Workshop on Internet and Network Economics (WINE), volume 4858 of LNCS, pages 381-387, 2007. Google Scholar
  21. T. Harks and M. Klimm. On the existence of pure Nash equilibria in weighted congestion games. Mathematics of Operations Research, 37(3):419-436, 2012. Google Scholar
  22. E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 1653 of LNCS, pages 404-413, 1999. Google Scholar
  23. T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. A new model for selfish routing. Theoretical Computer Science, 406(3):187-2006, 2008. Google Scholar
  24. J. F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Science, 36(1):48-49, 1950. Google Scholar
  25. R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65-67, 1973. Google Scholar
  26. T. Roughgarden. Intrinsic robustness of the price of anarchy. Journal of ACM, 62(5):32:1-32:42, 2015. Google Scholar
  27. S. Suri, C. Tóth, and Y. Zhou. Selfish load balancing and atomic congestion games. Algorithmica, 47(1):79-96, 2007. 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 Imprint Privacy Contact