Nicolas Markey

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.

@inproceedings{fsttcs2020-BMSS,
  author =              {Bertrand, Nathalie and Markey, Nicolas and
                         Sadhukhan, Suman and Sankur, Ocan},
  title =               {Dynamic network congestion games},
  editor =              {Saxena, Nitin and Simon, Sunil},
  booktitle =           {{P}roceedings of the 40th {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'20)},
  acronym =             {{FSTTCS}'20},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {182},
  pages =               {40:1-40:16},
  year =                {2020},
  month =               dec,
  doi =                 {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.
                         \par 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.},
}