On June 18, 2013, Jun.-Prof. Dr. Alexander Skopalik will give a lecture about "Algorithmen, Spiele, Netzwerke" in the context of the SFB 901.
Abstract:
Viele Entscheidungsprozesse wie z.B. die Allokation von Ressourcen, finden heute im Internet und anderen Netzwerken statt oder sind zumindest aus informationstechnisch erfassbar. Während die klassische Spieltheorie das Verhalten von (meist egoistischen) Akteuren modelliert und das Ergebnis solcher Situationen beschreibt, beschäftigt die Algorithmische Spieltheorie mit der Frage der Berechenbarkeit solcher Vorhersagen und der Komplexität verwandter Berechnungs- und Optimierungsprobleme.
In diesem Vortrag konzentrieren wir uns auf sog. Auslastungsspiele und die Berechnung bzw. Approximation reiner Nash Gleichgewichte. Das Berechnen solcher Gleichgewichte und selbst ihre Approximation ist im Allgemeinen ein schweres Problem. Wir stellen einen überraschend einfachen Algorithmus mit polynomieller Laufzeit vor, der approximative Gleichgewichte in einer großen Klasse von Auslastungsspielen berechnet.