The curse of sequentiality in routing games

Jose Correa, Jasper de Jong, Bart de Keijzer, Marc Jochen Uetz

Research output: Book/ReportReportOther research output

11 Citations (Scopus)
109 Downloads (Pure)

Abstract

In the ``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 analysed it for various problems, yet one of the most interesting open problems was to pin down its value for network congestion games, where the price of anarchy equals 5/2. The main contribution of this paper 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. Complementing this unboundedness result we solve an open problem in the area by establishing that the (regular) price of anarchy for linear symmetric routing games equals 5/2. Additionally, we prove that in these games, even with two players, computing the outcome of a subgame perfect equilibrium is NP-hard. The latter explains, to some extent, the difficulty of analyzing subgame perfect equilibria.
Original languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages17
Publication statusPublished - Oct 2015

Publication series

NameCTIT Technical Report Series
PublisherUniversity of Twente, Centre for Telematics and Information Technology (CTIT)
No.TR-CTIT-15-07
ISSN (Print)1381-3625

Keywords

  • MSC-65K05
  • METIS-312720
  • Price of Anarchy
  • CR-F.2
  • IR-97861
  • MSC-90C27
  • Network Routing Games
  • EWI-26301

Cite this