Tight bounds for worst-case equilibria

By Artur Czumaj, Berthold Vöcking. ACM-SIAM Symposium on Discrete Algorithms, 2002

355 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/99aeed42c49d09a06900ce3b38a287f21d112e30

How researchers see this paper

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

Citations in the corpus

Stackelberg scheduling strategies (2001, methodology): “Our approach also adds an algorithmic dimension to the existing studies comparing Nash equilibria and optimal solutions [ 8 , 20, 22, 31, 32], in that one aspect of our analysis of Stackelberg equilibria is the design of algorithms for efficiently computing good Stackelberg strategies.”
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],”
The price of stability for network design with fair cost allocation (2004, background): “We discuss connections to the class of potential games defined by Monderer and Shapley, and extend our results to cases in which users are seeking to balance network design costs with latencies in the constructed network, with stronger results when the network has only delays and no construction…”
The price of anarchy of finite congestion games (2005, background): “The price of anarchy for the maximum social cost, expressed as a function of m, is Θ(logm/ log logm)— the lower bound was shown in [13] and the upper bound in [12, 6].”
The price of anarchy is independent of the network topology (2002, background): “More recently, Roughgarden and Tardos [19] extended these results to a broader class of games (that need not take place in a network); Roughgarden [17] examined the inefficiency of Stackelberg (rather than Nash) equilibria when one player is a network manager wishing to optimize network performance;”