The price of anarchy is independent of the network topology

By Tim Roughgarden. Symposium on the Theory of Computing, 2002

602 citations recorded by the source corpus.

Subfields: Management Science and Operations Research, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/2819fe2af0c7a86d74b8efb7849d81db812ceb2c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Statistical and Nonlinear Physics

Citations in the corpus

Bounding the inefficiency of equilibria in nonatomic congestion games (2004, methodology): “Our results extend previous work on traffic routing games [16, 17, 18].”
Tight bounds for worst-case equilibria (2002, background): “We believe that understanding the ratio between worst possible Nash quilibrium and the social optimum in simple situations is necessary for making rigorous analyses in more complicated networks (see also the recent work of Roughgarden [ Rou02 ] that gives an additional support to this claim).”
Efficiency loss in a network resource allocation game: the case of elastic supply (2004, background): “We note that a similar bound was observed by Roughgarden and Tardos (2002) for traffic routing games with affine link latency functions.”
Joint Strategy Fictitious Play with Inertia for Potential Games (2005, background): “It is well known that a Nash equilibrium may not minimize the total congestion experienced by all drivers [ 33 ].”
Selfish Routing in Capacitated Networks (2004, unknown): “In this paper, we extend the work of Roughgarden and Tardos (2002a) and Roughgarden (2002) to network models that are more realistic.”
Network games (2004, background): “There has been considerable progress on questions arising from this perspective for many problems including routing [29, 31], load balancing [4, 6, 25, 30, 32],”
Program equilibrium (2004, background): “Examples include work on issues such as selfish routing [11] or incorporating distributed systems features into game-theoretic models [7].”
The price of stability for network design with fair cost allocation (2004, background): “This establishes that the fair cost allocation protocol is in fact a useful mechanism for inducing strategic behavior to form nearoptimal equilibria.”
Selfish routing and the price of anarchy (2005, background): “Roughgarden [65] extended this proof and established Theorem 2.”