The Price of selfish Routing

E I N L A D U N G


Hiermit lade ich Sie zur öffentlichen Antrittsvorlesung von Herrn

Dr. Berthold V Ö C K I N G am
http://www.mpi-sb.mpg.de/~voecking/

Freitag, dem 22.02.2002, 14 Uhr c.t.,
in den Hörsaal 024, Gebäude 46 (MPI)

ein.

"The Price of selfish routing"
http://www.cs.uni-sb.de/top/antritt.php

A fundamental problem arising in the management of large-scale traffic and
communication networks is that of routing traffic to optimize network
performing. It is often difficult or even impossible to impose optimal or
near-optimal routing strategies on the traffic in a network; in these
settings, network users are free to act according to their own interest,
without regard to overall network performance.
The central question of this task is how much does network performance
suffer from this lack of regulation? - As the first step toward this
question mathematically, we assume that, in the absence of network
regulation, users act in a purely selfish manner. Under this assumption, we
can view network users as independent agents participating in a
non-cooperative game and expect the routes chosen by users to form a Nash
equilibrium in the sense of classical game theory.
We present first results from this new, fascinating area of research. The
talk gives an overview over models and results introduced in recent articles
by Roughgarden, Tardos, Koutsoupias, Papadimitriou, Mavrolinkas, Spirakis as
well as Czumaj, Krysta and myself.

Professor Dr. R. SCHULZE-PILLOT-ZIEMEN
Dekan der NTF I