Logo der Universität Wien

Über uns

Algorithmische Spieltheorie

Im Bereich der algorithmischen Spieltheorie werden sowohl algorithmische Fragestellungen der klassischen Spieltheorieals als auch neue Fragestellungen erforscht, die in rechnerbasierten Anwendungen, gerade auch durch das Internet entstehen. Diese reichen von Fragen der Komplexität, wie beispielsweise die Komplexität der Berechnung bestimmter Gleichgewichte bei Spielen, über Lernen bei wiederholten Auktionen, bis hin zu Zuteilungs- und Preisermittlungsfragen in spezifischen Märkten. Zurzeit forschen wir an den zuletzt genannten Fragestellungen im Rahmen eines WWTF-finanzierten Forschungsprojektes an Problemstellungen aus den Systemen der Onlinewerbung.

Graphalgorithmen und ihre Anwendungen

Graphen werden in vielen Anwendungen benutzt, um das Verhältnis zwischen Daten zu modellieren. Eine dieser Anwendungen ist die computergestuetzte Verfikation. Hierbei wird das System oder das Programm, welches verifiziert werden soll, als ein Graph dargestellt, bei dem die Knoten den Zustand eines Systems determinieren und die Kanten die Übergänge zwischen diesen Zuständen beschreiben. Die Verifikationsalgorithmen ueberpruefen Eigenschaften dieses Graphens, um die Fehlerfreiheit eines Systems zu bestimmen. Deswegen sind Graphalgorithmen der zentrale Teil der computergestuetzten Verfikation. Herzstück der Moderne Algorithmen-Techniken, wie etwa dynamische Graph-Algorithmen und Randomisierung, wurden in den letzten Jahren entwickelt und haben zur schnelleren Lösung zahlloser Probleme – wie beispielsweise in der Evolutionsbiologie die Entdeckung von Abkürzungen (minimum cuts) in Netzwerken um homöomorphe Teilbäume ausfindig zu machen. Allerdings werden diese aktuellen Graph-Algorithmen noch nicht in der Verifkation verwendet. Unsere Zielsetzung ist es zu erforschen, wie diese Graphalgorithmen eingesetzt werden können, um schnellere Algorithmen für essentielle algorithmische Fragestellungen zu entwickeln. Gemeinsam mit Krishnendu Chatterjee (IST Austria) arbeiten wir in einem Forschungsprojekt an diesem Thema.

Kontakt
Fakultät für Informatik
Universität Wien

Währinger Straße 29
1090 Wien