The Price of Anarchy
Posted January 2011.What Prisoner's Dilemma and Braess's Paradox point out is that there are situations where, if individuals are left to make their own decisions, the result might be that as a group or as individuals they are worse off....
Common economic wisdom suggests that if markets are free to operate without intervention, the good times will roll. The recent world economic crisis, now sometimes referred to as the Great Recession, seems to suggest a more complex reality. Much of modern economics is based on the assumption that the "human actors" in the "economic drama" behave rationally. However, with the help of insights from the branch of mathematics known as game theory, some of the assumptions of modern economics can be seen as "simplistic." First, when people do act in what seems to be a rational way, they can wind up in a "bad place." Here we will take a look at a concept that has come to be called the "price of anarchy." The intuition here is that when rational people just do what they want, how bad can the result be compared with what could be achieved if they were "regulated" or "induced" into other behavior which is optimal (best)? Second, it may not be computationally easy to find one's way to a good place, whether it's an individual trying to get one's best outcome or a regulator who is trying to help the actors achieve their best outcomes.
The name Prisoner's Dilemma is due to the mathematician Albert Tucker, who, though not the creator of this example, did much to popularize interest in it. It is one of many important games--including Chicken--which have been important both in the theory and application of game theory.
Table 1 (Payoff matrix for Prisoner's Dilemma)
Table 2 (Payoff matrix for a "fair" zero-sum game)
Common sense suggests that if one has a road network which is currently congested, opening a new road should help. To understand what might go wrong, consider the following situation which may be an eye-opening example for seeing the subtleties of situations that economic planners and/or business executives might face. The issue is a real one in route planning for information packets traffic on the internet.
Dietrick Braess (Oberwolfach Photo Collection)
Braess's original paper appeared in German in 1968, under the title: Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung (Translation: A paradox of traffic planning).
The price of anarchy
The study of the price of anarchy was initiated by Christos Papadimitriou and Elias Koutsoupias in a paper which appeared in 1999. Koutsoupias writes: "At the time, we called it 'coordination ratio', but later Christos coined the catchy term 'price of anarchy'." The catchy term may have helped because there are now hundreds of scholarly articles which make reference to this idea or have extended the concept.
(Photo courtesy of Elias Koutsoupias (left) and Christos Papadimitriou (right))
The power of introducing new "measures'" such as the price of anarchy is that it makes it possible to quantitatively compare different situations and to focus questions about a particular game or class of games. For example, one might be willing to live with a situation where the price of anarchy was relatively small because it meant that even in the worst case allowing people to make choices freely could not be much improved upon.
Anshelevich, E. and A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden, The price of stability for network design with fair cost allocation. In Proc. 45th Symposium Foundations of Computer Science, pp. 295-304, 2004.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance