2026-08-17T19:53:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13281 2024-03-06T10:52:01Z ddc:004 open_access

Dynamic Network Congestion Games Bertrand, Nathalie Markey, Nicolas Sadhukhan, Suman Sankur, Ocan Congestion games Nash equilibria Subgame perfect equilibria Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathalie Bertrand and Nicolas Markey and Suman Sadhukhan and Ocan Sankur 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.40 urn:nbn:de:0030-drops-132811 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.40 eng https://creativecommons.org/licenses/by/3.0/legalcode