The Price of Anarchy (PoA)
is a concept in
economics
Economics () is the social science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services.
Economics focuses on the behaviour and intera ...
and
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
that measures how the
efficiency
Efficiency is the often measurable ability to avoid wasting materials, energy, efforts, money, and time in doing something or in producing a desired result. In a more general sense, it is the ability to do things well, successfully, and without ...
of a system degrades due to
selfish
Selfishness is being concerned excessively or exclusively, for oneself or one's own advantage, pleasure, or welfare, regardless of others.
Selfishness is the opposite of altruism or selflessness; and has also been contrasted (as by C. S. Lewis) w ...
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
A game is a structured form of play (activity), play, usually undertaken for enjoyment, entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator s ...
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.). Different concepts of equilibrium can be used to model the selfish behavior of the agents, among which the most common is the
Nash equilibrium
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
. 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.
[M. Goemans, V. Mirrokni, A. Vetta, ]
Sink equilibria and convergence
', FOCS 05
The term Price of Anarchy was first used by
Elias Koutsoupias
Education
Elias Koutsoupias is a Greek computer scientist working in algorithmic game theory.
Koutsoupias received his bachelor's degree in electrical engineering from the National Technical University of Athens and his doctorate in computer ...
and
Christos Papadimitriou
Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia Un ...
,
but the idea of measuring inefficiency of equilibrium is older.
[P. Dubey. Inefficiency of Nash equilibria. Math. Operat. Res., 11(1):1–8, 1986] The concept in its current form was designed to be the analogue of the 'approximation ratio' in an
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
or the 'competitive ratio' in an
online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.
In contrast, an o ...
. This is in the context of the current trend of analyzing games using algorithmic lenses (
algorithmic game theory
Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.
Typically, in Algorithmic Game Theory problems, the input t ...
).
Mathematical definition
Consider a game
, 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 include the sum of players utilities (utilitarian objective)
minimum utility (fairness or egalitarian objective)
..., 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 (for example, the set of
Nash equilibria
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
). 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' (e.g. delay in a network) we use (following the convention in approximation algorithms):
A related notion is that of the
Price of Stability
In game theory, the price of stability (PoS) of a game is the ratio between the best objective function value of one of its equilibria and that of an optimal outcome. The PoS is relevant for games in which there is some objective authority that ...
(PoS) 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
The Prisoner's Dilemma is an example of a game analyzed in game theory. It is also a thought experiment that challenges two completely rational agents to a dilemma: cooperate with their partner for mutual reward, or betray their partner ("defe ...
, given by the following cost matrix:
and let the cost function be
Now, the worst (and only)
Nash Equilibrium
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
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
. 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
In operations research, the makespan of a project is the length of time that elapses from the start of work to the end. This type of multi-mode resource constrained project scheduling problem (MRCPSP) seeks to create the shortest logical project sc ...
.''
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. 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 (or higher ranked) 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's paradox
Consider a road network as shown in the adjacent diagram on which 4000 drivers wish to travel from point Start to End. The travel time in minutes on the Start–A road is the number of travelers (T) divided by 100, and on Start–B is a constant 45 minutes (likewise with the roads across from them). If the dashed road does not exist (so the traffic network has 4 roads in total), the time needed to drive Start–A–End route with
drivers would be
. The time needed to drive the Start–B–End route with
drivers would be
. As there are 4000 drivers, the fact that
can be used to derive the fact that
when the system is at equilibrium. Therefore, each route takes
minutes. If either route took less time, it would not be a Nash equilibrium: a rational driver would switch from the longer route to the shorter route.
Now suppose the dashed line A–B is a road with an extremely short travel time of approximately 0 minutes. Suppose that the road is opened and one driver tries Start–A–B–End. To his surprise he finds that his time is
minutes, a saving of almost 25 minutes. Soon, more of the 4000 drivers are trying this new route. The time taken rises from 40.01 and keeps climbing. When the number of drivers trying the new route reaches 2500, with 1500 still in the Start–B–End route, their time will be
minutes, which is no improvement over the original route. Meanwhile, those 1500 drivers have been slowed to
minutes, a 20-minute increase. They are obliged to switch to the new route via A too, so it now takes
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. If every driver were to agree not to use the A–B path, or if that route were closed, every driver would benefit by a 15-minute reduction in travel time.
Generalized routing problem
The routing problem introduced in the Braess's 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
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 (Nash-equilibrium flow). 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 (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
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.
See also
*
Tragedy of the commons
Tragedy (from the grc-gre, τραγῳδία, ''tragōidia'', ''tragōidia'') is a genre of drama based on human suffering and, mainly, the terrible or sorrowful events that befall a main character. Traditionally, the intention of tragedy ...
*
Competitive facility location game The competitive facility location game is a kind of competitive game in which service-providers select locations to place their facilities in order to maximize their profits.Eva Tardos and Tom Wexler, "Network Formation Games". Chapter 19 in The g ...
- a game with a small price-of-anarchy.
*
Price of anarchy in auctions
The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in aucti ...
References
* Tim Roughgarden and Eva Tardos, "Introduction to the Inefficiency of Equilibria". Chapter 17 in .
*
Further reading
* Fabio Cunial
Price of anarchy
{{DEFAULTSORT:Price Of Anarchy
Game theory