Document Open Access Logo

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

Authors George Christodoulou, Martin Gairing, Yiannis Giannakopoulos , Diogo Poças , Clara Waldmann

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.32.pdf
  • Filesize: 0.57 MB
  • 18 pages

Document Identifiers

Author Details

George Christodoulou
  • Department of Computer Science, University of Liverpool, UK
Martin Gairing
  • Department of Computer Science, University of Liverpool, UK
Yiannis Giannakopoulos
  • Operations Research Group, TU Munich, Germany
Diogo Poças
  • Operations Research Group, TU Munich, Germany
Clara Waldmann
  • Operations Research Group, TU Munich, Germany

Funding

Supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (BMBF).

Acknowledgements

Y. Giannakopoulos is an associated researcher with the Research Training Group GRK 2201 "Advanced Optimization in a Networked Economy", funded by the German Research Foundation (DFG).

Cite As Get BibTex

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças, and Clara Waldmann. Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.32

Abstract

We study the existence of approximate pure Nash equilibria (α-PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree d. Previously it was known that d-approximate equilibria always exist, while nonexistence was established only for small constants, namely for 1.153-PNE. We improve significantly upon this gap, proving that such games in general do not have Θ̃(√d)-approximate PNE, which provides the first super-constant lower bound.
Furthermore, we provide a black-box gap-introducing method of combining such nonexistence results with a specific circuit gadget, in order to derive NP-completeness of the decision version of the problem. In particular, deploying this technique we are able to show that deciding whether a weighted congestion game has an Õ(√d)-PNE is NP-complete. Previous hardness results were known only for the special case of exact equilibria and arbitrary cost functions.
The circuit gadget is of independent interest and it allows us to also prove hardness for a variety of problems related to the complexity of PNE in congestion games. For example, we demonstrate that the question of existence of α-PNE in which a certain set of players plays a specific strategy profile is NP-hard for any α < 3^(d/2), even for unweighted congestion games.
Finally, we study the existence of approximate equilibria in weighted congestion games with general (nondecreasing) costs, as a function of the number of players n. We show that n-PNE always exist, matched by an almost tight nonexistence bound of Θ̃(n) which we can again transform into an NP-completeness proof for the decision problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Theory of computation → Exact and approximate computation of equilibria
  • Theory of computation → Representations of games and their complexity
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Atomic congestion games
  • existence of equilibria
  • pure Nash equilibria
  • approximate equilibria
  • hardness of equilibria

Metrics

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

Related Versions

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):1-22, December 2008. URL: https://doi.org/10.1145/1455248.1455249.
  2. Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602-1623, 2008. URL: https://doi.org/10.1137/070680096.
  3. Ioannis Caragiannis and Angelo Fanelli. On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 133:1-133:12, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.133.
  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 IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 532-541, 2011. URL: https://doi.org/10.1109/focs.2011.50.
  5. Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. Approximate pure nash equilibria in weighted congestion games: Existence, efficient computation, and structure. ACM Trans. Econ. Comput., 3(1):2:1-2:32, March 2015. URL: https://doi.org/10.1145/2614687.
  6. Ho-Lin Chen and Tim Roughgarden. Network design with weighted players. Theory of Computing Systems, 45(2):302, 2008. URL: https://doi.org/10.1007/s00224-008-9128-8.
  7. George Christodoulou and Martin Gairing. Price of stability in polynomial congestion games. ACM Transactions on Economics and Computation, 4(2):1-17, 2015. URL: https://doi.org/10.1145/2841229.
  8. George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças, and Clara Waldmann. Existence and complexity of approximate equilibria in weighted congestion games. CoRR, abs/2002.07466, February 2020. URL: http://arxiv.org/abs/2002.07466.
  9. George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, and Paul G. Spirakis. The price of stability of weighted congestion games. SIAM Journal on Computing, 48(5):1544-1582, 2019. URL: https://doi.org/10.1137/18M1207880.
  10. George Christodoulou, Elias Koutsoupias, and Paul G. Spirakis. On the performance of approximate equilibria in congestion games. Algorithmica, 61(1):116-140, 2011. URL: https://doi.org/10.1007/s00453-010-9449-2.
  11. Vincent Conitzer and Tuomas Sandholm. New complexity results about Nash equilibria. Games and Economic Behavior, 63(2):621-641, 2008. URL: https://doi.org/10.1016/j.geb.2008.02.015.
  12. José R. Correa, Andreas S. Schulz, and Nicolás E. Stier-Moses. Selfish routing in capacitated networks. Mathematics of Operations Research, 29(4):961-976, 2004. URL: https://doi.org/10.1287/moor.1040.0098.
  13. 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. URL: https://doi.org/10.1287/moor.1080.0322.
  14. Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The complexity of pure nash equilibria. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pages 604-612, 2004. URL: https://doi.org/10.1145/1007352.1007445.
  15. Matthias Feldotto, Martin Gairing, Grammateia Kotsialou, and Alexander Skopalik. Computing approximate pure nash equilibria in shapley value weighted congestion games. In Web and Internet Economics, pages 191-204. Springer International Publishing, 2017. URL: https://doi.org/10.1007/978-3-319-71924-5_14.
  16. Dimitris Fotakis, Spyros Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, and Paul Spirakis. The structure and complexity of Nash equilibria for a selfish routing game. Theoretical Computer Science, 410(36):3305-3326, 2009. URL: https://doi.org/10.1016/j.tcs.2008.01.004.
  17. Dimitris Fotakis, Spyros Kontogiannis, and Paul Spirakis. Selfish unsplittable flows. Theoretical Computer Science, 348(2):226-239, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.024.
  18. Yiannis Giannakopoulos, Georgy Noarov, and Andreas S. Schulz. An improved algorithm for computing approximate equilibria in weighted congestion games. CoRR, abs/1810.12806, October 2018. URL: http://arxiv.org/abs/1810.12806.
  19. Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1(1):80-93, March 1989. URL: https://doi.org/10.1016/0899-8256(89)90006-7.
  20. M. Goemans, Vahab Mirrokni, and A. Vetta. Sink equilibria and convergence. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 142-151, 2005. URL: https://doi.org/10.1109/SFCS.2005.68.
  21. Christoph Hansknecht, Max Klimm, and Alexander Skopalik. Approximate pure Nash equilibria in weighted congestion games. In Proceedings of APPROX/RANDOM, pages 242-257, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242.
  22. 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. URL: https://doi.org/10.1287/moor.1120.0543.
  23. Tobias Harks, Max Klimm, and Rolf H Möhring. Strong equilibria in games with the lexicographical improvement property. International Journal of Game Theory, 42(2):461-482, 2012. URL: https://doi.org/10.1007/s00182-012-0322-1.
  24. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? Journal of Computer and System Sciences, 37(1):79-100, 1988. URL: https://doi.org/10.1016/0022-0000(88)90046-3.
  25. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65-69, 2009. URL: https://doi.org/10.1016/j.cosrev.2009.04.003.
  26. Lavy Libman and Ariel Orda. Atomic resource sharing in noncooperative networks. Telecommunication Systems, 17(4):385-409, August 2001. URL: https://doi.org/10.1023/A:1016770831869.
  27. Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007. Google Scholar
  28. Panagiota N. Panagopoulou and Paul G. Spirakis. Algorithms for pure Nash equilibria in weighted congestion games. Journal of Experimental Algorithmics, 11:27, February 2007. URL: https://doi.org/10.1145/1187436.1216584.
  29. Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  30. Robert W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65-67, 1973. URL: https://doi.org/10.1007/BF01737559.
  31. Robert W. Rosenthal. The network equilibrium problem in integers. Networks, 3(1):53-59, 1973. URL: https://doi.org/10.1002/net.3230030104.
  32. Tim Roughgarden. Twenty Lectures on Algorithmic Game Theory. Cambridge University Press, 2016. Google Scholar
  33. Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM Journal on Computing, 20(1):56-87, 1991. URL: https://doi.org/10.1137/0220004.
  34. 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. URL: https://doi.org/10.1145/1374376.1374428.
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