2005 · 444 citations · 18 references
Social SciencesEconomicsGame TheoryMicroeconomicsPricing TheoryCongestion ControlGeneral EquilibriumMarket EquilibriumNash EquilibriumNetwork GamesNoncooperative Game TheoryFinite GamesNash Equilibrium PricingNetwork Congestion GamesNetwork Equilibrium
The authors investigate the price of anarchy of pure Nash equilibria in congestion games, extending their analysis to polynomial latency functions and mixed Nash equilibria. They analyze congestion games with linear latency functions, then generalize the results to bounded‑degree polynomial latency functions and to mixed Nash equilibria. They find that for asymmetric games the maximum‑social‑cost price of anarchy grows as Θ(√N), while in all other symmetric or asymmetric cases and for both maximum and average social cost it equals 5/2.
We consider the price of anarchy of pure Nash equilibria in congestion games with linear latency functions. For asymmetric games, the price of anarchy of maximum social cost is Θ(√N), where N is the number of players. For all other cases of symmetric or asymmetric games and for both maximum and average social cost, the price of anarchy is 5/2. We extend the results to latency functions that are polynomials of bounded degree. We also extend some of the results to mixed Nash equilibria.
18
Dov Monderer, Lloyd S. Shapley · Games and Economic Behavior · 1996 · 3.5K citations
Tim Roughgarden, Éva Tardos · Journal of the ACM · 2002 · 1.6K citations
Algorithms, games, and the internet
Christos H. Papadimitriou · 2001 · 1.1K citations
The complexity of pure Nash equilibria
Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar · 2004 · 662 citations