Betrachtet man Kommunikationsnetzwerke, auf denen n
Agenten ihre Pakete durch ein gemeinsames Netzwerk von ihrer Quelle zu
ihrem Ziel schicken und dabei versuchen, ihre privaten
möglicherweise unterschiedlichen) Zielfunktionen zu optimieren,
ohne sich mit anderen Agenten abzusprechen, so spricht man von
nichtkooperativen Netzwerken
[KLO95,LO99]. Ein sehr bekanntes Beispiel ist
das Internet. Ein solches Netzwerk, welchem aufgrund seiner
Grösse oder Struktur eine zentrale Kontrollinstanz fehlt,
kann mit Hilfe der Spieltheorie als nichtkooperatives Spiel
modelliert werden [OR94]. Die Agenten
wählen eine eigene private Strategie. Im Kommunikationsnetzwerk
entspricht das einer Wahrscheinlichkeitsverteilung über alle
Pfade von ihrer Quelle zu ihrem Ziel. Falls es den Agenten nicht
erlaubt ist, eine randomisierte Strategie zu wählen, d.h., wenn
sie sich für genau einen Pfad entscheiden müssen, dann
sprechen wir von reinen Strategien. Jeder Agent versucht, die
erwartete Latenz auf seinem Pfad zu minimieren, ohne dabei auf die
globalen/sozialen Kosten zu achten. Ein Nash Equilibrium
[Nas51] ist ein Zustand in einem solchen System,
in dem kein Agent durch einseitiges ändern seiner Strategie seine
privaten Kosten verbessern kann.
KP-Modell
Ist es den Agenten nicht erlaubt, ihre Pakete zu teilen und auf
verschiedenen Pfaden zu verschicken, so gestaltet sich eine Analyse
schon auf einfachen Netzwerken sehr schwierig. Koutsoupias und
Papadimitriou betrachten deshalb ein besonders einfaches Netzwerk [KP99]. Es besteht nur aus zwei Knoten, Quelle und
Ziel, die durch m parallele Links mit Kapazitäten
c1,...,cm
verbunden sind. Auf diesem Netzwerk wollen n Agenten Pakete der
Grösse w1,...,wn
von der Quelle zum Ziel verschicken. Trotz des einfachen Szenarios
lassen sich die wesentlichen Aspekte nichtkooperativen Verhaltens
beobachten. Es werden drei Szenarien
unterschieden: Falls alle Links die Kapazität 1 haben, sind sie
identisch. Die Links werden related genannt, falls sich
die Latenz auf einem Link als Quotient aus der Summe der
Paketgrössen auf diesem Link und seiner Kapazität ergibt. Im
allgemeinen Fall hängt die Latenz sowohl vom Agenten als auch vom
Link ab. Wir sprechen dann von unrelated Links (andere
Latenzfunktionen werden in [RT00]
untersucht). Ziel eines jeden Agenten ist es nun, die Latenz seines
Paketes, berechnet als Summe der Latenzen aller Pakete auf demselben
Link, zu minimieren. Die sozialen Kosten sind das Maximum der
Gesamtlatenzen auf den Links. Das beschriebene Modell ist als
KP-Modell bekannt und wurde intensiv untersucht:
Berechnung von Nash Equilibria
In einem greedy selfish step wechselt ein Agent auf den
für in besten verbessernden Link. Jede Folge solcher greedy
selfish steps endet irgenwann in einem reinen Nash
Equilibrium. Allerdings kann die Länge einer solchen Folge
exponentiell in n sein [EDKM03,FGL+03].
Mit Hilfe des Graham-Algorithmus lässt sich sowohl auf
identischen als auch auf related Links ein reines Nash Equilbrium
berechnen [FKK+02], dessen sozialen Kosten höchstens um
Faktor 19/12 von den minimalen Kosten entfernt sind [Dob84].
Best-case und worst-case Nash Equilibria
Es gibt immer ein reines Nash Equilibrium mit opimalen sozialen
Kosten. Allerdings ist es schon im Fall identischer
Linkkapazitäten NP-schwer, das beste
bzw. das schlechteste Nash Equilibrium zu berechnen [FKK+02]. Ein Nash
Equilibrium wird Fully Mixed Nash Equilibrium genannt, wenn
jeder Agent jeden Link mit positiver Wahrscheinlichkeit wählt [MS01]. Nach dem heutigen Kenntnisstand
scheinen im Falle der Existenz des Fully Mixed Nash Equilibriums
dessen soziale Kosten die sozialen Kosten eines beliebigen Nash
Equilibriums nach oben zu beschränken. Diese Vermutung, die
sogenannte Fully Mixed Conjecture [FKK+02], konnte
aber bisher nicht bewiesen werden. Im Fall identischer Links
lässt sich zeigen, dass die sozialen Kosten eines beliebigen Nash
Equilibriums höchstens um Faktor 6 höher sind als die des
Fully Mixed Nash Equilibriums [GLM+02]. Desweiteren wurde für einige
Spezialfälle sowohl auf identischen als auch auf related Links
die Vermutung bewiesen [LMM+03].
Verhältnis best-case zu worst-case Nash Equilibria
Koutsoupias und Papadimitriou [KP99]
schlugen als Effektivitätsmass in einem System mit
nichtkooperativen Agenten auf gemeinsamen Resourcen das
Verhältnis zwischen den grösstmöglichen sozialen Kosten
eines Nash Equilibriums und den Kosten im sozialen Optimum vor, die
sogenannte Coordination Ratio. Sie ist im KP-Modell für
related Links nach oben durch O(log(m)/log(log(log(m))))
beschränkt [CV02,KMS02].
Wardrop-Modell
Das Wardrop-Modell wurde schon in den 50er Jahren des letzen
Jahrhunderts [War56,BMW56] im Zusammenhang mit
Verkehrsnetzwerken untersucht. Im Gegensatz zum KP-Modell ist es den
Agenten erlaubt, ihre Pakete in beliebig viele Teile zu
zerlegen. Wardrop [War56]
führte Equilibria ein, um das Verhalten von Agenten in solchen
Verkehrsnetzwerken zu beschreiben. Eine Übersicht früher
Arbeiten in diesem Modell findet man in [Bec67].
Im Wardrop-Modell wird
unregulierter Verkehrsfluss als Netzwerkfluss modelliert. Für
ein gegebenes Netzwerk mit Kantenlatenzfunktionen lassen sich
Flüsse im Equilibrium als Flüsse mit gleicher Latenz auf
allen benutzten Pfaden, definiert als Summe der Kantenlatenzen,
zwischen einem gegebenen Quelle-Ziel-Paar klassifizieren. Falls die
Kantenlatenzen als konvexe Funktionen gegeben sind, sind Flüsse
im Equilibrium optimale Lösungen eines konvexen Programms.
Die praktische Relevanz des Wardrop-Modells wird durch seine Nutzung
durch Verkehrsforscher verdeutlicht, die Equilibria für
Navigationssysteme nutzen, um das Verhalten von Autofahrern
vorherzusagen. Die neuesten Analysen wurden von Schulz und Stier
Moses [SM02] für Netzwerke mit
Kantenkapazitäten durchgeführt. Algorithmen und Benchmarks
mit Szenarien aus der echten Welt findet man in Jahn et al. [JMSM02].
Flüsse im Equilibrium können als Nash Equilibria in einem Spiel mit
unendlich vielen Agenten interpretiert werden, wobei jeder Agent einen
infinitesimalen Anteil des Pakets von der Quelle zum Ziel
verschickt. Die individuellen Kosten eines Agenten sind als
Summe der Kantenlatenzen auf dem von ihm benutzten Pfad von der Quelle
zum Ziel definiert, und die sozialen Kosten als Summe aller
Kantenlatenzen im Netzwerk. Inspiriert durch das neue Interesse an der
Coordination Ratio untersuchten Roughgarden und Tardos [RT02,Rou01,Rou02] das Wardrop-Modell erneut.
Viele bisherige Arbeiten über das Wardrop-Modell waren motiviert durch
das Braess Paradoxon [Bra68] (für eine
kurze Übersicht siehe [RT02], Kapitel 1.2). Dieses
Paradaxon zeigt, dass es Netzwerke gibt, für die sich eigensinnige
Agenten auf echten Teilnetzwerken besser bzgl. der sozialen Kosten
verhalten. Falls das Ziel ist, ein Netzwerk mit möglichst kleiner
Coordination Ratio zu konstruieren, stellt sich ein interessantes
Netzwerkdesign-Problem: Bestimme für ein gegebenes Netzwerk eine Menge
von zu entfernenden Kanten, um ein bestmögliches Routing im Netzwerk
zu erhalten. Solche Netzwerkdesign-Probleme stellen sich zum Beispiel,
wenn Verkehrsingenieure Strassen bestimme sollen, die geschlossen oder
auch in Einbahnstrasses umgewandelt werden sollen, um den
Verkehrsfluss zu verbessern.
Berechnung von Nash Equilibria
Die sozialen Kosten sowie die Kantenlasten eines Nash Equilibriums
sind im Wardrop-Modell eindeutig. Ein Nash Equilibrium kann mit
Hilfe eines konvexen Programms
berechnet werden.
Verhältnis optimale Lösung zu Nash Equilibrium
Analog zum KP-Modell definieren wir die Coordination Ratio als
Quotient aus den sozialen Kosten eines Nash Equilibriums und den
minimalen sozialen Kosten eines Routings. Roughgarden und Tardos [RT02] haben gezeigt, dass im Fall linearer
Latenzfunktionen die Coordination Ratio nach oben durch 4/3
beschränkt ist. Im Fall polynomieller Latenzfunktionen mit Grad
höchstens d lässt sich die obere Schranke
Θ(d/log(d)) zeigen [Rou02]. Zudem
sind die sozialen Kosten eines Nash Equilibriums durch die sozialen
Kosten eines optimalen Schedules mit doppelten Paketgrössen nach oben
beschränkt [RT02].
Netzwerkdesign-Problem
Wie schon erwähnt ist hier das Ziel, für eine gegebene
Instanz ein Teilnetzwerk zu bestimmen, auf dem die sozialen Kosten
eines Nash Equilibriums minimal sind. Im Fall linearer
Latenzfunktionen gibt es dafür keinen (4/3-ε)-Approximationsalgorithmus, es sei
denn P=NP [Rou01]. Dieses Ergebnis
lässt sich auch auf stetige, monoton wachsende
Latenzfunktionen erweitern. In diesem Fall existiert kein (n/2-ε)-Approximationsalgorithmus.
Als Vorarbeit im Bereich Nash Equilibria haben wir vor allem das
KP-Modell untersucht.
Im Fall reiner Nash Equilibria entsprechen die sozialen Kosten den
maximalen Kosten eines Agenten. Zur Berechnung eines reinen Nash
Equilibriums mit minimalen sozialen Kosten wurde ein polynomieller
Algorithmus entwickelt, der jede Zuordnung der Benutzer zu den Links
in ein Nash Equilibrium mit gleichen oder kleineren sozialen Kosten
umwandelt. Dieser Vorgang wird Nashification genannt. Im Fall
von identischen Links ist dies mit Hilfe von
greedy selfish steps möglich, d.h. mit Schritten, in denen
genau einem Agent erlaubt wird sich grösstmöglich zu
verbessern. Allerdings können dabei Sequenzen mit exponentiell vielen
Schritten auftreten [FGL+03]. Im Fall von related Links konnte ein
polynomieller Nashification-Algorithmus entwickelt werden, dessen
Schritte nicht notwendigerweise selfish steps sind [FGL+03]. Zusammen mit dem PTAS für das multiprocessor scheduling problem [HS87,HS88] erhält man ein PTAS für die Approximation des
besten Nash Equilibriums.
Im Gegensatz dazu ist das schlechteste Nash Equilibrium schon auf
identischen Links nicht 2-approximierbar [GLM+02]. Wir konnten eine neue obere Schranke für
die Coordination Ratio angeben, die für kleine Anzahlen von Links
besser ist als die bisherigen Ergebnisse [FGL+03]. Darüber hinaus haben wir einen neuen
strukturellen Parameter eingeführt, der nicht, wie bisher üblich, nur
von der Anzahl Links oder nur von den Kapazitäten der Links abhängt,
sondern beides miteinander vereint. Dieser Parameter ermöglichte es
uns, die Schranken in [CV02] leicht zu verbessern.
Ausserdem konnten wir die Fully Mixed Conjecture sowohl für identische
Paketgrössen, related Links und n=2 als auch für identische
Paketgrössen, identische Links und m=2 beweisen. Ferner konnten
wir zeigen, dass die Fully Mixed Conjecture im Fall von unrelated
Links zwar noch für 2 Agenten auf 2 Links gilt, für 3 Agenten auf 2
Links allerdings widerlegt werden kann [LMM+03].
Eine Übersicht vieler Ergebnisse sowohl im KP-Modell als auch im
Wardrop-Modell haben wir in einem Übersichtspapier zusammengefasst. Es
erscheint als invited paper im Tagungsband der MFCS 2003 [MFG+03].
Wir wollen die beim Selfish Routing in Netzwerken auftretenden
Probleme besser verstehen lernen. Dazu wollen wir
Selfish-Routing-Modelle im Umfeld des KP-Modells und des
Wardrop-Modells untersuchen. Die bisherigen Arbeiten zum KP-Modell
haben noch viele Fragen offen gelassen, die wir in der kommenden
Antragsphase betrachten wollen:
Für unrelated Links wollen wir unsere Erfahrung auf
identischen und related Links nun dazu nutzen, um diesen Fall zu
analysieren. Ziel ist es einen polynomiellen Algorithmus anzugeben,
der immer ein Nash Equilibrium liefert. Zudem soll die
Approximierbarkeit von best-case und worst-case Nash Equilibria
untersucht werden. Desweiteren planen wir, die verallgemeinerte
Variante, in der jeder Agent nur eine vorgegebene Teilmenge der Links
benutzen darf, zu untersuchen.
Im Zuge unserer bisherigen Untersuchungen haben wir für einige
Spezialfälle die Fully Mixed Conjecture bewiesen. Wir wollen
diese Erkenntnisse auf ihre globale Anwendbarkeit hin untersuchen
und so einen allgemeinen Beweis der Vermutung finden oder sie
widerlegen.
Wir haben gezeigt, dass das worst-case Nash Equilibrium nicht
2-approximierbar ist. Offen ist, ob dieses Ergebnis scharf ist. Mit
Hilfe von Testläufen und Strukturanalysen sollen Algorithmen
und ihre worst-case Instanzen gefunden werden, die eine
Gütegarantie für die Approximation des worst-case Nash
Equilibriums liefern. Ferner wollen wir untersuchen, ob das
Einführen von Mechanismen zur Verbesserung der coordination
ratio genutzt werden kann.
Im Fall identischer Links konnten wir wie schon erwähnt einen
Algorithmus angeben, der jede reine Zuordnung mit Hilfe von (greedy)
selfish steps in ein reines Nash Equilibrium mindestens gleicher
Güte umwandelt. Für related Links ist nicht bekannt, ob es
ebenfalls einen solchen Algorithmus gibt. Bisher ist das Umwandeln
in ein Nash Equlibrium lediglich auch unter Verwendung von
Schritten, in denen sich der Agent verschlechtert,
möglich. Deshalb wollen wir untersuchen, aus welchem Grund der
Algorithmus auf identischen Links nicht auf related Links
übertragbar ist. Die daraus gewonnenen Erkenntnisse sollen die
Frage beantworten helfen, ob auch ein Nashification-Algorithmus auf
related Links existiert, der nur (greedy) selfish steps benutzt.
Das Wardrop-Modell und das KP-Modell unterscheiden sich in
wesentlichen Punkten. Im KP-Modell sind die Pakete nicht teilbar und
die globalen Kosten sind definiert als Maximum der individuellen
Kosten. Im Wardrop-Modell sind die Pakete beliebig teilbar, und die
globalen Kosten sind definiert als Summe der individuellen Kosten. Im
Wardrop-Modell gibt es sehr weitgehende Ergebnisse für beliebige
Graphen, im KP-Modell sind wir gerade dabei, die Eigenschaften des
Spieles mit zwei Knoten zu verstehen. Als wesentlichen Grund für
diesen Unterschied sehen wir die Teilbarkeit der Pakete an. Im
Wardrop-Modell kann man Methoden der konvexen Optimierung benutzen,
das Nash Equilibrium ist eindeutig. Im KP-Modell existieren im
Allgemeinen viele Nash Equilibria mit sehr unterschiedlichen Kosten,
und methodisch bewegt man sich im Bereich der kombinatorischen
Optimierung. Wir wollen das Zusammenspiel der verschiedenen Parameter
dieser beiden Modelle untersuchen und werden dazu die folgenden drei
Modelle betrachten:
Individuelle Kosten wie im KP-Modell
Globale Kosten = Summe der individuellen Kosten
Individuelle Kosten wie im Wardrop-Modell
Globale Kosten = Maximum der individuellen Kosten
teilbare Pakete, aber Latenz eines Pfades definiert als
Maximum der Latenz der Kanten
Globale Kosten = Maximum der individuellen Kosten
Dabei werden wir unser Modell (1) zuerst wieder auf das einfache
Netzwerk mit zwei Knoten und parallelen Kanten beschränken. Ziel
der Untersuchung ist ein besseres Verständnis dafür, welche
Parameter für welche Eigenschaften verantwortlich sind. Alle drei
Modelle haben auch praktische Bedeutung. Modell (1) ist die
Diskretisierung des Wardrop-Modells, Modell (2) hat die gleichen
Equilibria wie das Wardrop-Modell und die Kundenzufriedenheit als
Optimierungsziel. Modell (3) spiegelt das Routing in
Kommunikationsnetzwerken wider, das stärker durch die maximale
Belastung einer Kante als durch die Summe der Kantenbelastung gegeben
ist.
Natürlich wollen wir auch versuchen, Ergebnisse über Nash
Equilibria im Fall nicht teilbarer Pakete für allgemeinere Netzwerke
als das aus lediglich zwei Knoten und m Links bestehende Netzwerk im
KP-Modell zu erhalten.
Die im Selfish Routing erlangten Erkenntnisse wollen wir auch auf
verwandte Szenarien anwenden. Untersuchen werden wir z.B. das aus dem
k-Partitionierungsproblem abgeleitete Partitionierungsspiel, in dem
die Lasteinheiten selbstständige Agenten sind und das globale Ziel
darin besteht, die Zahl der externen Kanten zu minimieren oder die
``Form'' der Partitionen zu optimieren. Hier wissen wir aus eigenen
Vorarbeiten, dass eine gewisse Zusammenarbeit gegenüber rein
lokalem Vorgehen Vorteile bringt. Die Möglichkeiten und Grenzen
dieses Ansatzes sollen detailiert untersucht werden.
Nach dem Satz von Nash existiert stets ein Nash Equilibrium. Offen
ist noch, ob sich für ein beliebiges Spiel ein Nash Equilibrium
stets in polynomieller Zeit berechnen lässt. Dies ist wohl die
prominenteste offene Frage in diesem Themenkreis, und wir werden sie
im Auge behalten.
Kooperation mit A3
In den bisherigen Antragsphasen wurden im Teilprojekt A3 unter anderem
lokalen Heuristiken und Verfahren zur Berechnung von Lösungen für
das Graphpartitionierungsproblem (Helpful Sets) und das
Lastbalancierungsproblem (Diffusion) auf verteilten Netzwerken
entwickelt. Dabei wurde immer davon ausgegangen, dass die Prozessoren
sich gutmütig bezüglich der globalen Zielfunktion verhalten.
In der kommenden Antragsphase sollen die obigen Verfahren so erweitert
werden, dass auch eigensinnige Prozessoren zulässig
sind. Hierzu sollen die im Teilprojekt A2 entwickelten Methoden
genutzt werden. In Kooperation mit A3 soll insbesondere analysiert
werden, in wie weit sich die Eigensinnigkeit der Prozessoren auf die
Güte der berechneten Lösung auswirkt.
D. Bienstock.
ε-approximate linear programs: new bounds and computation.
In Proceedings of the 11th ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 1-2, 2000.
A. Czumaj and B. Vöcking.
Tight bounds for worst-case equilibria.
In Proceedings of the 13th ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 413-420, 2002.
E. Even-Dar, A. Kesselmann, and Y. Mansour.
Convergence time to nash equilibria.
In Proceedings of the 30th International Colloquium on Automata,
Languages and Programming (ICALP), 2003.
D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis.
The structure and complexity of nash equilibria for a selfish routing
game.
In Proceedings of the 29th International Colloquium on Automata,
Languages and Programming (ICALP), pages 123-134, 2002.
D. S. Hochbaum and D. Shmoys.
Using dual approximation algorithms for scheduling problems:
theoretical and practical results.
Journal of the ACM, 34(1):144-162, 1987.
D. S. Hochbaum and D. Shmoys.
A polynomial approximation scheme for scheduling on uniform
processors: using the dual approximation approach.
SIAM Journal on Computing, 17(3):539-551, 1988.
O. Jahn, R.H. Möhring, A.S. Schulz, and N.E. Stier Moses.
System-optimal routing of traffic flows with user constraints in
networks with congestion.
Technical report, MIT Sloan School of Management Working Paper No.
4394-02, 2002.
Y. A. Korilis, A. A. Lazar, and A. Orda.
Architecting noncooperative networks.
IEEE Journal on Selected Areas in Communications,
13(7):1241-1251, 1995.
E. Koutsoupias, M. Mavronicolas, and P. Spirakis.
Approximate equilibria and ball fusion.
In Proceedings of the 9th International Colloquium on Structural
Information and Communication Complexity, 2002.
E. Koutsoupias and C. Papadimitriou.
Worst-case equilibria.
In Proceedings of the 16th Symposium on Theoretical Aspects of
Computer Science (STACS), pages 404-413, 1999.
B. M. Maggs, F. Meyer auf der Heide, B. Vöcking, and M. Westermann.
Exploiting locality for networks of limited bandwidth.
In Proceedings of the 38th IEEE Symposium on Foundations of
Computer Science (FOCS), pages 284-293, 1997.
M. Mavronicolas and P. Spirakis.
The price of selfish routing.
In Proceedings of the 33rd ACM Symposium on Theory of Computing
(STOC), pages 510-519, 2001.
T. Roughgarden.
Designing networks for selfish users is hard.
In Proceedings of the 42nd Annual Symposium on Foundations of
Computer Science (FOCS'01), pages 472-481, 2001.
T. Roughgarden.
The price of anarchy is independent of the network topology.
In Proceedings of the 34th Annual ACM Symposium on the Thoery of
Computing (STOC'02), pages 428-437, 2002.
T. Roughgarden and E. Tardos.
How bad is selfish routing?
In Proceedings of the 41st IEEE Symposium on Foundations of
Computer Science (FOCS), pages 93-102, 2000.
A. S. Schulz and N. E. Stier Moses.
On the performance of user equilibria in traffic networks.
Technical report, MIT Sloan School of Management Working Paper No.
4274-02, 2002.
J.G. Wardrop.
Some theoretical aspects of road traffic research.
In Proceedings of the Institute of Civil Engineers, Pt. II, Vol.
1, pages 325-378, 1956.
R. Feldmann, M. Gairing, T. Lücking, B. Monien, and M. Rode.
Nashification and the coordination ratio for a selfish routing game.
In Proceedings of the 30th International Colloquium on Automata,
Languages and Programming (ICALP), pages 514-526, 2003.
T. Lücking, M. Mavronicolas, B. Monien, M. Rode, P. Spirakis, and I. Vrto.
Which is the worst-case nash equilibrium?
In Proceedings of the 28th International Symposium on
Mathematical Foundations of Computer Science (MFCS), pages 551-561, 2003.
T. Lücking, B. Monien, and M. Rode.
On the problem of scheduling flows on distributed networks.
In Proceedings of the 27th International Symposium on
Mathematical Foundations of Computer Science (MFCS), pages 495-505, 2002.
M. Gairing, T. Lücking, M. Mavronicolas, B. Monien, and P. Spirakis.
Extreme nash equilibria.
Technical Report FLAGS-TR-03-10, Universität Paderborn, 2002.
B. Monien, R. Feldmann, M. Gairing, T. Lücking, and M. Rode.
Selfish routing in non-cooperative networks: A survey.
In Proceedings of the 28th International Symposium on
Mathematical Foundations of Computer Science (MFCS 2003), pages 21-45, 2003.
