Price of anarchy

The Price of Anarchy (PoA)[1] is a concept in economics and game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents.

For example, consider the system of transportation of a city and many agents trying to go from some initial location to a destination.

Here, efficiency means the average time for an agent to reach the destination.

In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time.

The Price of Anarchy measures the ratio between average travel time in the two cases.

Usually the system is modeled as a game and the efficiency is some function of the outcomes (e.g. maximum delay in a network, congestion in a transportation system, social welfare in an auction, etc.).

Solution concepts other than Nash equilibrium lead to variations such as the Price of Sinking.

[2] The term Price of Anarchy was first used by Elias Koutsoupias and Christos Papadimitriou,[1][3] but the idea of measuring inefficiency of equilibrium is older.

We can define a measure of efficiency of each outcome which we call welfare function

Natural candidates include the sum of players utilities (utilitarian objective)

The Price of Anarchy is then defined as the ratio between the optimal 'centralized' solution and 'worst equilibrium':

A related notion is that of the Price of Stability (PoS) which measures the ratio between the optimal 'centralized' solution and the 'best equilibrium':

Now, the worst (and only) Nash Equilibrium would be when both players defect and the resulting cost is

However, the highest social welfare occurs when both cooperate, in which case the cost is

Since the game has a unique Nash equilibrium, the PoS is equal to the PoA and it is 5 too.

The Price of Anarchy compares the situation where the selection of machines is guided/directed centrally to the situation where each player chooses the machine that will make its job run fastest.

It should be clear that mixed PoA ≥ pure PoA, because any pure Nash equilibrium is also a mixed Nash equilibrium (this inequality can be strict: e.g. when

For each job scheduling game, there exists at least one pure-strategy Nash equilibrium.

must decrease as a result of the move and no other machine is affected, this means that the new configuration is guaranteed to have reduced the

It is easy to upper-bound the welfare obtained at any mixed-strategy Nash equilibrium

Q.E.D Consider a road network as shown in the adjacent diagram on which 4000 drivers wish to travel from point Start to End.

Now suppose the dashed line A–B is a road with an extremely short travel time of approximately 0 minutes.

Nobody has any incentive to travel A-End or Start-B because any driver trying them will take 85 minutes.

Thus, the opening of the cross route triggers an irreversible change to it by everyone, costing everyone 80 minutes instead of the original 65.

The routing problem introduced in the Braess's paradox can be generalized to many different flows traversing the same graph at the same time.

This definition is closely related to what we said about the support of mixed-strategy Nash equilibria in normal-form games.

PoA upper bounds can be obtained if the game is shown to satisfy a so-called smoothness inequality.

[6] (A symmetrical statement is similarly valid for utility-sharing games with convex utility functions.)

In mechanism design, this means that the Shapley value solution concept is optimal for these sets of games.

Moreover, for these (finite) games it was proven that every equilibrium which achieves the PoA bound is fragile, in the sense that the agents demonstrate a state of indifference between their equilibrium action and the action they would pursue in a system-optimal outcome.