Nicolas Markey

Abstract

Network congestion games are a simple model for reasoning about routing problems in a network. They are a very popular topic in algorithmic game theory, and a huge amount of results about existence and (in)efficiency of equilibrium strategy profiles in those games have been obtained over the last 20 years.

In particular, the price of anarchy has been defined as an important notion for measuring the inefficiency of Nash equilibria. Generic bounds have been obtained for the price of anarchy over various classes of networks, but little attention has been put on the effective computation of this value for a given network. This talk presents recent results on this problem in different settings.

@inproceedings{formats2023-Mar,
  author =              {Markey, Nicolas},
  title =               {Computing the price of anarchy in atomic network
                         congestion games (invited~talk)},
  editor =              {Petrucci, Laure and Sproston, Jeremy},
  booktitle =           {{P}roceedings of the 21st {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'23)},
  acronym =             {{FORMATS}'23},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {14138},
  pages =               {3-12},
  year =                {2023},
  month =               sep,
  doi =                 {10.1007/978-3-031-42626-1_1},
  abstract =            {Network congestion games are a simple model for
                         reasoning about routing problems in a network. They
                         are a very popular topic in algorithmic game theory,
                         and a huge amount of results about existence and
                         (in)efficiency of equilibrium strategy profiles in
                         those games have been obtained over the last
                         20~years. \par In~particular, the price of anarchy
                         has been defined as an important notion for
                         measuring the inefficiency of Nash equilibria.
                         Generic bounds have been obtained for the price of
                         anarchy over various classes of networks, but little
                         attention has been put on the effective computation
                         of this value for a given network. This talk
                         presents recent results on this problem in different
                         settings.},
}