The Price of Anarchy (PoA) is a concept in economics and game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and many agents trying to go from some initial location to a destination. Let efficiency in this case mean 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. In the 'decentralized' version, each agent chooses its own path. The Price of Anarchy measures the ratio between average travel time in the two cases.
Contents
- Mathematical definition
- Prisoners dilemma
- Job scheduling
- Braess paradox
- Generalized routing problem
- References
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, ...). Different concepts of equilibrium can be used to model the selfish behavior of the agents, among which the most common is the Nash equilibrium. Different flavors of Nash equilibrium lead to variations of the notion of Price of Anarchy as Pure Price of Anarchy (for deterministic equilibria), Mixed Price of Anarchy (for randomized equilibria), and Bayes-Nash Price of Anarchy (for games with incomplete information). Solution concepts other than Nash equilibrium lead to variations such as the Price of Sinking.
The term Price of Anarchy was first used by Koutsoupias and Papadimitriou, but the idea of measuring inefficiency of equilibrium is older. The concept in its current form was designed to be the analogue of the 'approximation ratio' in an approximation algorithm or the 'competitive ratio' in an online algorithm. This is in the context of the current trend of analyzing games using algorithmic lenses (algorithmic game theory).
Mathematical definition
Consider a game
We can define a subset
If, instead of a 'welfare' which we want to 'maximize', the function measure efficiency is a 'cost function'
A related notion is that of the Price of Stability (PoS) which measures the ratio between the 'best equilibrium' and the optimal 'centralized' solution:
or in the case of cost functions:
We know that
Both the PoS and the PoA have been calculated for various types of games. Some examples are presented below.
Prisoner's dilemma
Consider the 2x2 game called prisoner's dilemma, given by the following cost matrix:
and let the cost function be
Since the game has a unique Nash equilibrium, the PoS is equal to the PoA and it is 5 too.
Job scheduling
A more natural example is the one of job scheduling. There are
Each machine has a speed
The cost for player
We consider two concepts of equilibrium: pure Nash and mixed Nash. 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
Claim. For each job scheduling game, there exists at least one pure-strategy Nash equilibrium.
Proof. We would like to take a socially optimal action profile
We claim that this is a pure-strategy Nash equilibrium. Reasoning by contradiction, suppose that some player
Claim. For each job scheduling game, the pure PoA is at most
Proof. It is easy to upper-bound the welfare obtained at any mixed-strategy Nash equilibrium
Consider, for clarity of exposition, any pure-strategy action profile
Since the above holds for the social optimum as well, comparing the ratios
Braess' paradox
Consider a road network in which a fixed number of drivers need to move from a common source to a common destination; assume that each driver chooses its route selfishly, and that the time to traverse a road depends linearly on the number of drivers choosing that road.
We can formalize this setting as a routing problem in a directed, connected graph
Consider the example in the figure: if the dashed road is not available, the mixed-strategy Nash equilibrium happens when each player chooses the top route and the bottom route with the same probability: this equilibrium has social cost 1.5, and it takes 1.5 units of time to each driver to go from
Hence, the uncommon result of denying access to the fastest road by central control to be beneficial to the public in some cases.
Generalized routing problem
The routing problem introduced in the Braess' paradox can be generalized to many different flows traversing the same graph at the same time.
Definition (Generalized flow). Let
The flow traversing a specific edge of
For succinctness, we write
Definition (Nash-equilibrium flow). A flow
This definition is closely related to what we said about the support of mixed-strategy Nash equilibria in normal-form games.
Definition (Conditional welfare of a flow). Let
Fact 1. Given a Nash-equilibrium flow
Proof (By contradiction). Assume that
Since
Therefore, there must be a pair
In other words, the flow
Note that Fact 1 does not assume any particular structure on the set
Fact 2. Given any two real numbers
Proof. This is another way to express the true inequality
Theorem. The pure PoA of any generalized routing problem
Proof. Note that this theorem is equivalent to saying that for each Nash-equilibrium flow
By using Fact 2, we have that
since
We can conclude that
Note that in the proof we have made extensive use of the assumption that the functions in
Theorem. Given a generalized routing problem with graph
Note that the PoA can grow with
This quantity tends to zero when