Document Open Access Logo

On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies

Authors Ioannis Caragiannis, Angelo Fanelli

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.133.pdf
  • Filesize: 447 kB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Theory of computation → Convergence and learning in games
Keywords
  • Congestion games
  • approximate pure Nash equilibrium
  • potential functions
  • approximate price of stability

Metrics

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

Abstract

We consider the problem of the existence of natural improvement dynamics leading to approximate pure Nash equilibria, with a reasonable small approximation, and the problem of bounding the efficiency of such equilibria in the fundamental framework of weighted congestion game with polynomial latencies of degree at most d >= 1. In this work, by exploiting a simple technique, we firstly show that the game always admits a d-approximate potential function. This implies that every sequence of d-approximate improvement moves by the players always leads the game to a d-approximate pure Nash equilibrium. As a corollary, we also obtain that, under mild assumptions on the structure of the players' strategies, the game always admits a constant approximate potential function. Secondly, by using a simple potential function argument, we are able to show that in the game there always exists a (d+delta)-approximate pure Nash equilibrium, with delta in [0,1], whose cost is 2/(1+delta) times the cost of an optimal state.

Cite As Get BibTex

Ioannis Caragiannis and Angelo Fanelli. On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 133:1-133:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.133

Author Details

Ioannis Caragiannis
  • University of Patras & CTI "Diophantus", Patras, Greece
Angelo Fanelli
  • CNRS (UMR-6211), Caen, France

Funding

  • Fanelli, Angelo: ANR-14-CE24-0007-01 "CoCoRICo-CoDec"

References

  1. Sebastian Aland, Dominic Dumrauf, Martin Gairing, Burkhard Monien, and Florian Schoppmann. Exact price of anarchy for polynomial congestion games. SIAM Journal on Computing, 40(5):1211-1233, 2011. Google Scholar
  2. Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. Approximate pure Nash equilibria in weighted congestion games: Existence, efficient computation, and structure. ACM Transactions on Economics and Computation, 3(1):2:1-2:32, 2015. Google Scholar
  3. Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Panagiotis Kanellopoulos, and Luca Moscardelli. Tight bounds for selfish and greedy load balancing. Algorithmica, 61(3):606-637, 2011. Google Scholar
  4. Steve Chien and Alistair Sinclair. Convergence to approximate Nash equilibria in congestion games. Games and Economic Behavior, 71(2):315-327, 2011. Google Scholar
  5. Nicolas Christin, Jens Grossklags, and John Chuang. Near Rationality and Competitive Equilibria in Networked Systems. In Proceedings of the ACM SIGCOMM Workshop on Practice and Theory of Incentives in Networked Systems (PINS), pages 213-219, 2004. Google Scholar
  6. George Christodoulou and Martin Gairing. Price of stability in polynomial congestion games. ACM Transactions on Economics and Computation, 4(2):10:1-10:17, 2016. Google Scholar
  7. George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, and Paul G. Spirakis. The Price of Stability of Weighted Congestion Games. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), pages 150:1-150:16, 2018. Google Scholar
  8. George Christodoulou and Elias 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), pages 59-70, 2005. Google Scholar
  9. Juliane Dunkel and Andreas S. Schulz. On the complexity of pure-strategy Nash equilibria in congestion and local-effect games. Mathematics of Operations Research, 33(4):851-868, 2008. Google Scholar
  10. Dimitris Fotakis, Spyros C. Kontogiannis, and Paul G. Spirakis. Selfish unsplittable flows. Theoretical Computer Science, 348(2-3):226-239, 2005. Google Scholar
  11. Michel X. Goemans, Vahab S. Mirrokni, and Adrian Vetta. Sink equilibria and convergence. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 142-154, 2005. Google Scholar
  12. 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), pages 242-257, 2014. Google Scholar
  13. Tobias Harks and Max Klimm. On the existence of pure Nash equilibria in weighted congestion games. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Part I, pages 79-89, 2010. Google Scholar
  14. Lavy Libman and Ariel Orda. Atomic resource sharing in noncooperative networks. Telecommunication Systems, 17(4):385-409, 2001. Google Scholar
  15. Panagiota N. Panagopoulou and Paul G. Spirakis. Algorithms for pure Nash equilibria in weighted congestion games. ACM Journal of Experimental Algorithmics, 11, 2006. Google Scholar
  16. Robert W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65-67, 1973. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact