Publications
Back to Publications
Author(s) 
Hoefer, M., Souza, A. 
Title 
Tradeoffs and averagecase equilibria in selfish routing 
Abstract 
We consider the price of selfish routing in terms of tradeoffs and from an averagecase perspective. Each player in a network game seeks to send a message with a certain length by choosing one of several parallel links that have transmission speeds. A player desires to minimize his own transmission time (latency). We study the quality of Nash equilibria of the game, in which no player can decrease his latency by unilaterally changing his link. In this paper we treat two important aspects of network traffic management: the influence of the total traffic upon network performance and fluctuations in the lengths of the messages. We introduce a probabilistic model where message lengths are random variables and evaluate the expected price of anarchy of the game for various social cost functions.
For total latency social cost, which was only scarcely considered in previous work so far, we show that the price of anarchy is Θ(n/t), where n is the number of players and t the total messagelength. The bound states that the relative quality of Nash equilibria in comparison with the social optimum increase with increasing traffic. This result also transfers to the situation when fluctuations are present, as the expected price of anarchy is O(n/)/(E(T)), where (E(T) is the expected traffic. For maximum latency the expected price of anarchy is even 1 + o(1) for sufficiently large traffic.
Our results also have algorithmic implications. For the special case of identical links, we give an algorithm for computing the social optimum for total latency cost in polynomial time. Furthermore, our analyses of the expected prices are averagecase analyses of a local search algorithm that computes Nash equilibria in polynomial time. 
Download 
HoSo07.pdf 
Back to Publications
