ALCOMFT-TR-03-138

Thomas Lucking, Marios Mavronicolas, Burkhard Monien and Manuel Rode
A New model for Selfish Routing
Paderborn and Cyprus. Work packages 2 and 4. December 2003.

Abstract: In this work, we introduce and study a new model for selfish routing over non-cooperative networks that combines features from the two such best studied models, namely the KP model and the Wardrop model in an interesting way.

We consider a set of n users, each having a mixed strategy to ship its unsplittable traffic over a network consisting of m parallel links. In an Nash equilibrium, no user can decrease its Individual Cost by unilaterally deviating from its strategy. To evaluate the performance of such Nash equilibria, we introduce Quadratic Social Cost as a certain sum of Individual Costs - namely, the sum of the expectations of the squares of the incurred link latencies. This definition is unlike the KP model, where Maximum Social Cost has been defined as the maximum of Individual Costs.

We are interested in understanding the impact of our modeling assumptions on the various algorithmic, combinatorial, structural and optimality properties of Nash equilibria in this new model. The findings of our study are outlined as follows.

• We present a comprehensive collection of elegant, combinatorial expressions for the computation of Quadratic Social Cost. These expressions readily imply some polynomial algorithms to compute Quadratic Social Cost in several special cases, and a corresponding general, pseudopolynomial, dynamic programming algorithm.

• Through an elegant combinatorial analysis, we prove, as our main result, that, for the model of identical users and identical links, the worts-case Nash equilibrium - the one that maximizes Quadratic Social Cost - is the fully mixed Nash equilibrium, where each user assigns (strictly) positive probability to every link.

• Finally, we present a comprehensive collection of (usually tight) constant (that is, independent of m and n) lower and upper bounds on Quadratic Coordination Ratio, the variant of Maximum Coordination Ratio (defined using Maximum Social Cost) that we define using Quadratic Social Cost, in a number of models.

  Some of these constant bounds stand in very sharp contrast to corresponding Theta( (lg m)/( lg lg m )) bounds on Maximum Coordination Ratio, which were previously shown for the KP model. \enditemize

Postscript file: ALCOMFT-TR-03-138.ps.gz (180 kb).