The Sequential Price of Anarchy

Jasper de Jong — The Sequential Price Of Anarchy

The price of anarchy measures the costs to society due to the selfishness of players. More formally, it is a lower bound on the quality of any Nash equilibrium relative to the quality of the global optimum. However, in particular games some Nash equilibria are not realistic, therefore the price of anarchy gives an overly pessimistic view. Instead of assuming that all players choose their strategies simultaneously, we consider games where players choose their strategies sequentially. The sequential prices of anarchy is then a lower bound on the quality of any subgame perfect equilibrium of such a game relative to the quality of the global optimum. This idea was introduced in a recent paper by Paes Leme, Syrgkanis, and Tardos, where they indeed give examples where sequential decision making leads to better equilibria. We review some of their results, touch upon our own results for a throughput scheduling problem, and discuss some of our ongoing work on linear congestion games.