research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleApproximate Equilibria and Ball Fusion
Bibtex cite IDRACTI-RU1-2003-25
Journal Theory of Computing Systems
Year published 2003
Month December
Volume 36
Number 6
Pages 683-693
ISSN 1432-4350 (Print) 1433-0490 (Onl
DOI 10.1007/s00224-003-1131-5
We consider selfish routing over a network consisting of m parallellinks through which $n$ selfish users route their traffic trying tominimize their own expected latency. We study the class of mixedstrategies in which the expected latency through each link is at mosta constant multiple of the optimum maximum latency had globalregulation been available. For the case of uniform links it is knownthat all Nash equilibria belong to this class of strategies. We areinterested in bounding the coordination ratio (or price of anarchy) ofthese strategies defined as the worst-case ratio of the maximum (overall links) expected latency over the optimum maximum latency. The loadbalancing aspect of the problem immediately implies a lower boundO(ln m ln ln m) of the coordinationratio. We give a tight (up to a multiplicative constant) upper bound.To show the upper bound, we analyze a variant of the classical ballsand bins problem, in which balls with arbitrary weights are placedinto bins according to arbitrary probability distributions. At theheart of our approach is a new probabilistic tool that we call ballfusion; this tool is used to reduce the variant of the problem whereballs bear weights to the classical version (with no weights). Ballfusion applies to more general settings such as links with arbitrarycapacities and other latency functions.
Koutsoupias, Elias
Mavronicolas, Marios
Spirakis, Paul
fulltext.pdf (main file)
Publication ID289