e-mail: mavronic@ucy.ac.cy

Back to Main Page

One Hundred Bounds on the Price of Anarchy

The Price of Anarchy was originally defined by Koutsoupias and Papadimitriou as a measure of the performance loss for a computer system due to the selfish behavior of its components. The components may be the users, the machines, the links or the agents. The performance loss is measured using the so called Social Cost (the cost to the system). Price of Anarchy is a worst-case measure: it refers to the worst-possible acceptable system behavior, usually (but not always) identified with Nash equilibrium.

The last seven years have witnessed a vast amount of effort towards provng bounds on the Price of Anarchy for a wide variety of system models and definitions of Social Cost. In these lectures, we will survey the most interesting such bounds. We will place some emphasis on a categorization of techniques used to prove the bounds, and we will address open problems.

Here is the slide show presentation of the lecture I gave. (ppt) (pdf)