LIPIcs.FSTTCS.2020.40.pdf
- Filesize: 0.58 MB
- 16 pages
Document
Dynamic Network Congestion Games
Authors
Nathalie Bertrand 
,
Nicolas Markey ,
Ocan Sankur
-
Part of:
Volume:
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
File
Document Identifiers
Author Details
Cite As Get BibTex
Nathalie Bertrand, Nicolas Markey, Suman Sadhukhan, and Ocan Sankur. Dynamic Network Congestion Games. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.40
Abstract
Congestion games are a classical type of games studied in game theory, in which n players choose a resource, and their individual cost increases with the number of other players choosing the same resource. In network congestion games (NCGs), the resources correspond to simple paths in a graph, e.g. representing routing options from a source to a target. In this paper, we introduce a variant of NCGs, referred to as dynamic NCGs: in this setting, players take transitions synchronously, they select their next transitions dynamically, and they are charged a cost that depends on the number of players simultaneously using the same transition. We study, from a complexity perspective, standard concepts of game theory in dynamic NCGs: social optima, Nash equilibria, and subgame perfect equilibria. Our contributions are the following: the existence of a strategy profile with social cost bounded by a constant is in PSPACE and NP-hard. (Pure) Nash equilibria always exist in dynamic NCGs; the existence of a Nash equilibrium with bounded cost can be decided in EXPSPACE, and computing a witnessing strategy profile can be done in doubly-exponential time. The existence of a subgame perfect equilibrium with bounded cost can be decided in 2EXPSPACE, and a witnessing strategy profile can be computed in triply-exponential time.
Subject Classification
ACM Subject Classification
- Theory of computation → Algorithmic game theory
- Theory of computation → Formal languages and automata theory
- Theory of computation → Solution concepts in game theory
- Theory of computation → Verification by model checking
Keywords
- Congestion games
- Nash equilibria
- Subgame perfect equilibria
- Complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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.
- Guy Avni, Shibashis Guha, and Orna Kupferman. Timed network games. In Kim Guldstrand Larsen, Hans L. Bodlaender, and Jean-François Raskin, editors, Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS'17), volume 84 of Leibniz International Proceedings in Informatics, pages 37:1-37:16. Leibniz-Zentrum für Informatik, August 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.37.
- Guy Avni, Shibashis Guha, and Orna Kupferman. Timed network games with clocks. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS'18), volume 117 of Leibniz International Proceedings in Informatics, pages 23:1-23:18. Leibniz-Zentrum für Informatik, August 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.23.
- Guy Avni, Thomas A. Henzinger, and Orna Kupferman. Dynamic resource allocation games. Theoretical Computer Science, 807:42-55, February 2020. URL: https://doi.org/10.1016/j.tcs.2019.06.031.
- Baruch Awerbuch, Yossi Azar, and Amir Epstein. Large the price of routing unsplittable flow. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on the Theory of Computing (STOC'05), pages 57-66. ACM Press, May 2005. URL: https://doi.org/10.1145/1060590.1060599.
- Nathalie Bertrand, Nicolas Markey, Suman Sadhukhan, and Ocan Sankur. Dynamic network congestion games. CoRR, abs/2009.13632, 2020. URL: http://arxiv.org/abs/2009.13632.
-
Dimitri P. Bertsekas and John N. Tsitsiklis. Parallel and distributed computation: numerical methods. Prentice Hall, 1989.
- Umang Bhaskar, Lisa Fleischer, and Elliot Anshelevich. A Stackelberg strategy for routing flow over time. Games and Economic Behavior, 92:232-247, July 2015. URL: https://doi.org/10.1016/j.geb.2013.09.004.
- Thomas Brihaye, Véronique Bruyère, Aline Goeminne, Jean-François Raskin, and Marie Van den Bogaard. The complexity of subgame perfect equilibria in quantitative reachability games. In Wan J. Fokkink and Rob van Glabbeek, editors, Proceedings of the 30th International Conference on Concurrency Theory (CONCUR'19), volume 140 of Leibniz International Proceedings in Informatics, pages 13:1-13:16. Leibniz-Zentrum für Informatik, August 2019. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2019.13.
- Martin Hoefer, Vahab S. Mirrokni, Heiko Röglin, and Shang-Hua Teng. Competitive routing over time. Theoretical Computer Science, 412(39):5420-5432, September 2011. URL: https://doi.org/10.1016/j.tcs.2011.05.055.
- Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Gabor Rudolf, and Jihui Zhao. On short paths interdiction problems: Total and node-wise limited interdiction. Theory of Computing Systems, 43(2):204-233, August 2008. URL: https://doi.org/10.1007/s00224-007-9025-6.
- Ronald Koch and Martin Skutella. Nash equilibria and the price of anarchy for flows over time. Theory of Computing Systems, 49(1):71-97, July 2011. URL: https://doi.org/10.1007/s00224-010-9299-y.
- Elias Koutsoupias and Christos H. Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65-69, May 2009. URL: https://doi.org/10.1016/j.cosrev.2009.04.003.
- Elias Koutsoupias and Katia Papakonstantinopoulou. Contention issues in congestion games. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP'12) - Part II, volume 7392 of Lecture Notes in Computer Science, pages 623-635. Springer-Verlag, July 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_55.
- Carol A. Meyers and Andreas S. Schulz. The complexity of welfare maximization in congestion games. Networks, 59(2):252-260, March 2012. URL: https://doi.org/10.1002/net.20439.
- Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14(1):124-143, May 1996. URL: https://doi.org/10.1006/game.1996.0044.
- Michal Penn, Maria Polukarov, and Moshe Tennenholtz. Random order congestion games. Mathematics of Operations Research, 34(3):706-725, August 2009. URL: https://doi.org/10.1287/moor.1090.0394.
- Lili Qiu, Richard Yang, Yin Zhang, and Scott Shenker. On selfish routing in internet-like environments. IEEE Transactions on Computers, 14(4):725-738, August 2006. URL: https://doi.org/10.1109/TNET.2006.880179.
- Robert W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65-67, December 1973. URL: https://doi.org/10.1007/BF01737559.
-
Tim Roughgarden. Routing games. In Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors, Algorithmic Game Theory, chapter 18, page 461–486. Cambridge University Press, 2007.
- Subhash Suri, Csaba D. Tóth, and Yunhong Zhou. Selfish load balancing and atomic congestion games. Algorithmica, 47(1):79-96, 2007. URL: https://doi.org/10.1007/s00453-006-1211-4.