The curse of sequentiality of network congestion games

Jasper de Jong, UT-EWI-DMMP


In “The curse of simultaneity”, Paes Leme at al. show that there are interesting classes of games for which sequential decision making and corresponding subgame perfect equilibria avoid worst case Nash equilibria, resulting in substantial improvements for the price of anarchy. This is called the sequential price of anarchy. A handful of papers have lately analyzed it for various problems, yet one of the most interesting open problems was to pin down its value for linear atomic routing (also: network congestion) games, where the price of anarchy equals 5/2. Our main contribution is the surprising result that the sequential price of anarchy is unbounded even for linear symmetric routing games, thereby showing that sequentiality can be arbitrarily worse than simultaneity for this important class of games. Additionally, we prove that in these games, even with two players, computing the outcome of a  subgame perfect equilibrium is NP-hard.