The sequential price of anarchy for atomic congestion games

Research output: Book/ReportReportProfessional

10 Citations (Scopus)
94 Downloads (Pure)

Abstract

In situations without central coordination, the price of anarchy relates the quality of any Nash equilibrium to the quality of a global optimum. Instead of assuming that all players choose their actions simultaneously, here we consider games where players choose their actions sequentially. The sequential price of anarchy, recently introduced by Paes Leme, Syrgkanis, and Tardos then relates the quality of any subgame perfect equilibrium to the quality of a global optimum. The effect of sequential decision making on the quality of equilibria, however, depends on the specific game under consideration. Here we analyze the sequential price of anarchy for atomic congestion games with affine cost functions. We derive several lower and upper bounds, showing that sequential decisions mitigate the worst case outcomes known for the classical price of anarchy. Next to tight bounds on the sequential price of anarchy, a methodological contribution of our work is, among other things, a "factor revealing" integer linear programming approach that we use to solve the case of three players.
Original languageEnglish
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages20
Publication statusPublished - 18 Jul 2014

Publication series

NameCTIT Technical Report Series
PublisherCentre for Telematics and Information Technology, University of Twente
No.TR-CTIT-14-09
ISSN (Print)1381-3625

Keywords

  • Linear programming
  • Sequential price of anarchy
  • Equilibrium
  • Congestion games
  • Game theory

Fingerprint Dive into the research topics of 'The sequential price of anarchy for atomic congestion games'. Together they form a unique fingerprint.

Cite this