The Price of Anarchy (PoA) is a concept in 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.
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), Bayes-Nash Price of Anarchy (for games with incomplete information), ... Other notions, other than Nash equilibria, 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 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).
Read more about Price Of Anarchy: Mathematical Definition, See Also
Famous quotes containing the words price of, price and/or anarchy:
“One has to have run a household before one can know the price of rice and firewood, and one has to have raised children before one can understand a parent’s love.”
—Chinese proverb.
“For what were all these country patriots born?
To hunt, and vote, and raise the price of corn?”
—George Gordon Noel Byron (1788–1824)
“It’s the anarchy of poverty
delights me, the old
yellow wooden house indented
among the new brick tenements”
—William Carlos Williams (1883–1963)