Document Open Access Logo

Approximate Pure Nash Equilibria in Weighted Congestion Games

Authors Christoph Hansknecht, Max Klimm, Alexander Skopalik

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.242.pdf
  • Filesize: 0.48 MB
  • 16 pages

Document Identifiers

Author Details

Christoph Hansknecht
Max Klimm
Alexander Skopalik

Cite As Get BibTex

Christoph Hansknecht, Max Klimm, and Alexander Skopalik. Approximate Pure Nash Equilibria in Weighted Congestion Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 242-257, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242

Abstract

We study the existence of approximate pure Nash equilibria in weighted congestion games and develop techniques to obtain approximate potential functions that prove the existence of alpha-approximate pure Nash equilibria and the convergence of alpha-improvement steps. Specifically, we show how to obtain upper bounds for approximation factor alpha for a given class of cost functions. For example for concave cost functions the factor is at most 3/2, for quadratic cost functions it is at most 4/3, and for polynomial cost functions of maximal degree d it is at at most d + 1. For games with two players we obtain tight bounds which are as small as for example 1.054 in the case of quadratic cost functions.

Subject Classification

Keywords
  • Congestion game
  • Pure Nash equilibrium
  • Approximate equilibrium
  • Existence
  • Potential function

Metrics

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

References

  1. Heiner Ackermann, Heiko Röglin, and Berthold Vöcking. On the impact of combinatorial structure on congestion games. Journal of the ACM, 55(6), 2008. Google Scholar
  2. Heiner Ackermann, Heiko Röglin, and Berthold Vöcking. Pure Nash equilibria in player-specific and weighted congestion games. Theoretical Computer Science, 410(17):1552-1563, 2009. Google Scholar
  3. Heiner Ackermann and Alexander Skopalik. Complexity of pure Nash equilibria in player-specific network congestion games. Internet Mathematics, 5(4):323-342, 2008. Google Scholar
  4. Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. Efficient computation of approximate pure Nash equilibria in congestion games. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, (FOCS), pages 532-541, 2011. Google Scholar
  5. Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC), pages 284-301, 2012. Google Scholar
  6. Ho-Lin Chen and Tim Roughgarden. Network design with weighted players. In Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 29-38, 2006. Google Scholar
  7. Steve Chien and Alistair Sinclair. Convergence to approximate Nash equilibria in congestion games. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 169-178, 2007. Google Scholar
  8. George Christodoulou, Elias Koutsoupias, and Paul G. Spirakis. On the performance of approximate equilibria in congestion games. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA), pages 251-262. Springer, 2009. Google Scholar
  9. Juliane Dunkel and Andreas S. Schulz. On the complexity of pure-strategy Nash equilibria in congestion and local-effect games. In Proceedings of the 2nd International Workshop Internet & Network Economics (WINE), pages 62-73, 2006. Google Scholar
  10. Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The complexity of pure Nash equilibria. In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pages 604-612, 2004. Google Scholar
  11. Dimitris Fotakis, Spyros Kontogiannis, and Paul G. Spirakis. Selfish unsplittable flows. Theoretical Computer Science, 348(2-3):226-239, 2005. Google Scholar
  12. Irving L. Glicksberg. A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points. Proceedings of the AMS, 3:170-174, 1952. Google Scholar
  13. Michel X. Goemans, Vahab S. Mirrokni, and Adrian Vetta. Sink equilibria and convergence. In Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS), pages 142-154, 2005. Google Scholar
  14. Tobias Harks and Max Klimm. On the existence of pure Nash equilibria in weighted congestion games. Mathematics of Operations Research, 37(3):419-436, 2012. Google Scholar
  15. Lavy Libman and Ariel Orda. Atomic resource sharing in noncooperative networks. Telecommunication Systems, 17(4):385-409, 2001. Google Scholar
  16. Igal Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13(1):111-124, 1996. Google Scholar
  17. John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, USA, 36:48-49, 1950. Google Scholar
  18. Panagiota N. Panagopoulou and Paul G. Spirakis. Algorithms for pure Nash equilibria in weighted congestion games. Journal of Experimental Algorithmics, 11, 2007. Google Scholar
  19. Robert Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65-67, 1973. Google Scholar
  20. Alexander Skopalik and Berthold Vöcking. Inapproximability of pure Nash equilibria. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 355-364, 2008. 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