Nicolas Markey

Abstract

We consider atomic congestion games on series-parallel networks, and study the structure of the sets of Nash equilibria and social local optima on a given network when the number of players varies. We establish that these sets are definable in Presburger arithmetic and that they admit semilinear representations whose all period vectors have a common direction. As an application, we prove that the prices of anarchy and stability converge to 1 as the number of players goes to infinity, and show how to exploit these semilinear representations to compute these ratios precisely for a given network and number of players.

@inproceedings{fsttcs2022-BMSS,
  author =              {Bertrand, Nathalie and Markey, Nicolas and
                         Sadhukhan, Suman and Sankur, Ocan},
  title =               {Semilinear Representations for Series-Parallel
                         Atomic Congestion Games},
  editor =              {Dawar, Anuj and Guruswami, Venkatesan},
  booktitle =           {{P}roceedings of the 42nd {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'22)},
  acronym =             {{FSTTCS}'22},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {250},
  pages =               {32:1-32:20},
  year =                {2022},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2022.32},
  abstract =            {We~consider atomic congestion games on
                         series-parallel networks, and study the structure of
                         the sets of Nash equilibria and social local optima
                         on a given network when the number of players
                         varies. We establish that these sets are definable
                         in Presburger arithmetic and that they admit
                         semilinear representations whose all period vectors
                         have a common direction. As~an~application, we~prove
                         that the prices of anarchy and stability converge
                         to~1 as the number of players goes to infinity, and
                         show how to exploit these semilinear representations
                         to compute these ratios precisely for a given
                         network and number of players.},
}