ALCOMFT-TR-02-110

Elias Koutsoupias, Marios Mavronicolas and Paul Spirakis
Approximate Equilibria and Ball Fusion
Patras and Cyprus. Work packages 2 and 4. May 2002.

Abstract: We consider selfish routing over a network consisting of m parallel links. We assume a collection of n users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of its own assigned traffic. The expected latency through a link is taken to be the expectation of the traffic assigned to the link; all users sharing a link incur the same expected latency cost, taken to be the link's expected latency. In an approximate equilibrium, each user selfishly routes its traffic so that the expected latency of any link is at most a constant multiple of the optimum (i.e., the least possible) maximum latency had global regulation been available.

We introduce and study the approximate coordination ratio, defined as the ratio of the maximum (over all links) expected latency in the worst possible approximate equlibrium, over the least possible maximum latency had global regulation been available, as a measure of the cost of lack of coordination among the users. The load balancing aspect of our selfish routing problem immediately implies a lower bound of Omega( (\ln m)/(\ln \ln m )) on approximate coordination ratio. The main result of our work provides a corresponding upper bound to establish that this lower bound is \emphtight. To show the upper bound, we introduce and analyze a novel variant of the classical \emphballs and bins problem, in which balls with arbitrary \emphweights are placed into bins according to arbitrary probability distributions; this variant may be of independent interest. A central milestone to our analysis of the variant of the balls and bios problem we consider is a new probabilistic tool that we introduce here and call \emphball fusion; this tool is used to reduce the variant of the problem where balls bear weights to the classical version (with no weights).

Postscript file: ALCOMFT-TR-02-110.ps.gz (62 kb).