The sequential price of anarchy for atomic congestion games

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