Price of anarchy - AbsoluteAstronomy.com

The Price of Anarchy is a concept in game theory

Game theory

Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

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.

Usually the system is modeled as a game

Game theory

Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

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 concept of equilibrium can be used to model the selfish behavior of the agents, among which the most common is the Nash Equilibrium

Nash equilibrium

In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...

. 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), Bayes-Nash Price of Anarchy (for games with incomplete information), ... Other notions, other than Nash, lead to variations of the concept, 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 Approximation Algorithms or the 'competitive ratio' in Online Algorithms. This is in the context of the current trend of analyzing games using algorithmic lenses (Algorithmic Game Theory

Algorithmic game theory

Algorithmic game theory is an area in the intersection of game theory and algorithm design, whose objective is to design algorithms in strategic environments. Typically, in Algorithmic Game Theory problems, the input to a given algorithm is distributed among many players who have a personal...

Mathematical definition

Consider a game

Game

A game is structured playing, usually undertaken for enjoyment and sometimes used as an educational tool. Games are distinct from work, which is usually carried out for remuneration, and from art, which is more often an expression of aesthetic or ideological elements...

, defined by a set of players

, strategy sets

for each player and utilities

(where

also called set of outcomes). We can define a measure of efficiency of each outcome which we call welfare function

. Natural candidates as sum of players utilities (utilitarian objective)

, minimum utility (fairness or egalitarian objective)

, ... or any function that is meaningful for the particular game being analyzed.

We can define a subset

to be the set of strategies in equilibrium (for example, the set of Nash equilibria). The Price of Anarchy is then defined as the ratio between the optimal 'centralized' solution and the 'worse equilibrium':

Following the convention in approximation algorithms, if the function measure efficiency is, instead of a 'welfare' we want to 'maximize', a 'cost function'

we want to 'minimize' (delay in a network, for example) we use:

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

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'.

Prisoner's dilemma

Consider the 2x2 game called Prisoner's dilemma, given by the following payoff matrix:

	Cooperate	Defect
Cooperate	1, 1	7, 0
Defect	0, 7	5, 5

and let the cost function be

. Now, the minimum cost function would be when both players cooperate and the resulting cost is

, however the only Nash equilibrium

Nash equilibrium

occurs when both defect the cost in such a situation is

, so the Price of Anarchy of this game will be

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

, i.e., the load of the machine she 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 (this inequality can be strict: e.g. when

, and

, the mixed strategies

achieve an average makespan of 1.5, while any pure-strategy PoA in this setting is

). 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 (all having the same maximum load). 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 (i.e., smallest) load, where there can only be one distribution of loads (unique up to permutation). This would also be called the lexicographic smallest sorted load vector.

We claim that this is a pure-strategy nash equilibrium. Suppose not. Suppose that some player

could strictly improve by moving from machine

to machine

. This means that the larger of the two loads must go down, because

must have been using the machine with larger load in both cases. But this violates the 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

Consider, for clarity of exposition, any pure-strategy action profile

: clearly

Since the above holds for the social optimum as well, correlating the ratios

and

proves the claim. Q.E.D

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

(imagine the flow to be composed of the travel decisions of the different drivers). 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

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

Social cost

Social cost, in economics, is generally defined in opposition to "private cost". In economics, theorists model individual decision-making as measurement of costs and benefits...

1.5, and it takes 1.5 units of time to each driver to go from

. 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

Social cost

Social cost, in economics, is generally defined in opposition to "private cost". In economics, theorists model individual decision-making as measurement of costs and benefits...

would increase to 2 and now it would take 2 units of time to each player 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

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

, with the constraint that

The flow traversing a specific edge of

is defined as

For succinctness, we write

when

are clear from context.

Definition (Nash-equilibrium flow). A flow

is a Nash-equilibrium flow iff

and

from

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

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 (By contradiction). 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

such that

, and

In other words, the flow

can achieve a lower welfare than

only if there are two paths from

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.

Mathematical definition

Prisoner's dilemma

Job scheduling

Braess' paradox

Generalized routing problem

Further reading