Price of anarchy
The price of anarchy is an economics and game theory term that measures the effect of selfish behavior on the efficiency of a system. The system is modeled as a game and efficiency is a function that assigns a number to every strategy combination.
The term was mentioned by Koutsoupias and Papadimitriou , but the idea is older. Related concepts are the quality of approximation algorithms and the competitiveness of online algorithms .
definition
The term comes from the English "Price of Anarchy" and describes the relationship between the profit in the entire system with selfish behavior of the players and the optimal profit. Here, selfish behavior usually means a choice of strategies that corresponds to a Nash equilibrium , i. H. each player chooses the optimal strategy for himself on the assumption that all other players stick to their current strategy. In contrast to this, the optimal profit is achieved through a socially optimal choice of strategies which maximizes the profit of the entire system.
Example route planning
When planning a route, it is easy to see the relationship between socially optimal planning and selfish behavior. In general, routes are planned in such a way that each individual person chooses the best route for himself, knowing the current traffic situation. This corresponds to a Nash equilibrium.
This results in a certain paradox in road traffic: the construction of expressways does not always reduce the total traffic jam time in a system. In 1990, as an environmental action by New York's commissioner, the 42nd street with the most traffic jams was closed for one day. Surprisingly, with the same volume of traffic, this led to less traffic jams overall in the city, even though one of the most heavily used roads was eliminated. This is also known as the Braess paradox. It can be explained by the fact that adding new roads can only reduce the socially optimal traffic jam time in the system. In the case of selfish behavior, adding a new road can worsen the Nash equilibria. B. by everyone using the new major road and there are major traffic jams.
If we assume that the traffic jam on a road is dependent on the amount of traffic on the road, we can limit the price of anarchy. In other words, in such a system the ratio between the worst result of a Nash equilibrium and the socially optimal travel time is the highest .
