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:
“I sometimes think that the price of liberty is not so much eternal vigilance as eternal dirt.”
—George Orwell (1903–1950)
“This state is full of these log cabin Abe Lincolns with price tags on ‘em. The louder he yells, the higher his price.”
—Robert Rossen (1908–1966)
“Things fall apart; the centre cannot hold;
Mere anarchy is loosed upon the world,
The blood-dimmed tide is loosed, and everywhere
The ceremony of innocence is drowned;
The best lack all conviction, while the worst
Are full of passionate intensity.”
—William Butler Yeats (1865–1939)