[Nrg-l] Remainder - December 3rd @ 3pm

Jorge Londoño jmlon at cs.bu.edu
Fri Nov 30 15:51:58 EST 2007

Next Monday Joseph will be presenting the following paper, which
appeared in FOCS04:

The Price of Stability for Network Design with Fair Cost Allocation
Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg , Eva Tardos, Tom
Wexler and Tim Roughgarden


Network design is a fundamental problem for which it is important to
understand the effects of strategic behavior. Given a collection of
self-interested agents who want to form a network connecting certain
endpoints, the set of stable solutions- the Nash equilibria - may look
quite different from the centrally enforced optimum. We study the quality
of the best Nash equilibrium, and refer to the ratio of its cost to the
optimum network cost as the price of stability. The best Nash equilibrium
solution has a natural meaning of stability in this context - it is the
optimal solution that can be proposed from which no user will defect". We
consider the price of stability for network design with respect to one of
the most widely-studied protocols for network cost allocation, in which
the cost of each edge is divided equally between users whose connections
make use of it; this fair-division scheme can be derived from the Shapley
value, and has a number of basic economic motivations. We show that the
price of stability for network design with respect to this fair cost
allocation is O(log k), where k is the number of users, and that a good
Nash equilibrium can be achieved via best-response dynamics in which users
iteratively defect from a starting solution. This establishes that the
fair cost allocation protocol is in fact a useful mechanism for inducing
strategic behavior to form near-optimal equilibria. 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 costs. We also present bounds
on the convergence time of best-response dynamics, and discuss extensions
to a weighted game.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://cs-mailman.bu.edu/pipermail/nrg-l/attachments/20071130/afad2f72/attachment.html 

More information about the Nrg-l mailing list