The Price of Anarchy

The Price of Anarchy measures the gap between the best possible outcome in a game (when a central planner coordinates everyone) and the worst Nash equilibrium (when everyone acts selfishly). The concept was formalised by Elias Koutsoupias and Christos Papadimitriou in 1999 and named by Papadimitriou in a 2001 paper. The motivating example is traffic routing. In a network where each driver independently chooses the fastest route, the total travel time can be significantly worse than if a central authority assigned routes optimally. Tim Roughgarden proved in his 2002 thesis that in networks with linear latency functions, selfish routing can be at most 4/3 times worse than optimal — a tight bound. But for more general latency functions, and for broader classes of games, the Price of Anarchy is often unknown. The concept connects directly to Braess's paradox: adding capacity to a network can increase the Price of Anarchy, making selfish behaviour even more costly. The Price of Anarchy has been computed for congestion games, auctions, cost-sharing games, and network design games, but many important game families remain open. The Academy hosts the Price of Anarchy in the World School because it quantifies the cost of competition — the exact tax the world pays when players refuse to cooperate — and for many of the games that matter most, we do not know how high that tax is.

Elias Koutsoupias and Christos Papadimitriou, "Worst-Case Equilibria," STACS, 1999. Christos Papadimitriou, "Algorithms, Games, and the Internet," STOC, 2001. Tim Roughgarden and Éva Tardos, "How Bad Is Selfish Routing?", Journal of the ACM 49(2), 2002. Tim Roughgarden, Selfish Routing and the Price of Anarchy (MIT Press, 2005). The connection to Braess's paradox: Dietrich Braess, "Über ein Paradoxon aus der Verkehrsplanung," Unternehmensforschung 12, 1968. Noam Nisan et al., eds., Algorithmic Game Theory (Cambridge University Press, 2007).