Paper Info
Title
Strong and Pareto Price of Anarchy in Congestion Games
Abstract
Strong Nash equilibria and Pareto-optimal Nash equilibria are natural and important strengthenings of the Nash equilibrium concept. We study these stronger notions of equilibrium in congestion games, focusing on the relationships between the price of anarchy for these equilibria and that for standard Nash equilibria (which is well understood). For symmetric congestion games with polynomial or exponential latency functions, we show that the price of anarchy for strong and Pareto-optimal equilibria is much smaller than the standard price of anarchy. On the other hand, for asymmetric congestion games with polynomial latencies the strong and Pareto prices of anarchy are essentially as large as the standard price of anarchy; while for asymmetric games with exponential latencies the Pareto and standard prices of anarchy are the same but the strong price of anarchy is substantially smaller. Finally, in the special case of linear latencies, we show that in asymmetric games the strong and Pareto prices of anarchy coincide exactly with the known value $\frac{5}{2}$ for standard Nash, but are strictly smaller for symmetric games.
Year
DOI
Venue
2009
10.1007/978-3-642-02927-1_24
ICALP
Keywords
Field
DocType
standard nash equilibrium,strong nash equilibrium,congestion games,pareto-optimal nash equilibrium,strong price,standard nash,pareto price,nash equilibrium concept,asymmetric game,asymmetric congestion game,standard price,nash equilibria,nash equilibrium,price of anarchy
Congestion game,Combinatorics,Mathematical economics,Epsilon-equilibrium,Price of stability,Computer science,Best response,Price of anarchy,Nash equilibrium,Pareto principle,Special case
Conference
Volume
ISSN
Citations 
5555
0302-9743
16
PageRank 
References 
Authors
0.71
15
2
Name
Order
Citations
PageRank
Steve Chien132319.12
Alistair Sinclair21506308.40