Price of anarchy


The Price of Anarchy 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 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. 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.
Usually the system is modeled as a game and the efficiency is some function of the outcomes. 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, Mixed Price of Anarchy, and Bayes–Nash Price of Anarchy. Solution concepts other than Nash equilibrium lead to variations such as the Price of Sinking.
The term Price of Anarchy was first used by Elias Koutsoupias and Christos 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.

Mathematical definition

Consider a game , defined by a set of players, strategy sets for each player and utilities . We can define a measure of efficiency of each outcome which we call welfare function. Natural candidates include the sum of players utilities minimum utility ..., or any function that is meaningful for the particular game being analyzed and is desirable to be maximized.
We can define a subset to be the set of strategies in equilibrium. The Price of Anarchy is then defined as the ratio between the 'worst equilibrium' and the optimal 'centralized' solution:
If, instead of a 'welfare' which we want to 'maximize', the function measure efficiency is a 'cost function' which we want to 'minimize' we use :
A related notion is that of the Price of Stability which measures the ratio between the 'best equilibrium' and the optimal 'centralized' solution:
or in the case of cost functions:
We know that by the definition. It is expected that the loss in efficiency due to game-theoretical constraints is somewhere between 'PoS' and 'PoA'.
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:
CooperateDefect
Cooperate1, 17, 0
Defect0, 75, 5

and let the cost function be Now, the minimum cost would be when both players cooperate and the resulting cost is. However, the only Nash equilibrium occurs when both defect, in which case the cost is. Thus the PoA of this game will 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 players and each of them has a job to run. They can choose one of machines to run the job. 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.
Each machine has a speed Each job has a weight
A player picks a machine to run his or her job on. So, the strategies of each player are Define the load on machine to be:
The cost for player is i.e., the load of the machine they chose. We consider the egalitarian cost function, here called the makespan.
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. First we need to argue that there exist pure Nash equilibria.
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. This would mean simply an action profile whose makespan is minimum. However, this will not be enough. There may be several such action profiles leading to a variety of different loads distributions. Among these, we further restrict ourselves to one that has a minimum second-largest load. Again, this results in a set of possible load distributions, and we repeat until the th-largest load, where there can only be one distribution of loads. This would also be called the lexicographic smallest sorted load vector.
We claim that this is a pure-strategy Nash equilibrium. Reasoning by contradiction, suppose that some player could strictly improve by moving from machine to machine. This means that the increased load of machine after the move is still smaller than the load of machine before the move. As the load of machine 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 th-largest load in the distribution. This, however, violates the assumed lexicographic minimality of.
Q.E.D.
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 by
Consider, for clarity of exposition, any pure-strategy action profile : clearly
Since the above holds for the social optimum as well, comparing the ratios and proves the claim. Q.E.D

Selfish Routing

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, in which we want to send one unit of flow from a source node to a destination node . In particular, let the flow be a function assigning to each edge a non-negative real number, and consider the set of linear functions that map the flow traversing each edge to the latency to traverse the edge. Let's also define the social welfare of a flow as
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 to. Hoping to improve the performance of the network, a legislator could decide to make the dashed, low-latency edge available to the drivers: in this case, the only Nash equilibrium would happen when every driver uses the new road, therefore the social cost would increase to 2 and now it would take 2 units of time to each player to go from to.
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 . Let, and be as defined above, and suppose that we want to route the quantities through each distinct pair of nodes in.
A flow is defined as an assignment of a real, nonnegative number to each path going from to , with the constraint that
The flow traversing a specific edge of is defined as
For succinctness, we write when are clear from context.
Definition . A flow is a Nash-equilibrium flow iff and from to
This definition is closely related to what we said about the support of mixed-strategy Nash equilibria in normal-form games.
Definition . Let and be two flows in associated with the same sets and. In what follows, we will drop the subscript to make the notation clearer. Assume to fix the latencies induced by on the graph: the conditional welfare of with respect to is defined as
Fact 1. Given a Nash-equilibrium flow and any other flow,.
Proof . Assume that. By definition,
Since and are associated with the same sets, we know that
Therefore, there must be a pair and two paths from to such that,, and
In other words, the flow can achieve a lower welfare than only if there are two paths from to having different costs, and if reroutes some flow of from the higher-cost path to the lower-cost path. This situation is clearly incompatible with the assumption that is a Nash-equilibrium flow.
Q.E.D.
Note that Fact 1 does not assume any particular structure on the set.
Fact 2. Given any two real numbers and,.
Proof. This is another way to express the true inequality.
Q.E.D.
Theorem. The pure PoA of any generalized routing problem with linear latencies is.
Proof. Note that this theorem is equivalent to saying that for each Nash-equilibrium flow,, where is any other flow. By definition,
By using Fact 2, we have that
since
We can conclude that, and prove the thesis using Fact 1.
Q.E.D.
Note that in the proof we have made extensive use of the assumption that the functions in are linear. Actually, a more general fact holds.
Theorem. Given a generalized routing problem with graph and polynomial latency functions of degree with nonnegative coefficients, the pure PoA is.
Note that the PoA can grow with. Consider the example shown in the following figure, where we assume unit flow: the Nash-equilibrium flows have social welfare 1; however, the best welfare is achieved when, in which case
This quantity tends to zero when tends to infinity.