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 congestion games (CG).
In this example, selfish routing leads to a total delay that is 4/3 times higher than the optimum, so the price of anarchy is 4/3.
In general, the price of anarchy may differ based on the type of congestion game, the structure of the network, and the delay functions.
Various authors have computed upper and lower bounds on the PoA in various congestion games.
A congestion game (CG) is defined by a set of resources.
The function maps the amount of congestion in the resource (e.g. the number of drivers choosing to use the road) to the delay experienced by each player using it.
A Nash equilibirum is a situation in which no player can improve his delay by unilaterally changing his choice.
There are several main classes of congestion games: Another classification of CGs is based on the sets of strategies available to the players: Moreover: Christodoulou and Koutsoupias[2] analyzed atomic unweighted CGs.
In another paper, Christodoulou and Koutsoupias[3] analyzed the PoS of atomic unweighted congestion games with linear delay functions.
Aland, Dumrauf, Gairing, Monien and Schoppmann[5] computed the exact PoA for atomic CGs, for delay functions that are polynomials of degree at most d: The same bounds hold whenever no player can improve his expected cost by a unilateral deviation.
Moreover, the bounds hold for unweighted and weighted network congestion games.
Bhawalkar, Gairing and Roughgarden[6] analyze weighed CGs, and show how to compute the PoA for any class of cost functions (not necessarily polynomial).
They also show that, with polynomial cost functions, the worst-case PoA is attained on a simple network, consisting only of a set of parallel edges.
They also show that the PoA of symmetric unweighted congestion games is always equal to the asymmetric ones.
For singleton congestion games with affine cost functions, when there are n players, the sequential PoA is at most n-1; when
For symmetric singleton atomic congestion games with affine cost functions, the sequential PoA is exactly 4/3.
Fotakis[8] studies the PoA of CGs with linearly-independent paths, which is an extension of the setting of parallel links.
Law, Huang and Liu[9] study the PoA of CGs in cognitive radio networks.
Gairing, Burkhard and Karsten[10] study the PoA of CGs with player-specific linear delay functions.
In particular, when d=1, the PoA is 4/3; this shows that Pigou's simple example is the worst case for linear delay functions.
Chau and Sim[13] extend the results of Roughgarden and Tardos by (1) considering symmetric cost maps and (2) incorporating elastic demands.
Correa, Schulz and Stier-Moses[14] present a short, geometric proof to the results on PoA for nonatomic CGs.
Blum, Even-Dar and Ligett[15] showed that all these PoA bounds apply under relatively weak behavioral assumptions: it is sufficient that all users achieve vanishing average regret over repeated plays of the game.
[16] Mlichtaich[17] analyzed singleton nonatomic CGs, with the following additional characteristics: In such games, the equilibrium payoffs are always unique and Pareto-efficient, but may not maximize the sum of utilities.
Moreover: Roughgarden and Schoppmann[18] analyzed splittable congestion games.
For example: The basic CG model assumes that players are selfish - they care only about their own payoff.
In fact, players may be altruistic and care about the social cost too.
[21][22] An alternative way to measure the effect of altruism on efficiency is via comparative statics: in a single game (not necessarily worst-case one), how does increasing the altruism coefficient affect the social cost?