Abstract of Paper

Selfish Routing in Non-Cooperative Networks: A Survey
by R. Feldmann, M. Gairing, T. Luecking, B. Monien and M. Rode

Abstract:

We study the problem of $n$ users selfishly routing traffics through a
shared network. Users route their
traffics by choosing a path from their source to their destination of the
traffic with the aim of minimizing their private latency. In such an
environment Nash equilibria represent stable states of the system: no
user can improve its private latency by unilaterally changing its
strategy.

In the first model the network consists only of a single source and a
single destination which are connected by $m$ parallel links.
Traffics are unsplittable. Users may route their traffics
according to a probability distribution over the links.
The social optimum minimizes the maximum load of a link.
In the second model the network is arbitrary, but traffics are splittable
among several paths leading from their source to their destination.
The goal is to minimize the sum of the edge latencies.

Many interesting problems arise in such environments:
A first one is the problem of analyzing the
loss of efficiency due to the lack of central regulation, expressed in
terms of the coordination ratio.
A second problem is the Nashification problem, i.e.
the problem of converting any given non-equilibrium
routing into a Nash equilibrium without increasing the social cost.
The Fully Mixed Nash Equilibrium Conjecture (\FMNE Conjecture) states that
a Nash equilibrium, in which every user routes along every possible
edge with probability greater than zero, is a worst Nash equilibrium
with respect to social cost. A third problem is to exactly specify the
sub-models in which the \FMNE Conjecture is valid.
The well-known Braess's Paradox shows that there exist
networks, such that strict sub-networks perform better when users are
selfish.
A natural question is the following network design
problem: Given a network, which edges should be removed to obtain the
best possible Nash equilibrium.

We present complexity results for various problems in this setting,
upper and lower bounds for the coordination ratio, and
algorithms solving the problem of Nashification.
We survey results on the validity of the
\FMNE Conjecture in the model of unsplittable
flows, and for the model of splittable flows we survey results for the
network design problem.