University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Publications

Back to Publications

Author(s) Hoefer, M., Souza, A.
Title Tradeoffs and average-case equilibria in selfish routing
Abstract We consider the price of selfish routing in terms of tradeoffs and from an average-case 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 message-length. 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 average-case analyses of a local search algorithm that computes Nash equilibria in polynomial time.
Download HoSo07.pdf

Back to Publications