Theory Matters - Visioning/PriceAnarchy

view · edit · attach · print · history

The Price of Anarchy

Is it OK to be selfish?

Summary

How do you choose your route to work each morning? Almost certainly you choose your route "selfishly", aiming to get to work as quickly as possible, without regard to the additional congestion that you cause other commuters to experience. Naturally, you also expect your fellow commuters to behave in a similarly egocentric fashion. But what if everyone cooperated by coordinating routes? Is it possible to limit the interference among routes, thereby improving commute times? If so, by how much?

Performance loss caused by a lack of coordination arises in many computer science applications --- e.g., in routing packets through a communication network, scheduling jobs on processors, or creating and allocating network infrastruture --- and researchers in theoretical computer science formulated the price of anarchy to rigorously understand this issue. The price of anarchy measures the extent to which competition approximates cooperation. It involves the idea of an equilibrium, an idea fundamental to game theory, and the concept of approximation, which is ubiquitous in theoretical computer science. It is an example of a broader research agenda in theoretical computer science: to analyze optimization problems where an optimal solution is unimplementable --- here, because of an inability to control and coordinate independent entities --- and to derive insight from a quantitative analysis of approximation solutions (such as equilibria).

Rationale

The price of anarchy is a quantitative measure of the "quality" of game-theoretic equilibria, and is defined for every choice of game, non-negative objective function, and equilibrium concept. A game specifies a set of players, a set of actions for each player, and a payoff (or cost) to each player in every possible game outcome. For example, players could correspond to source-destination vertex pairs in a network, with actions corresponding to paths, and the cost incurred by a player in an outcome could be the delay incurred by its traffic in the resulting traffic pattern. A (pure-strategy) Nash equilibrium is an outcome from which no player can improve its payoff via a unilateral change in action. The price of anarchy (POA) is defined as the worst ratio between the objective function value of an equilibrium and that of an optimal outcome. (Here "worst" is over the possibly many equilibria of the game.) A typical objective function would be the sum of players' payoffs (or costs). In the network routing example, the POA would be the factor by which average delay at equilibrium exceeds the minimum-possible average delay achievable given dictatorial control over players' actions. A POA close to 1 indicates near-optimal equilibria, while a POA far from 1 demonstrates severe performance loss from selfish behavior. Theoretical computer scientists have determined tight bounds on the POA in several interesting classes of games. For example, in the network routing case, the POA is at most 4/3 in every multicommodity network with affine edge delay functions. A matching lower bound is achieved in a two-vertex, two-link network originally studied by Pigou in 1920.

Contributors and Credits

Tim Roughgarden, with input from Shuchi Chawla, Jason Hartline, Anna Karlin, and Claire Mathieu.

Image Ideas

A bunch of people simultaneously rushing to join the (previously) shortest queue; a two-node, two-link network; a picture of the "Prisoner's Dilemma" (a la the cover of Straffin's game theory book).

Comments

to give feedback on this nugget, just add another bullet to this list.
The summary is a nice explanation of what the price of anarchy is, with a nice example, but it would be nice to conclude it by conveying the broader research agenda for TCS here and its importance (rather than ending with a specific question about a specific instantiation of the problem). - Salil
I agree with Salil's point. Maybe the text could be structured as 3 short paragraphs: the first would be essentially the first 2 sentences (perhaps with a bit of elaboration), the second could be the nice concrete example, and the third paragraph could start with a segue from the traffic example to, say, routing network traffic in the Internet; go on to say that the price of anarchy is a recent concept that has come out of TCS (make sure we get the credit!) and is actively being explored; and close by somehow expressing the broader agenda and its importance as Salil suggested. -- Rocco
I personally like the second sentence, but "rendevous" may be a bit poetic for this context; maybe "It relates the idea..." instead? - Rocco
I agree with "rendezvous" -> something else much lamer, somehow it doesnt gel in there. --Anupam
Other than that, I like the text, but would suggest altering the order, in a somewhat different way from Rocco's and Salil's suggestions. (Talk about too many cooks here! :) ) Start with the motivation (driving to work) to draw people in, subtly indicate what the competition and collaboration would mean in this context, and then talk about the price of anarchy measuring how well competition approximates collaboration. Then the bit about PoA ? merging two central concepts from Econ/TCS, internet routing, and the broader agenda. --Anupam
Summary edited to reflect above comments. -Tim
It might be good if the tagline hinted more about the (T)CS side of this, otherwise it sounds like it might be entirely in the domain of economics or moral philosophy. - Salil
Added concrete applications to the summary, added a rationale. -Tim
tagline: seems to equate anarchy with selfishness, which is philosophically dodgy. - bernard
Note from designer Elaine Park: This is an instance in which the original image idea proved difficult for me to execute. Here is a classic example of the difference between an illustrator and a designer/art director; I apologize for my lack of pen to paper drawing skills. However, I'm hoping this solution begins to get the core idea across. Here is simply a group of gears that could, but will not work together, resulting in performance loss. Another idea might be a set of gears that are interlocked so that they should work, except that one gear is square (which would speak more to selfishness, but I think that this one gets the idea of "anarchy" across more effectively).
In response to Bernard: the concept we want to convey is that of selfishness and the anarchy brought about because different people care for different things. Unfortunately "price of anarchy" is a standard term so we have to stick with it, although I agree with you that it doesn't bring out the meaning quite fully. -- Shuchi
Personally, I don't like the suggestion with the gears. Maybe the easiest (though not that evocative) is a stock image of flow or traffic in a network. - Tim
Revised ppt uploaded. - Salil
Note from designer Elaine Park: I hope the gridlock is effective. The bottom half may stand for the bottom link [in Pigou's two-node,two-link network].