Price of anarchy
The ratio of the social cost of the worst Nash equilibrium to the social cost of the optimum is bounded above by a constant that depends on the class of cost functions and not on the size of the game, and for selfish routing with affine latencies that constant is 4/3 however complicated the network.
The ratio of the social cost of the worst Nash equilibrium to the social cost of the optimum is bounded above by a constant that depends on the class of cost functions and not on the size of the game, and for selfish routing with affine latencies that constant is 4/3 however complicated the network.
Games that show it
Know these first
When it stops being true
- continuum-of-players
- complete-information
Sources
- Roughgarden, T. (2005). MIT Press.
- Braess, D. (1968). Unternehmensforschung 12, 258-268.
- Pigou, A. C. (1920). Macmillan.