The Price of Anarchy

 

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: