A new model for selfish routing
Date
2004Author
Lücking, T.Mavronicolas, Marios
Monien, Burkhard
Rode, M.
Source
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Volume
2996Pages
547-558Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
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 using a mixed strategy to ship its unsplittable traffic over a network consisting of m parallel links. In a Nash equilibrium, no user can increase 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 analyse the impact of our modeling assumptions on the computation of Quadratic Social Cost, on the structure of worst-case Nash equilibria, and on bounds on the Quadratic Coordination Ratio. © Springer-Verlag 2004.