Martin Hoefer and Alexander Souza
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: |
|