Summary: 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, we consider games where players choose their actions sequentially. The sequential price of anarchy, recently introduced by R. P. Leme et al. [in: Proceedings of the 3rd conference on innovations in theoretical computer science, ITCS’12, Cambridge, MA, USA, January 8–10, 2012. New York, NY: Association for Computing Machinery (ACM). 60–67 (2012; Zbl 1348.91014)], 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, depends on the specific game under consideration. 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 [B. Awerbuch et al., in: Proceedings of the 37th annual ACM symposium on theory of computing, STOC’05. New York, NY: Association for Computing Machinery (ACM). 57–66 (2005; Zbl 1192.90099); G. Christodoulou and E. Koutsoupias, in: Proceedings of the 37th annual ACM symposium on theory of computing, STOC’05. New York, NY: Association for Computing Machinery (ACM). 67–73 (2005; Zbl 1192.91039)]. Next to tight bounds on the sequential price of anarchy, a methodological contribution of our work is, among other things, a “factor revealing” linear programming approach we use to solve the case of three players.
For the entire collection see [Zbl 1302.68013].