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.