Approximate Equilibria and Ball Fusion |
| |
Authors: | Elias Koutsoupias Marios Mavronicolas and Paul Spirakis |
| |
Affiliation: | (1) Department of Computer Science, University of California at Los Angeles, 405 Hilgard Avenue, Los Angeles, CA 90095-1361, USA and Department of Informatics, University of Athens, 15771 Athens, Greece;(2) Department of Computer Science, University of Cyprus, Nicosia CY-1678, Cyprus , Cyprus;(3) Department of Computer Engineering and Informatics, University of Patras, 265 00 Patras and Computer Technology Institute, 261 10 Patras, Greece |
| |
Abstract: | We consider selfish routing over a network consisting of m parallel
links through which $n$ selfish users route their traffic trying to
minimize their own expected latency. We study the class of mixed
strategies in which the expected latency through each link is at most
a constant multiple of the optimum maximum latency had global
regulation been available. For the case of uniform links it is known
that all Nash equilibria belong to this class of strategies. We are
interested in bounding the coordination ratio (or price of anarchy) of
these strategies defined as the worst-case ratio of the maximum (over
all links) expected latency over the optimum maximum latency. The load
balancing aspect of the problem immediately implies a lower bound
Ω(ln m ln ln m) of the coordination
ratio. We give a tight (up to a multiplicative constant) upper bound.
To show the upper bound, we analyze a variant of the classical balls
and bins problem, in which balls with arbitrary weights are placed
into bins according to arbitrary probability distributions. At the
heart of our approach is a new probabilistic tool that we call ball
fusion; this tool is used to reduce the variant of the problem where
balls bear weights to the classical version (with no weights). Ball
fusion applies to more general settings such as links with arbitrary
capacities and other latency functions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|