Prof. Dr. Burkhard Monien
Parallel Computing
Universität Paderborn

Eigennütziges Routing in Netzwerken: Algorithmen und Komplexität

Als Folge der neuen technologischen Entwicklung sind große, hoch dynamische, vernetzte Systeme entstanden, deren Verhalten durch das Zusammenwirken autonomer Agenten bestimmt wird. Das Internet und Verkehrssysteme sind typische Beispiele solcher Systeme. Jeder autonome Agent handelt selbstsüchtig und versucht, seine eigenen privaten Kosten zu Optimieren. Szenarien dieses Typs können als Spiele modelliert werden. Nash-Äquilibria repräsentieren die stabilen Zustände: Kein Agent kann sich durch einseitige Änderung seiner Strategie verbessern. Unter Optimierungsgesichtspunkten ist vor allem die Bestimmung des durch Mangel an Kooperation bedingten Verlustes, des sog. "Preis der Anarchie", von Interesse und seine Verkleinerung durch die Einführung von Zusatzregeln, an die sich die Agenten, bei sonst eigenständigem Handeln, halten müssen.

Die Untersuchung dieser Fragestellungen unter algorithmischen Gesichtspunkten ist in den letzten Jahren zu einem sehr aktiven Forschungsgebiet der Informatik geworden. Wir berichten über neue Ergebnisse für die spezielle Problemstellung der Auswahl von Verbindungswegen in Netzwerken.

Dieses Kolloquium findet anlässlich der Pensionierung von Prof. Dr. Manfred Kudlek statt.