Vortragender: Dr. Thomas Kesselheim, MPI für Informatik, Saarbrücken
Titel: Von Algorithmen zu einfachen und robusten Mechanismen
Zeit: 09.05.16, 09:30
Ort: IZ 161
Abstract:
Beim Entwurf von Mechanismen werden zum Beispiel Auktionen mit guten
Eigenschaften gesucht. In einem üblichen Szenario müssen Güter Spielern
zugeordnet werden. Jeder Spieler hat eine Bewertungsfunktion und es ist
das Ziel die Summe der Bewertungen zu maximieren. Das Problem ist, dass
es sich bei diesen Bewertungsfunktionen um private Informationen der
Spieler handelt. Dieser möchten ihren eigenen Nutzen maximieren und
verhalten sich entsprechend strategisch. Der klassische Ansatz ist es,
Mechanismen zu entwerfen, in denen jeder einzelne Spieler einen Anreiz
hat, seine Bewertungsfunktion wahrheitsgemäß mitzuteilen. Aus
algorithmischer Sicht stößt dieser Ansatz jedoch schnell an Grenzen,
weil im Normalfall eine approximative Lösung der Optimierungsprobleme
nicht ausreicht.
Wir verfolgen einen alternativen Ansatz: Wir setzen (Approximations-)
Algorithmen für die Optimierungsprobleme unmittelbar als Mechanismen
ein. Dabei nehmen wir strategisches Verhalten der Spieler in Kauf. Dies
führt zu einem Spiel, dessen Gleichgewichte wir untersuchen. Wir zeigen,
dass Algorithmen, die auf der Relax-and-Round-Technik basieren, sehr
hilfreich sind, um Mechanismen mit guten Gleichgewichten zu entwerfen.
Ferner gehen wir der Frage auf den Grund, welche kombinatorischen
Eigenschaften eines Algorithmus zu diesem Effekt führen, und
präsentieren eine exakte Charakterisierung. Dies ermöglicht es uns,
Unmöglichkeitsergebnisse und damit die Optimalität von gewissen
Mechanismen herzuleiten. Wie wir zeigen, lassen sich in vielen Fällen
derartige Algorithmen auch zum Entwurf von Posted-Price-Mechanismen
nutzen. Dies sind anreizkompatible Mechanismen im klassischen Sinn,
gleichzeitig aber auch Online-Algorithmen mit Kenntnis einer
Wahrscheinlichkeitsverteilung.
